Operations on Linked List Data Structure | DSA Tutorials

Operations on Linked List – To perform operations like insertion, deletion, sorting, reversing and searching on the linked list, we need to find the reference to a particular node in a linked list. So today, we are going to learn how we can find the reference to the nodes to perform operations on a linked list.

After completing this tutorial, you can learn

1. Reference to the last node
2. Reference to the second last node
3. Reference to a node with particular info
4. Reference to the predecessor of a node with particular info
5. Reference to a node at a particular position

Operations on Linked List Data Structure

Finding a reference to the last node

As we know, a linked list contains the null or None value at the linked part of the last node of the list. So here is the code to find the reference to the last node of the linked list.

p = self.start
while p.link is not None:
    p = p.link

Note: here we first store the reference of the first node of the list in the p variable, and then we continue to the next using the while loop till the value of the link part of a node is not equal to None.

Finding a reference to the second last node

Here is the Python code to find the reference to the second last node of the list.

p = self.start
while p.link.link is not None:
    p = p.link

Note: here we run the while loop till the value of next to the next link of the node is equal to the null of None.

Finding a reference to a node with particular info

Let’s assume we need to find the node that contains the value x. For example, if we need to find the node that contains the value 30, then here is the Python code to find the node with a particular value.

p = self.start
while p is not None:
    if p.info == x:
        break
    p = p.link

Note: here we run the while loop till the last node of the list. And if we found the value of the node that is equal to the value that we are searching for, then the break statement stops the while loop.

Finding a reference to the predecessor of a node with particular info

Predecessor: predecessor node is the node before the node that contains the particular value. As you see in Figure 4.

Note: here we need to find the reference to the predecessor of the node that contains the value x=30.

Here is the Python code to find the reference to the predecessor of the node with particular info.

p = self.start
while p.link is not None:
    if p.link.info == x:
        break    p = p.link

Here we run the loop till the last node of the linked list, and at every node, we check if the info part of the next to next node is equal to the value x or not. If the value is equal to x, then we break the loop.

Finding a reference to a node at a particular position

Here, we need to find the node at position 3, as you see in Figure 5.

Here is the Python code to find the node at a particular position.

p = self.start
i = 1
while i<k and p is not None:
    p = p.link
    i += 1

Note: here we run the while loop till the value of i is less than k, and the link of that particular node is added to the p variable. And we increment the value of i at every iteration.