linkedlist_implentation_usingarray.cpp File Reference

Linked list implementation using Arrays. More...

#include <iostream>

Include dependency graph for linkedlist_implentation_usingarray.cpp:

Go to the source code of this file.

Classes
class	Node< ValueType >

Functions
void	initialise_list ()
int	getnode ()
void	freeNode (int nodeToBeDeleted)
void	insertAtTheBeginning (int data)
void	insertAtTheEnd (int data)
void	display ()
int	main ()

Variables
Node	AvailArray [100]
	array that will act as nodes of a linked list.
int	head = -1
int	avail = 0

Detailed Description

Linked list implementation using Arrays.

The difference between the pointer implementation of linked list and array implementation of linked list:

1. The NULL is represented by -1;
2. Limited size. (in the following case it is 100 nodes at max). But we can reuse the nodes that are to be deleted by again linking it bacj to the list.

Definition in file linkedlist_implentation_usingarray.cpp.

Function Documentation

display()

void display

(

)

Definition at line 69 of file linkedlist_implentation_usingarray.cpp.

               {
    int temp = head;
    while (temp != -1) {
        std::cout << AvailArray[temp].data << "->";
        temp = AvailArray[temp].next;
    }
    std::cout << "-1" << std::endl;
}

freeNode()

void freeNode

(

int

nodeToBeDeleted

)

This function when called will delete the node with the index presented as an argument, and will put back that node into the array.

Definition at line 42 of file linkedlist_implentation_usingarray.cpp.

                                   {
    AvailArray[nodeToBeDeleted].next = avail;
    avail = nodeToBeDeleted;
}

getnode()

int getnode

(

)

This will return the index of the first free node present in the avail list

Definition at line 32 of file linkedlist_implentation_usingarray.cpp.

              {
    int NodeIndexToBeReturned = avail;
    avail = AvailArray[avail].next;
    return NodeIndexToBeReturned;
}

initialise_list()

void initialise_list

(

)

Definition at line 23 of file linkedlist_implentation_usingarray.cpp.

                       {
    for (int i = 0; i <= 98; i++) {
        AvailArray[i].next = i + 1;
    }
    AvailArray[99].next = -1;  // indicating the end of the linked list.
}

insertAtTheBeginning()

void insertAtTheBeginning

(

int

data

)

The function will insert the given data into the front of the linked list.

Definition at line 50 of file linkedlist_implentation_usingarray.cpp.

                                    {
    int newNode = getnode();
    AvailArray[newNode].data = data;
    AvailArray[newNode].next = head;
    head = newNode;
}

insertAtTheEnd()

void insertAtTheEnd

(

int

data

)

Definition at line 57 of file linkedlist_implentation_usingarray.cpp.

                              {
    int newNode = getnode();
    int temp = head;
    while (AvailArray[temp].next != -1) {
        temp = AvailArray[temp].next;
    }
    // temp is now pointing to the end node.
    AvailArray[newNode].data = data;
    AvailArray[newNode].next = -1;
    AvailArray[temp].next = newNode;
}

main()

int main

(

void

)

Main function

Definition at line 79 of file linkedlist_implentation_usingarray.cpp.

           {
    initialise_list();
    int x, y, z;
    for (;;) {
        std::cout << "1. Insert At The Beginning" << std::endl;
        std::cout << "2. Insert At The End" << std::endl;
        std::cout << "3. Display" << std::endl;
        std::cout << "4.Exit" << std::endl;
        std::cout << "Enter Your choice" << std::endl;
        std::cin >> z;
        switch (z) {
        case 1:
            std::cout << "Enter the number you want to enter" << std::endl;
            std::cin >> x;
            insertAtTheBeginning(x);
            break;
        case 2:
            std::cout << "Enter the number you want to enter" << std::endl;
            std::cin >> y;
            insertAtTheEnd(y);
            break;
        case 3:
            std::cout
                << "The linked list contains the following element in order"
                << std::endl;
            display();
            break;
        case 4:
            return 0;
        default:
            std::cout << "The entered choice is not correct" << std::endl;
        }
    }
 
    return 0;
}

Variable Documentation

avail

int avail = 0

Definition at line 22 of file linkedlist_implentation_usingarray.cpp.

AvailArray

Node AvailArray[100]

array that will act as nodes of a linked list.

Definition at line 19 of file linkedlist_implentation_usingarray.cpp.

head

int head = -1

Definition at line 21 of file linkedlist_implentation_usingarray.cpp.