Linked List

Linked List

            In  a linked list, the elements are not stored in continuous memory locations i.e., the elements of linked list are non-continuous.  A linked list is represented as follows:

     Since the elements are non-continuous, the next element is stored in current element i.e., the address of second element is stored in first element.  The address of third element is stored in second element and so on.  In general, address of (i+1)^th is stored in i^th element.  This address is called Link or Pointer and  element is called Data. The combination Data and Link is called Node.  Typically, node is shown as follows:

  First field in the node is Data Field and Second field is link field.  The link field contains address of the next node.  In the above linked list, the address of second node is 2000, which is stored in link field of I^st node.  The address of the last node is 7000, which is stored in link field of last but one node.  The link field of the last node contains ‘Nil’, which  indicates the end of Linked List.  Nil is the pointer constant.  The address of the first node is stored in the pointer variable “First”.  First always points to the “First Node”.  In other words, ‘First’ is the pointer to the entire linked list.

 Operations on Linked List

Insertion

Case  1.  Insertion in the middle

            Whenever any particular node is to be inserted, all we need to do is change the link field of preceding node to point to new node and link field of new node point to succeeding node.  For example, if we want to insert a new node between i^th and (i+1)^th node, point i^th node link to new node and new node link to (i+1)^th node.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            

                                                                 Before Insertion

                                                                  After Insertion
 
Case 2: Insertion at the Beginning

            Suppose, if we want to insert a new node at the beginning of Linked List, point new node link to first node and change “First” Pointer to new node.

Before Insertion

After Insertion

Case 3: Insertion at the End

            Suppose, if  we want to insert a new element at the end of the linked list, change link field of the last node to point to new node and new node link field contain Nil.

 Before Insertion

 After Insertion

Deletion

Case  1.  Deleting middle node from Linked List

           

            To delete i^th node form linked list, change link field of (i-1)^th node to (i+1)^th node.

Before Deletion

After Deletion 

Case  2.  Deleting first node from Linked List

            To Delete first node, move “first’ pointer to next node.

Before Deletion

 After Deletion

Case  3.  Deleting Last node from the Linked List

            To delete last node change link field of last but one node to contain ‘Nil’

 Before Deletion

After Deletion

Thus for insertion we have to modify two links and for deletion we have to modify one link.

Creating a Node:

            To create a new node we have to use function called “getnode()”. This function creates a new node and ‘p’ is pointer points to that node.   Whenever we want to insert a node first we have to create it.   malloc() is a function which will allocate memory of size “struct node”.  free() is a function will de-allocate memory of node.

To declare a node  in ‘C’,  following is the syntax

struct node

{

   int data;

   struct node *link;

};

struct node * getnode()

{

  struct node *p;

  p=(struct node *)malloc(sizeof(struct node));

  printf("Enter data into the node: ");

  scanf("%d", &p->data);

  p->link=NULL;

  return p;

}

To access each field in the node, we denote p->data to data field and p->link to link field