Linked List

Linked List

Linked list is a linear Data Structure, in which every element or node contains two different parts one of which is the info i.e information or data field and other is the pointer field which contains the address of next node.

Node is a container of a single element of a set. We can implement link list using two different approach

1.         Using Array.(i.e static memory allocation)

2.         Using Linked list (i.e Dynamic  memory allocation)

Array implementation of linked list in C.
Since list is a simply a collection of nodes hence array , may be the one the implementation of linked list.

      Using array one node can be defined as.

      #define NUMNODES 500

      Struct nodetype {

            Int  info, next;

       };

                 Struct nodetype node[NUMNODES];

Here we are creating 500 node using array but one thing that here “node can not be ordered by the array ordering” each must contain within itself a pointer to its successor.

Limitations of array implementations 

Here we have seen that the array can be used to implement linked list in which node are un- ordered and the “next” field tracks the information of the next element of that list.

       But using array as link-list  creates two problem.

1.      1. First the size of the array is fixed at compile time hence there is a great chance of overflow for any large   

         size of the array. 

    2. Second problem is that we have to allocate the whole array at compile time and if there is a need of less 

         number of nodes that memory goes waste and the storage can not be used for other purpose.

Using dynamic memory allocation:

Struct info {

          Int info;

          struct node *next;

};        

        typedef  struct node *NODEPTR;

  Allocation of space:

    If we declare

             NODEPTR = P;

            P = (NODEPTR)malloc(sizeof(struct node));

     

       Will create a node of ‘node’ type and p will contain the address of that node.

Header nodes:

Sometime we need an extra node attached to the list which do not contain the info part  but contains the address of the first element of the list, this type of node is called as header node.

                          In the first look it may seem that we are wasting the memory of the header node, as info field of is not used but header node may contain information like the address of last element of the list or number of elements in list and many more things.

                                                                : Circular link list :

As we all know that linked list is an ADT and one of the functions of this ADT is the traversing of the list, since the last node contains the null values we can not come to the first node using single linked list, in such a situation we use circular linked list. In circular linked list the last node contains the address of first node.

Here is a small problem:  If we traverse list using p=p->next where p is a node and next is the address of the next node contained, then we can not determine whether we  have traverse the whole list or not since the list is circular.

                   Solution for this problem is to keep another pointer p and check every time where list is the start of the linked list

Alternative method is to place a header node as first node of a circular list. This list may be evaluated using 

a special type of value in its info field which is totally different info value from the list info.

                                              : Doubly linked list:

Although circular list has advantage over linear list, it has still some disadvantage that we can not traverse the list in backward direction, for such condition doubly linked list is required.

                   In doubly linked list there are two address field one of which contains the address of the previous node and other contains the address of its next node.

Array implementation:                                                             #define NUMNODES 500 Struct node {     int info;     int left, right;  };  Struct node NODE[NUMNODES];

Dynamic implementation:   Struct node {      int info;       int node *left, *right; }; typedef struct node *NODEPTR;

 It may be a circular doubly linked list, whose last node’s next pointer will contain the address of the first node.

Posted in: Data Structure