Linked List

  Linked  List, is a data structure made of unit structures called nodes. Linked List is a container type data structure with one or more data fields and links to successive node.

Different types of Linked list exists.

·               Singly Linked List

·               Doubly Linked List

·               Circularly Linked List

·                   Skip List etc...

      We'll Learn one by one. First Singly Linked List: In Singly linked list each node has one or more data fields and single link to successive node. We use the name head for root node. Here the image illustrates the singly linked list. The link part of last node is SET to NULL in order to terminate the list.

Hence our Linked list starts with head node and terminate at NULL pointer. 

Eg: for node structure

struct Node

{

    int data;

    struct Node* link;  }

Usually the list will be build up with the node and functions are written to operate over it.

But we use a OOP approach to define the node and list. For introduction, we use the traditional approach.

ALGORITHM

ALGORITHM: PUSH(HEAD,INPUT)     

·         START PUSH()

·         CREATE  a new node = NewNode

·         SET Data field of NewNode = Input

·         SET Link field of NewNode =  Head

·         SET Head = NewNode

·         END OF PUSH()

ALGORITHM: SHOW(HEAD)

·         START SHOW()

·         CREATE a Temporary node = TEMP

·         TEMP = HEAD

·         LOOP until TEMP = NULL

·         PRINT Data of TEMP

·         SET TEMP = Link of TEMP

·         END OF SHOW()

IMPLEMENTATION OF LINKED LIST ALGORITHMS

1.  struct node

2.  {  int data;            //data field

3.     struct node* link;  //link field

4.     }

5.   

6.  int main()

7.  {    struct node* head;

8.       int data;

9.       //call to push() to add the data at beginning of list

10.      push(&head,data);     

11.//call to show() to display the values

12.//contained in node of the

13.//list with head as root node

14.show(head);      

15. }

16.void push(struct **head, int dat)

17.{     strcut node* newnode =  new node; 

18.      newnode->data=dat;

19.      newnode->link=*head;

20.      *head=newnode;

21.      }

22. 

23.void show(struct *head)

24.{      struct  node* curr = head;

25.        //iterate over the node of list

26.       //and prints the values

27.        //contained in each node

28.       while(curr!=NULL)

29.       {    cout<<”Data:”<data<

30.             curr=curr->link;   }

31.}

It's a  simple program to illustrate the concept of linked list. Working of this program is discussed throughout this article.

Why Linked lists are so important? Linked lists are useful to study for two reasons. Most obviously, linked lists are a data structure which you may want to use in real programs. Seeing the strengths and weaknesses of linked lists will give you an appreciation of the some of the time, space, and code issues which are useful to thinking about any data structures in general. Somewhat less obviously, linked lists are great way to learn about pointers. In fact, you may never use a linked list in a real program, but you are certain to use lots of pointers. Linked list problems are a nice combination of algorithms and pointer manipulation. Traditionally, linked lists have been the domain where beginning programmers get the practice to really understand pointers.

Array & Its Disadvantages

