top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Summary on Linked List.

+1 vote
452 views

Linked List is a linear data structure and it is very common data structure which consists of group of nodes in a sequence which is divided in two parts. Each node consists of its own data and the address of the next node and forms a chain. Linked Lists are used to create trees and graphs.

Following are the important points to be considered:

  • Linked List contains an link element called first.
  • Each Link carries a data field(s) and a Link Field called next.
  • Each Link is linked with its next link using its next link.
  • Last Link carries a Link as null to mark the end of the list.

Types of Linked List

  1. Simple Linked List 

  2. Doubly Linked List 

  3. Circular Linked List

Basic Operations

  • Insertion − add an element at the beginning of the list.

  • Deletion − delete an element at the beginning of the list.

  • Display − displaying complete list.

  • Search − search an element using given key.

  • Delete − delete an element using given key.

Advantages of Linked Lists

  • They are a dynamic in nature which allocates the memory when required.
  • Insertion and deletion operations can be easily implemented.
  • Stacks and queues can be easily executed.
  • Linked List reduces the access time.

Disadvantages of Linked Lists

  • The memory is wasted as pointers require extra memory for storage.
  • No element can be accessed randomly; it has to access each node sequentially.
  • Reverse Traversing is difficult in linked list.

Insertion Operation

Insertion is a three step process −

  • Create a new Link with provided data.
  • Point New Link to old First Link.
  • Point First Link to this New Link.

code snippet for insertion is given below:

    void insertFirst(int key, int data)

    {
     struct node *link = (struct node*) malloc(sizeof(struct node));     
     link->key = key;
     link->data = data;
     link->next = head;  //point it to old first node
     head = link;  //point first to new first node 
    }

Deletion Operation

Deletion is a two step process −

  • Get the Link pointed by First Link as Temp Link.
  • Point First Link to Temp Link's Next Link.

The code snippet for deletion is given below:

struct node* deleteFirst()

 {
   struct node *tempLink = head;
   head = head->next;  //mark next to first link as first
   return tempLink;   //return the deleted link
}

Navigation Operation

Navigation is a recursive step process and is basis of many operations like search, delete etc. −

  •  Get the Link pointed by First Link as Current Link.
  • Check if Current Link is not null and display it.
  • Point Current Link to Next Link of Current Link and move to above step.

The code snippet for Navigation is given below:

   void printList()     

   {
      struct node *ptr = head;
      printf("\n[ ");
      while(ptr != NULL)   //start from the beginning

        {       
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
        }
        printf(" ]");
   }       

Go through this video--

 

posted May 4, 2017 by Neeraj Kumar

  Promote This Article
Facebook Share Button Twitter Share Button LinkedIn Share Button

...