Singly Linked List in Data Structure

We utilize a linked list data structure to organize data when we have an unknown amount of data values to work with. A linked list is a linear data structure that consists of a succession of elements each of which is connected to the next member in the sequence. In a linked list, each entry is referred to as a “Node.” We’ll look at the first type of linked list, which is a single linked list. A single linked list is a form of a unidirectional linked list that may only be traversed in one way, from head to final node.

Graphical Depiction of Node

A node is a name for each element in a linked list. A single node includes data as well as a pointer to the next node, which aids in the list’s structure. The head is the first node in the list; it points to the first node in the list and allows us to access all of the other elements in the list. The last node, commonly known as the tail, refers to NULL, which allows us to determine when the list comes to an end. The following is a graphical depiction of a node in a single linked list:

Let’s see the example of a graphical depiction of a singly linked list:

Basic Operations on Singly Linked Lists

On a Singly Linked List, the following operations are done:

• Insertion

• Deletion

• Display

To perform the above-mentioned operations, we must first create an empty list by using the following procedure:

Step 1: Ensure that all of the program’s header files are included.

Step 2: Create a list of all user-defined functions.

Step 3: Create a Node structure with two data members.

Step 4: Create a ‘head’ for the Node pointer and set it to NULL.

Step 5: Implement the main method by showing an operations menu and calling the appropriate functions in the main method to conduct the user’s chosen operation.

Insertion

After creating the empty list, we can perform an insertion operation on the list. The insertion operation can be done in three different ways in a single linked list.

1. Inserting at the start of a list

2. Inserting at the end of the list

3. Inserting at a specific point in a list

Inserting at the Start of a List

The procedures below can be used to add a new node at the start of singly linked list:

Step 1: Generate a newNode using the supplied value.

Step 2: Verify that the list is empty (head == NULL).

Step 3: Set newNode→next = NULL and head = newNode if it’s empty.

Step 4: Set newNode→next = head and head = newNode if it is not empty.

Inserting at the End of the List

The procedures below can be used to add a new node to the end of a single linked list:

Step 1: Make a newNode with the specified value and set newNode → next to NULL.

Step 2: Determine whether or not the list is empty (head == NULL).

Step 3: Set head = newNode if it is empty.

Step 4: If it’s not empty, create a temp node pointer and initialize it with head.

Step 5: Continue shifting the temp to the next node in the list until it reaches the last node (or until temp→next equals NULL).

Step 6: Set temp→next = newNode.

Inserting at a Specific Point in a List

To insert a new node after a node in a single linked list, apply the instructions below:

Step 1: Construct a newNode using the supplied value.

Step 2: Verify that the list is empty (head == NULL).

Step 3: Set newNode next = NULL and head = newNode if it’s empty.

Step 4: If it’s not empty, create a temp node pointer and initialize it with head.

Step 5: Continue moving the temp to its next node until it reaches the node where we want to put the newNode (until temp1→data equals location, where location is the node value).

Step 6: Check if the temp has reached the last node or not at regular intervals. If you get to the last node, the message ‘Given node is not found in the list! Insertion is not possible!’ will appear and the function is terminated. If not, increment the temp to the next node.

Step 7: Finally, set ‘newNode→next = temp→next’ and ‘temp→next = newNode’ to their respective values.

Deletion

The deletion operation in a singly linked list may be done in three different ways. The following are the details:

1. Delete from the start of the list

2. Delete from the end of the list

3. Delete a Particular Node

Delete from the Start of the List

To delete a node from the single linked list’s beginning, apply the procedures below:

Step 1: Check to see if the list is empty (head == NULL).

Step 2: If the list is empty, display the message ‘List is Empty! Deletion is not feasible!’, and the function is terminated.

Step 3: If it is not empty, create a temp Node reference and initialize it with head.

Step 4: Verify that the list only has one node (temp next == NULL).

Step 5: If TRUE, change head to NULL and remove temp (Setting Empty list conditions).

Step 6: If the answer is FALSE, set head = temp next and delete temp.

Delete from the End of the List

The procedures below can be used to remove a node from the single linked list’s end:

Step 1: Check to see if the list is empty (head == NULL).

Step 2: If the list is empty, display the message ‘List is Empty! Deletion is not feasible’, and the function is terminated.

Step 3: If it’s not empty, create two Node pointers, ‘temp1’ and ‘temp2,’ and set ‘temp1’ to head.

Step 4: Verify that the list only includes one Node (temp1 next == NULL).

Step 5: Determine if it is TRUE. Then remove temp1 and set head = NULL. Finally, the function is terminated. (Setting the criterion for an empty list).

Step 6: If the answer is FALSE. Set ‘temp2 = temp1’and then shift temp1 to the next node. Continue in this manner until you reach the last node on the list. (until next temp1 == NULL).

Step 7: Finally, remove temp1 and set temp2 next = NULL.

Delete a Particular Node

The steps below can be used to remove a specific node from the single linked list:

Step 1: Check to see if the list is empty (head == NULL).

Step 2: If the list is empty, display the message ‘List is Empty!!!’ Deletion is not possible’, and the function is terminated.

Step 3: If it’s not empty, create two Node pointers, ‘temp1’ and ‘temp2,’ and set ‘temp1’ to head.

Step 4: Continue dragging the temp1 until it approaches the last node or the particular node to be deleted. And before moving ‘temp1’ to the next node, always set ‘temp2 = temp1’.

Step 5: Once you’re at the last node, the message “Given node not found in the list! Deletion Not Pssible” appears. Finally, the function is terminated.

Step 6: If you’ve reached the particular node which you want to delete, check to see if the list has only one node.

Step 7: Set head = NULL and remove temp1 (free(temp1)) if list contains just one node and that is the node to be deleted.

Step 8: Check if temp1 is the first node in the list (temp1 == head) if the list has several nodes.

Step 9: If temp1 is the initial node, remove temp1 and shift the head to the next node (head = head→next).

Step 10: If temp1 isn’t the first node in the list (temp1→next == NULL), see if it’s the final one.

Step 11: Set temp2→next = NULL and remove temp1 (free(temp1)) if temp1 is the final node.

Step 12: Set temp2→next = temp1 →next and remove temp1 (free(temp1)) if temp1 is not the first or last node.

Display

The components of a single linked list can be displayed using the methods below:

Step 1: Determine whether or not the list is empty (head == NULL).

Step 2: If the list is empty, show “List is Empty!!!” and exit the method.

Step 3: If it is not empty, create a ‘temp’ Node pointer and initialize it with head.

Step 4: Continue to display temp →data with an arrow (—>) until the temp reaches the last node.

Step 5: Finally, show temp →data with an arrow pointing to NULL (temp →data —> NULL).