Arrays Arrays are probably the most common data structure used to store collections of elements. In most languages, arrays are convenient to declare and the provide the handy [ ] syntax to access any element by its index number. The following example shows some typical array code and a drawing of how the array might look in memory. The code allocates an array int scores[100], sets the first three elements set to contain the numbers 1, 2, 3 and leaves the rest of the array uninitialized... void ArrayTest() {      int scores[100];      // operate on the elements of the scores array...      scores[0] = 1;      scores[1] = 2;      scores[2] = 3;            }                                                                                       Here is a drawing of how the scores array might look like in memory. The key point is that the entire array is allocated as one block of memory. Each element in the array gets its own space in the array. Any element can be accessed directly using the [ ] syntax.         scores 1 2 3 -3451 …..   23142 index     0 1 2 3 …....      99                                                                                                         Once the array is set up, access to any element is convenient and fast with the [ ] operator. Array access with expressions such as scores[i] is almost always implemented using fast address arithmetic: the address of an element is computed as an offset from the start of the array which only requires one multiplication and one addition. The disadvantages of arrays are...      1) The size of the array is fixed — 100 elements in this case. Most often this         size is specified at compile time with a simple declaration such as in the         example above . With a little extra effort, the size of the array can be         deferred until the array is created at runtime, but after that it remains fixed.         (extra for experts) You can go to the trouble of dynamically allocating an         array in the heap and then dynamically resizing it with realloc(), but that         requires some real programmer effort.      2) Because of (1), the most convenient thing for programmers to do is to         allocate arrays which seem "large enough" (e.g. the 100 in the scores         example). Although convenient, this strategy has two disadvantages: (a)         most of the time there are just 20 or 30 elements in the array and 70% of         the space in the array really is wasted. (b) If the program ever needs to         process more than 100 scores, the code breaks. A surprising amount of         commercial code has this sort of naive array allocation which wastes space         most of the time and crashes for special occasions. (Extra for experts) For         relatively large arrays (larger than 8k bytes), the virtual memory system         may partially compensate for this problem, since the "wasted" elements         are never touched.      3) (minor) Inserting new elements at the front is potentially expensive         because existing elements need to be shifted over to make room.

Explanation of Code:

Line No.	Explanation
1.	Declaration & Definition of data structure of node.
2.	Data field of node -declaration
3.	Link field of node -declaration
4.	Declaration of structure ends
5.
6.	Entry point of program main() block
7.	Creating an instance of node data-structure.
8.	Declaration of variable dat to hold the input data
9.
10.	Call to push() functions that inserts the argument passed to it at front-end of the list
11.
12.
13.
14.
15.	Call to show() function that iterates over the nodes of the list and prints the value contained in it to the screen
16.	End of the program.
17.
18.	Definition of push() functions starts.
19.	A temporary node-newnode is created to hold the input data(argument)
20.	Data field of newnode is assigned to input data value
21.	Link field of newnode is pointed to the address of head node
22.	Now the head is made pointing to newnode, thus adding a new node at front end.
23.	End of push() function.
24.
25.	Definition of show() function starts.
26.	A temporary node - curr is created and assigned the address of head node. It is used to iterate over the list
27.	Loop starts  with condition: curr!=NULL. Because the termination of list is indicated by the NULL pointer.
28.	Data value of current node is printed to the screen.
29.	The node curr is made pointing to the next node. Loop continues until the curr pointer reaches the end of the list i.e until curr==NULL.
30.	End of show() function.

Memory Maps:

Memory maps are much helpful in understanding the operation of functions related to linked lists.

Here we use memory mapping techniques to understand the operation of push() function. Assume that our list already has two nodes now we are adding one more node at front.

Line no	Memory Map
Before push operation
19
20
21
22

/*************************************/

/**Program: Linked List Model       */

/**Author : Vanangamudi             */

/************************************/

#include

#include

#include

#define ESC 27

//single node in a list

struct Node

{

    int data;

    int index ;

    struct Node* link;

    public:

      void show(){ cout<<"Index\t:"<<<"\tData\t:"<<

     

      };

//strcuture for contain the nodes -> list

struct List

{

    Node* head;

    Node* tail;

    int last;

   

    public:

    //Constructors

    List()

    { head = new Node;

      head->data=0;

      head->link=NULL;

       

      tail = head; 

        }

                 

    //member functions

      void append(int);

      void push(int);

      void insertAt(int,int);

      void show();

     

      int isEmpty();

      int no_of_nodes();

     void index();

     

      Node* delNode(int);

      Node Search(int);

      };

void List::append(int dat)

{

   struct Node* newnode = new Node;

   newnode->data = dat;

  

   if(head->data==0){ head->data=dat; }

   else

   {  newnode->link = head;

      head= newnode;

     }

   this->index();

   }

void List::push(int dat)

{

       struct Node* newnode = new Node;

       struct Node* temp=head;

  

       newnode->data=dat;

       newnode->link=NULL;

     

      if(head->data==0){ head->data=dat;  }

      else

      {    while(temp->link!=NULL)

           { temp=temp->link;  }

           temp->link = newnode;

           }

   

   this->index();

   }

void List::insertAt(int dat, int pos)

{

   struct Node* newnode = new Node;

   newnode->data= dat;

 

   struct Node* prev = new Node;

   struct Node* temp = head;

   while(temp->link!=NULL)

   {

      if(temp->index == pos ) { break;  }

        prev = temp;

        temp=temp->link;

      }

     

   prev->link= newnode;

   newnode->link = temp;

   this->index();

      }//insertAt()

void List::index()

{

     struct Node* temp=head;

     int ind=0;

     while(temp!=NULL)

     {   temp->index=++ind;

         temp=temp->link;

         }

         }     

      

void List::show()

{

   struct Node* temp = head;

  

   while(temp!=NULL)

   {

      temp->show();

      temp= temp->link;

      }

        }   //show()

int List::no_of_nodes()

{

   int count=1;

   struct Node* temp=head;

   while(temp->link!=NULL)

   {

      count++;

      temp=temp->link;

      }

   return(count);

      }//total no of items;

int List::isEmpty()

{  

   if(!no_of_nodes()) { return(1) ; }

   else { return(0);  }

   }

Node List::Search(int dat)

{

   struct Node* temp = head;

   while( temp->data!=dat)

   {temp=temp->link;   }

   struct Node tempp = *temp;

   tempp.link=NULL;

   return(tempp);

   }//srch()

Node* List::delNode(int dat)

{

   struct Node* temp = head;

   if(head->data==dat)

   {

      head=head->link;

      temp->link=NULL;

      this->index();

      return(temp);

       }

   else

   { while(temp->link->data!=dat)

       {   temp=temp->link;   }

     temp->link=temp->link->link;

     this->index();    

     return(temp);   }

    

     }//delNode()

    

/////////////////////////////////////////////////////

/////Functions for manipulation on main program//////

/////////////////////////////////////////////////////

//Menu_choice() displays the menu,

//and reads the choice and returns it

int Menu_Choice()

{

    int choice;

   

    cout<<"Menu:\n"<

    cout<<"1.Push Data"<

    cout<<"2.Append Data"<

    cout<<"3.Insert Data"<

    cout<<"4.Delete Data"<

    cout<<"5.No.of Items"<

    cout<<"6.List is Empty?"<

    cout<<"7.Search Data"<

   

    cout<<"Enter the choice\t:";

    cin>>choice;

    return(choice);

    }//Menu_choice()

   

//getInput()  reads a value and return it   

int getInput()

{

    int data;

    cout<<"Enter the data\t:";

    cin>>data;

    return(data);

   

    }//getInput()

    

    

//////////////////////////////////////////////

int main()

{

  struct List* Listt=new List;

  int index,input,key=0,choice;

    

  while(key!=ESC)

  { //display menu and read the choice

    choice = Menu_Choice();

    switch(choice)

    {

          case 1:

               //repeatedly reads the input and pushes

               //the input into the list

               //until the user presses ESC key

               while(key!=ESC)

               {     input=getInput();

                     Listt->push(input);

                     key=getch();

                     }//end of while loop

               Listt->show();

               break;

              

          case 2:

               //repeatedly reads the input and appends

               //the input into the list

               //until the user presses ESC key

               while(key!=ESC)

               {     input=getInput();

                     Listt->append(input);

                     key=getch();

                     }//end of while loop

               Listt->show();

               break;

              

          case 3:

               //repeatedly reads the input and index and insert

               //the input into the list at given index

               //until the user presses ESC key

               while(key!=ESC)

               {     cout<<"Enter the index and data\t:";

                     cin>>index>>input;

                     Listt->insertAt(input,index);

                     key=getch();

                     }//end of while loop

               Listt->show();

               break;

              

          case 4:

                //repeatedly reads the input and delete the item

               //from the list until the user presses ESC key

               while(key!=ESC)

               {     input=getInput();

                     Listt->delNode(input);

                     key=getch();

                     }//end of while loop

               Listt->show();

               break;

              

          case 5:

                //invoke no_of_node() method of List structure

               cout<<"No. of Items in the list\t:";

               cout<no_of_nodes();

               break;

              

          case 6:

               if(!(Listt->isEmpty()))

               { cout<<"Yes, the list is Empty\n" ;}

               else{ cout<<"The list is not empty";}

               break;

              

          case 7:

               struct Node srch ;

               srch.data=00;

               srch.link=NULL;

              

               cout<<"Enter the data to search\t:";

               cin>>input;

               srch = Listt->Search(input);

              

               if(srch.data==0){ cout<<"Item not found"<

               else{ cout<<"Item found  "<<

               break;

              

                 

               }//end of switch case

       cout<<"Press any key to continue or ES to exit!!!"<

       key =getch();

     }

    getch();

   

}