Singly linked list: A Good Point to Start With

Introduction

A singly linked list is a type of linked list data structure which is used to store a collection of elements or items. It consists of a sequence of nodes where each node contains two parts: first part consists of the values need to be stored, and second part is a pointer that points to the next node in the list. In other words we can say that the singly linked list is the simplest form of a Linked List.

The first node in the list is called the head, and the last node in the list is called the tail. Each node in the list only points to the next node, and the tail node points to NULL, indicating the end of the list.

Each node of the linked list is allocated memory from heap section. Then the data part of the node is updated, and the next pointer is marked to NULL. When we want to delete the node then we need to free the memory of this node otherwise it will lead to memory leaking.

As we had covered in Linked List post, here also it has mainly 3 operations.

• Traversing the whole linked list
• Inserting a node to the linked list
• Deleting a node from the linked list

Traversing a Singly Linked List

Traversing a Singly Linked List means accessing & visiting each and every node of the linked list starting from the head node and moving towards the end of the list. To traverse a singly linked list, we start from the Head Node. Then we follow the next pointer of each node until we reach the end of the list. If the next pointer is NULL then it means that we are at the end of the list. This node is known as tail of the linked list. At each node, we can access the data stored in that node and perform any required operations.

The basic algorithm to traverse a singly linked list is:

1. Start at the head node.
2. While the current node is not null, do the following: a. Process the data stored in the current node. b. Move to the next node by following the next pointer.
3. End of the list is reached.

Let us see this with an example also. In below code we are traversing the singly list and printing the values of each node.

In this example we have started from the head of the linked list and then moved to next node using the “next” pointer. “next” pointer holds the address of next node. If “next” is NULL then it means we are at the end of the Singly linked list.

Insert a node in a singly Linked List

In a singly linked list, a new node can be added at the beginning, end, or at a given specific position in the list. Let us discuss each of these one by one. Before moving ahead, please pay attention to below picture.

Insert a node at beginning

Insertion at the beginning of the singly linked list involves creating a new node and then making it the new head of the list. This is done by setting the “next” pointer of the new node to the current head of the list, and then updating the head pointer to point to the new node. Below is the code for reference

Insert a node at end

Insertion at the end of the list involves creating a new node and attaching it to the end of the list. This is done by traversing the list to find the last node, and then setting the next pointer of the last node to the new node.

Insert a node at a given position

Insertion at a specific position in the list involves creating a new node and inserting it between two existing nodes. This is done by traversing the list to find the node before the desired position, setting its next pointer to the new node, and setting the next pointer of the new node to the node that was originally at the desired position.

Deleting a node from a single Linked List

Deletion in a singly linked list involves removing a node from the list. There are three possible scenarios when deleting a node from a singly linked list: Lets discuss them one by one but please first pay attention to below picture

Deleting a Node from beginning

When we remove a node from the head of the linked list then we update the next pointer of the head node to point to the second node in the list, and then free the memory allocated to the node being deleted. Lets have a look at the C code for this purpose where we are deleting the head of the LL.

Deleting a Node from end

When deleting the last node, we first find the node that is second last in the linked list. If the node’s next->next is NULL then it means that node is second last. We need to free the node->next and mark it NULL. Lets have a look at below example which itself is self explanatory

Deleting a Node from a given position

When deleting an intermediate node, we first find the node that precedes the node being delete, after that we need to update its next pointer to point to the node that follows the node being deleted as shown in below example.

Deleting the whole Linked List

Sometimes we need to delete the complete linked list. to do so, we need to start from head and keep of freeing the node until we reach at the end of the linked list. Let have a look at below example that delete the complete singly linked list.

Advantages of Single Linked List:

Dynamic Size: The size of a singly linked list can be easily modified at runtime by adding or removing nodes. This makes it a dynamic data structure, which is particularly useful when the number of elements in the list is not known in advance.

Efficient Insertion and Deletion: Inserting or deleting a node from a singly linked list is an efficient operation, particularly when compared to other linear data structures such as arrays. This is because only a few pointers need to be updated, and no data needs to be shifted around in memory.

Efficient Memory Usage: A singly linked list uses memory efficiently as each node only requires memory for storing the element and the address of the next node in the list.

Easy to Implement: The implementation of a singly linked list is relatively simple and straightforward, making it a good choice for situations where simplicity is preferred over performance.

Disadvantages of Single Linked List:

Sequential Access: Unlike arrays, singly linked lists do not provide constant time random access to elements. In order to access an element at a particular index, we need to traverse the list from the beginning to the desired index.

No Backward Traversal: A singly linked list does not allow backward traversal. This means that we cannot iterate over the list in reverse order, and we cannot access the previous node of a given node.

Extra Memory for Pointers: Each node in a singly linked list requires an additional pointer to store the address of the next node in the list. This can result in extra memory usage compared to other data structures such as arrays.

Not Cache Friendly: Traversing a singly linked list can be less cache-friendly than traversing an array. This is because the nodes in a singly linked list may not be stored in contiguous memory locations, causing cache misses and reducing performance.

References

• Linked list – Wikipedia
• Linked List: Zero to Hero