How many operations performed on a singly linked list?

Types of Linked List and Operation on Linked List

In the previous blog, we have seen the structure and properties of a Linked List. In this blog, we will discuss the types of a linked list and basic operations that can be performed on a linked list.

Table of Contents Show

Types of Linked List and Operation on Linked List
Linked List
Linked List Operations: Traverse, Insert and Delete
Things to Remember about Linked List
Graphical Depiction of Node
Basic Operations on Singly Linked Lists
Data Structure and Algorithms - Linked List
What is a singly linked list?

Types of Linked List

Following are the types of linked list

Singly Linked List.
Doubly Linked List.
Circular Linked List.

Singly Linked List

A Singly-linked list is a collection of nodes linked together in a sequential way where each node of the singly linked list contains a data field and an address field that contains the reference of the next node.

The structure of the node in the Singly Linked List is

class Node { int data // variable to store the data of the node Node next // variable to store the address of the next node }

The nodes are connected to each other in this form where the value of the next variable of the last node is NULL i.e. next = NULL, which indicates the end of the linked list.

Doubly Linked List

A Doubly Linked List contains an extra memory to store the address of the previous node, together with the address of the next node and data which are there in the singly linked list. So, here we are storing the address of the next as well as the previous nodes.

The following is the structure of the node in the Doubly Linked List(DLL):

class DLLNode { int val // variable to store the data of the node DLLNode prev // variable to store the address of the previous node DLLNode next // variable to store the address of the next node }

The nodes are connected to each other in this form where the first node has prev = NULL and the last node has next = NULL.

Advantages over Singly Linked List-

It can be traversed both forward and backward direction.
The delete operation is more efficient if the node to be deleted is given. (Think! you will get the answer in the second half of this blog)
The insert operation is more efficient if the node is given before which insertion should take place. (Think!)

Disadvantages over Singly Linked List-

It will require more space as each node has an extra memory to store the address of the previous node.
The number of modification increase while doing various operations like insertion, deletion, etc.

Circular Linked List

A circular linked list is either a singly or doubly linked list in which there are no NULL values. Here, we can implement the Circular Linked List by making the use of Singly or Doubly Linked List. In the case of a singly linked list, the next of the last node contains the address of the first node and in case of a doubly-linked list, the next of last node contains the address of the first node and prev of the first node contains the address of the last node.

Advantages of a Circular linked list

The list can be traversed from any node.
Circular lists are the required data structure when we want a list to be accessed in a circle or loop.
We can easily traverse to its previous node in a circular linked list, which is not possible in a singly linked list. (Think!)

Disadvantages of Circular linked list

If not traversed carefully, then we could end up in an infinite loop because here we don't have any NULL value to stop the traversal.
Operations in a circular linked list are complex as compared to a singly linked list and doubly linked list like reversing a circular linked list, etc.

Basic Operations on Linked List

Traversal: To traverse all the nodes one after another.
Insertion: To add a node at the given position.
Deletion: To delete a node.
Searching: To search an element(s) by value.
Updating: To update a node.
Sorting: To arrange nodes in a linked list in a specific order.
Merging: To merge two linked lists into one.

We will see the various implementation of these operations on a singly linked list.

Following is the structure of the node in a linked list:

class Node{ int data // variable containing the data of the node Node next // variable containing the address of next node }

Linked List Traversal

The idea here is to step through the list from beginning to end. For example, we may want to print the list or search for a specific node in the list.

The algorithm for traversing a list

Start with the head of the list. Access the content of the head node if it is not null.
Then go to the next node(if exists) and access the node information
Continue until no more nodes (that is, you have reached the null node)

void traverseLL(Node head) { while(head != NULL) { print(head.data) head = head.next } }

Linked List node Insertion

There can be three cases that will occur when we are inserting a node in a linked list.

Insertion at the beginning
Insertion at the end. (Append)
Insertion after a given node

Insertion at the beginning

Since there is no need to find the end of the list. If the list is empty, we make the new node as the head of the list. Otherwise, we we have to connect the new node to the current head of the list and make the new node, the head of the list.

// function is returning the head of the singly linked-list Node insertAtBegin(Node head, int val) { newNode = new Node(val) // creating new node of linked list if(head == NULL) // check if linked list is empty return newNode else // inserting the node at the beginning { newNode.next = head return newNode } }

Insertion at end

We will traverse the list until we find the last node. Then we insert the new node to the end of the list. Note that we have to consider special cases such as list being empty.

In case of a list being empty, we will return the updated head of the linked list because in this case, the inserted node is the first as well as the last node of the linked list.

// the function is returning the head of the singly linked list Node insertAtEnd(Node head, int val) { if( head == NULL ) // handing the special case { newNode = new Node(val) head = newNode return head } Node temp = head // traversing the list to get the last node while( temp.next != NULL ) { temp = temp.next } newNode = new Node(val) temp.next = newNode return head }

Insertion after a given node

We are given the reference to a node, and the new node is inserted after the given node.

void insertAfter(Node prevNode, int val) { newNode = new Node(val) newNode.next = prevNode.next prevNode.next = newNode }

NOTE: If the address of the prevNode is not given, then you can traverse to that node by finding the data value.

Linked List node Deletion

To delete a node from a linked list, we need to do these steps

Find the previous node of the node to be deleted.
Change the next pointer of the previous node
Free the memory of the deleted node.

In the deletion, there is a special case in which the first node is deleted. In this, we need to update the head of the linked list.

// this function will return the head of the linked list Node deleteLL(Node head, Node del) { if(head == del) // if the node to be deleted is the head node { return head.next // special case for the first Node } Node temp = head while( temp.next != NULL ) { if(temp.next == del) // finding the node to be deleted { temp.next = temp.next.next delete del // free the memory of that Node return head } temp = temp.next } return head // if no node matches in the Linked List }

Linked List node Searching

To search any value in the linked list, we can traverse the linked list and compares the value present in the node.

bool searchLL(Node head, int val) { Node temp = head // creating a temp variable pointing to the head of the linked list while( temp != NULL) // traversing the list { if( temp.data == val ) return true temp = temp.next } return false }

Linked List node Updation

To update the value of the node, we just need to set the data part to the new value.

Below is the implementation in which we had to update the value of the first node in which data is equal to val and we have to set it to newVal.

void updateLL(Node head, int val, int newVal) { Node temp = head while(temp != NULL) { if( temp.data == val) { temp.data = newVal return } temp = temp.next } }

Linked List

Linked List can be defined as collection of objects called nodes that are randomly stored in the memory.
A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory.
The last node of the list contains pointer to the null.

Linked List Operations: Traverse, Insert and Delete

In this tutorial, you will learn different operations on a linked list. Also, you will find implementation of linked list operations in C/C++, Python and Java.

There are various linked list operations that allow us to perform different actions on linked lists. For example, the insertion operation adds a new element to the linked list.

Here's a list of basic linked list operations that we will cover in this article.

Traversal - access each element of the linked list
Insertion - adds a new element to the linked list
Deletion - removes the existing elements
Search - find a node in the linked list
Sort - sort the nodes of the linked list

Before you learn about linked list operations in detail, make sure to know about Linked List first.

Things to Remember about Linked List

head points to the first node of the linked list
next pointer of the last node is NULL, so if the next current node is NULL, we have reached the end of the linked list.

In all of the examples, we will assume that the linked list has three nodes 1 --->2 --->3 with node structure as below:

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

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:

Node of Linked List

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

Example of SLL

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.

Inserting at the start of a list

Inserting at the end of the list

Inserting at a specific point in a list

Inserting at the Start of a List

Insertion at Start of Singly Linked 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

Insertion at End of Singly Linked 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

Insertion at Specific Point of Singly Linked 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:

Delete from the start of the list

Delete from the end of the list

Delete a Particular Node

Delete from the Start of the List

Deleting First Node of Singly Linked 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

Deleting End Node of Singly Linked 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

Deleting Particular Node of Singly Linked List

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

Singly Linked Lists in C, Java and Python.

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).

Facebook

Prev Article Next Article

Data Structure and Algorithms - Linked List

What is a singly linked list?

A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail).

Each element in a linked list is called a node. A single node contains data and a pointer to the next node which helps in maintaining the structure of the list.

The first node is called the head; it points to the first node of the list and helps us access every other element in the list. The last node, also sometimes called the tail, points to NULL which helps us in determining when the list ends.