Singly Linked List Theory

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.


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. 

1. struct Node
2. {
3. int Data;
4. struct Node *Next;
5. };

Variable Data holds the data in the Node (It can be a pointer variable pointing to the dynamically allocated memory) while Nextholds the address to the next Node in the 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 Headpoints to the first Node in the List.

Pseudocode:
1. cur = head
2. 
3. forever:
4.
5. if cur == NULL
6. break;
7.
8. 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:

          1. firstNode = Head -> NExt

          2. 

          3. newNode -> Next = firstNode

          4.

          5. Head -> Next = newNode

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

         1. newNode -> Next = Head -> Next

         2. 

         3. Head -> Next = newNode

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

Sourcecode:
1. void addBeg(int num)

2. {

3. struct Node *temp;

4.

5. temp = (struct Node *)malloc(sizeof(struct Node));

6. temp -> Data = num;

7.

8. if (Head == NULL)

9. {

10. //List is Empty

11. Head = temp;

12. Head -> Next = NULL;

13. }

14. else

15. {

16.   temp -> Next = Head;

17.   Head = temp;

18.   }

19. }

• 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:

         1. cur = head

         2. 

         3. forever:

         4.

         5. if cur -> Next ==NULL

         6. break

         7.

         8. 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:

1. void addEnd(int num)

2. {

3. struct Node *temp1, *temp2;

4. 

5. temp1=(struct Node *)malloc(sizeof(struct Node));

6. temp1 -> Data = num;

7.

8. //Copying the Head location into another code.

9. temp2 = Head;

10.

11. if(Head ==NULL)

12. {

13.   // If List is empty we create First Node.

14. Head = temp1;

15. Head -> Next = NULL;

16. }

17. else

18. {

19.    // Traverse down to end of the list.

20.   while(temp2 -> Next !=NULL)

21.   temp2 = temp2 -> Next;

22.

23.   //Append at the end of the list.

24.   temp1 -> Next = NULL;

25.   temp2 -> Next = temp1;

26.   }

27. }

• 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 Nextpointing to newNode while newNode points to curNode.
  
  Pseudocode:

1. curNode = head
2. 
   
3. curPos = 1
4. 
   
5. forever:
6. if curPos == P || curNode == NULL
7. break
8. 
   
9. prevNode = curNode
10. curNode = curNode->Next
11. curPos++
12. 
    
13. if curNode != NULL:
14. prevNode->Next = newNode
15.  newNode->Next = curNode

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

Sourcecode:

1. void addAt(int num, int loc)
2. {
3.    int i;
4.    struct Node *temp, *prev_ptr, *cur_ptr;
5. 
   
6. cur_ptr = Head;
7. if(loc > (length() + 1) || loc < 0)
8. {
9.    printf("\nInsertion at given location is not possible\n");
10.  }
11. else
12. {
13.   // If the location is starting of the list
14.   if(loc == 1)
15.   {
16.     addBeg(num);
17.    }
18.  else
19.  {
20.   for(i=1;i<loc;i++)
21.   {
22.      prev_ptr = cur_ptr;
23.      cur_ptr = cur_ptr -> Next;
24.    }
25. 
    
26.  temp = (struct Node *)malloc(sizeof(struct Node));
27.  temp -> Data = num;
28.  prev_ptr -> Next = temp;
29.  temp -> Next = cur_ptr;
30.  }
31.  }
32. }
33. 
    
34.   //Counting number of elements in the List
35. 
    
36.     int length()
37.     {
38.       struct Node *cur_ptr;
39.       int count = 0;
40. 
    
41.       cur_ptr = Head;
42. 
    
43.       while(cur_ptr != NULL)
44.       {
45.          cur_ptr = cur_ptr -> Next;
46.          count++;
47.       }
48.      return(count);
49.   }