Implementation of Singly Linked List

This article is part of article series - "Datastructures"

Generally a Linked List means "Singly Linked List". It is a chain of records known as Nodes. Each node has at least two members, one of which points to the next Node in the list and the other holds the data.

Figure 1: Singly Linked List

Basically Single Linked Lists are uni-directional as they can only point to the next Node in the list but not to the previous. We use below structure for a Node in our example.

 struct Node
 {
   int Data;
   struct Node *Next;
 }; 

Variable Data holds the data in the Node (It can be a pointer variable pointing to the dynamically allocated memory) while Next holds the address to the next Node in the list.

Figure 2: Node in a Singly Linked List

Head is a pointer variable of type struct Node which acts as the Head to the list. Initially we set 'Head' as NULL which means list is empty.

Basic Operations on a Singly Linked List

• Traversing a List
• Inserting a Node in the List
• Deleting a Node from the List

Traversing a Singly Linked List
Traversing a Singly Linked List is the basic operation we should know before we do other operations like Inserting a Node or Deletion of a Node from the Singly Linked List. Let us see how to traverse Singly Linked List in Figure 1.Let us assume Head points to the first Node in the List.

Pseudocode:

cur = head

forever:

if cur == NULL
break

cur = cur->Next

Complexity:
To traverse a complete list of size 'n' it takes

• Time complexity: O(n).
• Space Complexity: O(1) for storing one temporary variable.

Inserting a Node in Singly Linked List
There are 3 possible cases for inserting a Node in a Singly Linked List.

• Inserting a Node at the beginning of the List
  
  In this case newNode is inserted at the starting of the List. We have to update Next in newNode to point to the previous firstNode and also update Head to point to newNode.
  
  Pseudocode:
  

  firstNode = Head->Next
  
  newNode->Next = firstNode
  
  Head->Next = newNode

  But above pseudocode can be modified to reduce the space complexity by removing the temporary variable usage as shown below
  

  newNode->Next = Head->Next
  
  Head->Next = newNode

  Complexity:
  Time Complexity: O(1)
  Space Complexity: None
  
  Sourcecode:

  void addBeg(int num)
   {
      struct Node *temp;
  
      temp=(struct Node *)malloc(sizeof(struct Node));
      temp->Data = num;
  
      if (Head == NULL)
      {
         //List is Empty
         Head=temp;
         Head->Next=NULL;
      }
      else
      {
         temp->Next=Head;
         Head=temp;
      }
   }

  
  
• Inserting a Node at the End of the List
  
  In order to add the node at the end of the list we have to first traverse to the end of the List. Then we have to update the Next variable in lastNode pointing to newNode.
  
  Pseudocode:

  cur = head
  
  forever:
  
   if cur->Next == NULL
   break
  
  cur->Next = newNode

  Complexity:
  To add a Node at the end of a list whose length is 'n'
  
  Time Complexity: O(n)
  Space Complexity: O(1)
  
  Sourcecode:
  

  void addEnd(int num)
   {
      struct Node *temp1, *temp2;
  
      temp1=(struct Node *)malloc(sizeof(struct Node));
      temp1->Data=num;
  
      // Copying the Head location into another node.
      temp2=Head;
  
      if(Head == NULL)
      {
         // If List is empty we create First Node.
         Head=temp1;
         Head->Next=NULL;
      }
      else
      {
         // Traverse down to end of the list.
         while(temp2->Next != NULL)
         temp2=temp2->Next;
  
         // Append at the end of the list.
         temp1->Next=NULL;
         temp2->Next=temp1;
      }
   }

  
  
• Inserting a Node at position 'p' in the List
  
  To add at the position 'p' we have to traverse the list until we reach the position 'p'. For this case have to maintain two pointers namely prevNode and curNode. Since Singly Linked Lists are uni-directional we have to maintain the information about previous Node in prevNode. Once we reach the position 'p' we have to modify prevNode Next pointing to newNode while newNode points to curNode.
  
  Pseudocode:
  

  curNode = head
  curPos = 1
  
  forever:
  
   if curPos == P || curNode == NULL
   break
  
   prevNode = curNode
   curNode = curNode->Next
   curPos++
  
  if curNode != NULL:
   
   prevNode->Next = newNode
   newNode->Next = curNode

  Complexity:
  Time Complexity: O(n) in worst case.
  Space Complexity: O(3)
  
  Sourcecode:

  void addAt(int num, int loc)
   {
      int i;
      struct Node *temp, *prev_ptr, *cur_ptr;
  
      cur_ptr=Head;
  
      if(loc > (length()+1) || loc <= 0)
      {
         printf("\nInsertion at given location is not possible\n ");
      }
      else
      {
          // If the location is starting of the list
          if (loc == 1)
          {
              addBeg(num);
          }
          else
          {
              for(i=1;i<loc;i++)
              {
                  prev_ptr=cur_ptr;   
                  cur_ptr=cur_ptr->Next;
              }
  
              temp=(struct Node *)malloc(sizeof(struct Node));
              temp->Data=num;
  
              prev_ptr->Next=temp;
              temp->Next=cur_ptr;
          }
      }
   }
  
   // Counting number of elements in the List
  
   int length()
   {
      struct Node *cur_ptr;
      int count=0;
  
      cur_ptr=Head;
  
      while(cur_ptr != NULL)
      {
         cur_ptr=cur_ptr->Next;
         count++;
      }
      return(count);
   }

Next Article: Deleting a Node from a Singly Linked List