Singly Linked List Tutorial

• Tweet

• Tweet

A Linked List, in computer science, is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (also known as, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence (wiki definition).

The biggest advantage of using a linked list over an array is, unlike array, insertion or deletion of any element, in linked list,  can be done without reallocation or reorganization of the entire structure (this is possible in linked list because. unlike array, linked list doesn’t use contiguous memory blocks to store data).

Analogy : Concept of Linked List can be best explained with the analogy of Post office. Suppose there is an agent A who want to send a secret book to Agent B. He went to post office and get a Post box only to found out that the post box is not big enough to contain complete book. Agent A tore upon the book and place a part of it in the post box and kept the rest of the part of book in other post box. Cleverly Agent A placed the key of second post box in post box one and sent key of first post box to Agent B. No matter how large the book is, this scheme can be extended to any number of boxes by always putting the key to the next box in the previous box. Similarly in Linked List a node contain a datum value (part of book) and a reference to next node (key of next post box).

After understanding what a linked list is now its time to get to know what all operations can be performed on a linked list. The various operations are :

• Inserting a node. This can be done at start or end or anywhere in between also.
• Deleting a node from the linked list.
• Traversing a linked list.

This post will take you through detailed steps explaining different operations (along with the code snippets) which can be performed over a Linked List.

So, let’s cut out the theory and jump over to logic and code part. Let’s first discuss how a node of linked list look like. The following is the node definition in C language :

struct Node{
int val;
struct Node *nextNode;
};

The above definition shows that a node have 2 parts, one which contain datum and the other which contain a link to other node.

• Inserting a node in a linked list

  While adding a node in a linked list just three steps need to be done.

  1. First create a new node and set the data value.
  2. Secondly traverse the list to the node where this new node is to be inserted.
  3. Lastly set the reference node of new node to the next node and that of previous node to the new node.

  Have a look at the below code snippet which is showing the above three steps.

  void AddToList(struct Node **head, int num, int position)
  {
      struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
      struct Node *tempNode = (struct Node*)malloc(sizeof(struct Node));
      int counter = 1;
      newNode->val = num;
      newNode->nextNode = NULL;
      tempNode = *head;
      if(*head == NULL)
      {
          printf("\n\tList is empty. Adding node at the start of the list");
          *head = newNode;
          return;
      }
  
      if(position == 1)
      {
          newNode->nextNode = *head;
          *head = newNode;
          return;
      }
  
      // Moving to the position where node is to be inserted.
      while((tempNode->nextNode != NULL) && (counter < position - 1 ))     {         counter++;         tempNode = tempNode->nextNode;
      }
  
      if(tempNode->nextNode == NULL)
      {
          printf("\n\tNot enoguh nodes. Adding new node at last");
          tempNode->nextNode = newNode;
      }
      else
      {
          printf("\n\tAdding new node at given postion");
          newNode->nextNode = tempNode->nextNode;
          tempNode->nextNode = newNode;
      }
  }
  

• Deleting a node from a linked list

  Like adding a node in linked list, follow the following steps to delete a node from linked list.

  1. Traverse the list from where the node is to be deleted.
  2. Set the reference of previous node to next of next Node.
  3. Free the memory of the next node.

  Have a look at the code snippet below to see how the above steps can be achieved.

  void DeleteNode(struct Node **head, int position)
  {
      struct Node *tempNode = (struct Node*)malloc(sizeof(struct Node));
      struct Node *pNode = (struct Node*)malloc(sizeof(struct Node));
      int counter = 1;
      tempNode = *head;
      if(*head == NULL)
      {
          printf("\n\tList empty");
          return;
      }
  
      if(position == 1)
      {
          pNode = *head;
          *head = pNode->nextNode;
          free(pNode);
          return;
      }
  
      while((tempNode->nextNode != NULL)&&(counter < position - 1))     {         counter++;         tempNode = tempNode->nextNode;
      }
  
      if(tempNode->nextNode == NULL)
      {
          printf("\n\tNot enough node");
      }
      else
      {
          pNode = tempNode->nextNode;
          tempNode->nextNode = pNode->nextNode;
          free(pNode);
      }
  }
  

• Traversing a linked list

  Traversing a list is the easiest of all the operations on linked list. While Traversing a linked list just keep moving to next node starting with the head and stopping as the null is encountered. Following code snippet just show how to traverse a linked list an print the value of datum in each node.

  void TraverseList(struct Node **head)
  {
      struct Node *tempNode = (struct Node*)malloc(sizeof(struct Node));
      tempNode = *head;
      if(*head==NULL)
      {
          printf("\n List is Empty");
          return;
      }
  
      tempNode = *head;
      while(tempNode->nextNode!=NULL)
      {
          printf("%d",tempNode->val);
          printf(" - >");
          tempNode = tempNode->nextNode;
      }
  
      printf("%d",tempNode->val);
      return;
  }
  

• Finding length of a linked list

  Finding length of a linked list is same as traversing a linked list. The only extra thing which one need to track is a counter as the one read the list and increment it accordingly. Code snippet below show how to do it.

  int LengthOfList(struct Node *head)
  {
      struct Node *current = head;
      int count = 0;
      while(current != NULL)
      {
          count++;
          current = current->nextNode;
      }
  
      return count;
  }
  

This is all about the linked list. Click here to get the complete code snippet. Keep looking for other articles on idlebrains. Write your comments, feedback and valuable suggestions for improvement in the below Leave a Comment area.

Pritam Hinger

Co-Founder of IdleBrains, is software Engineer by profession with expertise in .NET technologies and data structures. An avid reader and writer, loves to keep himself well versed with new technologies. When not working can be found on Badminton court or chatting with friends. Among other hobbies, loves to listen old hindi numbers of Kishore Kumar and Mukesh.