4.8 Singly Linked Lists

Generally “linked list” means asingly linked list. This list consists of a number of nodes in whicheach node has a next pointer to the following element. The link of the last node in the list is NULL, which indicates the end of the list.

Following is a type declaration for a linked list of integers:

				
					

struct ListNode{ 
int data; struct ListNode *next;
};
				
			

Basic Operations on a List

• Traversing the list
• Inserting an item in the list
• Deleting an item from the list

Traversing the Linked List

Let us assume that the head points to the first node of the list. To traverse the list we do the following

• Follow the pointers.
• Display the contents of the nodes (or count) as they are traversed.
• Stop when the next pointer points to NULL.

The List Length() function takes a linked list as input and counts the number of nodes in the list. The function given below can be used for printing the list data with extra print function.

				
					

int ListLength(struct ListNode *head) { struct ListNode *current = head; int count = 0;
while (current != NULL) {
}
count++;
current current-next;
return count;
				
			

Time Complexity: O(n), for scanning the list of size n.
Space Complexity: O(1), for creating a temporary variable

Singly Linked List Insertion

Insertion into a singly-linked list has three cases:

• Inserting a new node before the head (at the beginning)
• Inserting a new node after the tail (at the end of the list)
• Inserting a new node at the middle of the list (random location)

Note: To insert an element in the linked list at some position p, assume that after inserting the element the position of this new node is p.

Inserting a Node in Singly Linked List at the Beginning

In this case, a new node is inserted before the current head node. Only one next pointer needs to be modified (new node’s next pointer) and it can be done in two steps:

• Update the next pointer of new node, to point to the current head.

Inserting a Node in Singly Linked List at the Ending

In this case, we need to modify two next pointers (last nodes next pointer and new nodes next pointer).

• New nodes next pointer points to NULL

Inserting a Node in Singly Linked List at the Middle

Let us assume that we are given a position where we want to insert the new node. In this case also, we need to modify two next pointers.

• If we want to add an element at position 3 then we stop at  position 2. That means we traverse 2 nodes and insert the new node. For simplicity let us assume that the second node is called position node. The new node points to the next node of the position where we want to add this node.

Let us write the code for all three cases. We must update the first element pointer in the calling function, not just in the called function. For this reason we need to send a double pointer. The following code inserts a node in the singly linked list.