DSA Linked Lists Operations
Linked List Operations
Using linked lists, we can execute the following basic tasks:
1.Traversal
2.Remove a node
3.Insert a node
4.Sort
The next explanations of these processes will make use of singly linked lists for convenience.
Traversal of a Linked List
Following the links between one node and the next to navigate a linked list is known as traversing the list.
Typically, traversing linked lists is used to look for a particular node, read or edit its contents, remove it, or add a node that is immediately before or after it.
When traversing a singly linked list, we begin at the head node, the first node in the list, and move on to the next node, and the one after that, and so on, until the next address is null, as shown in the animation below:
===== Example MUKAVU =====
The code below prints out the node values as it traverses along the linked list, in the same way as the animation above.
Example
Python traversal of a singly linked list:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverseAndPrint(head):
currentNode = head
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
traverseAndPrint(node1)
Find The Lowest Value in a Linked List
Let’s traverse a singly linked list and check each number to determine which one is the lowest.
Similar to finding the lowest value in an array, finding the lowest value in a linked list requires following the next link to reach the next node.
In theory, locating the lowest value in a linked list operates as follows:
==== Example MUKAVU =====
We must iterate through the list, just as in the previous code, in order to find the lowest value. When we locate a node with a lower value, we must not only traverse the list but also update the existing lowest value.
The algorithm for locating the lowest value has been placed into a function named findLowestValue in the code below.
Example
Python code for locating the lowest value in a single linked list:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def findLowestValue(head):
minValue = head.data
currentNode = head.next
while currentNode:
if currentNode.data < minValue:
minValue = currentNode.data
currentNode = currentNode.next
return minValue
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
print("The lowest value in the linked list is:", findLowestValue(node1))
Delete a Node in a Linked List
Here, we have the URL, pointer, or link to a node that we wish to remove.
In order to keep the linked list intact, it is crucial to connect the nodes on either side of the removed node.
Therefore, we must retrieve the next pointer from the previous node and link it to the new next node before removing the node that comes in between.
Since there is no way to travel backwards from the node we wish to delete, in a singly linked list like the one we have here, in order to acquire the next reference from the previous node, we must actually traverse the list from the beginning.
The simulation below illustrates the node we wish to remove as well as how the list needs to be properly scanned in order to connect the list before the node can be removed without causing the linked list to break.
==== Example MUKAVU =====
Prior to deleting the node we wish to destroy, it is a good idea to attach the next pointer to the node. This is to prevent a “dangling” pointer—that is, a pointer that, even for a short while, points to nothing.
The deleteSpecificNode function in the code below houses the algorithm for deleting a node.
Example
In Python, removing a particular node from a singly linked list:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverseAndPrint(head):
currentNode = head
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
def deleteSpecificNode(head, nodeToDelete):
if head == nodeToDelete:
return head.next
currentNode = head
while currentNode.next and currentNode.next != nodeToDelete:
currentNode = currentNode.next
if currentNode.next is None:
return head
currentNode.next = currentNode.next.next
return head
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
print("Before deletion:")
traverseAndPrint(node1)
# Delete node4
node1 = deleteSpecificNode(node1, node4)
print("\nAfter deletion:")
traverseAndPrint(node1)
The new head of the linked list is the return result of the aforementioned deleteSpecificNode method. Thus, the new head that is returned will be the following node if, for instance, the node that has to be destroyed is the first node.
Insert a Node in a Linked List
Because we must watch out for the following pointers in both situations to ensure that we do not break the linked list, adding a node to a linked list and removing a node are very similar operations.
In order to add a node to a linked list, we must first build it. Then, at the node’s placement, we must modify the pointers such that the new node points to the appropriate next node and the previous node points to the new node.
The simulation that follows demonstrates how the links are changed when a new node is inserted.
===== Example MUKAVU =====
1.New node is created
2.Node 1 is linked to new node
3.New node is linked to next node
Example
In Python, adding a node to a singly linked list:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverseAndPrint(head):
currentNode = head
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
def insertNodeAtPosition(head, newNode, position):
if position == 1:
newNode.next = head
return newNode
currentNode = head
for _ in range(position - 2):
if currentNode is None:
break
currentNode = currentNode.next
newNode.next = currentNode.next
currentNode.next = newNode
return head
node1 = Node(7)
node2 = Node(3)
node3 = Node(2)
node4 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
print("Original list:")
traverseAndPrint(node1)
# Insert a new node with value 97 at position 2
newNode = Node(97)
node1 = insertNodeAtPosition(node1, newNode, 2)
print("\nAfter insertion:")
traverseAndPrint(node1)
The new head of the linked list is the return result of the insertNodeAtPosition function mentioned above. The new head that is returned will be the new node, for instance, if the node is added at the beginning of the linked list.
Other Linked Lists Operations
Only the three fundamental linked list operations—trench (also known as search), node deletion, and node insertion—have been discussed thus far.
Linked lists can be used for many different tasks, such as sorting, among many more.
Numerous sorting methods were previously discussed in the course, and many of them could also be applied to linked lists. Consider selection sort as an illustration. Using selection sort, we identify the lowest value, take it out, and add it at the start. I assume we could also accomplish the same thing with a linked list. We have just learned how to add, remove, and search through a linked list of nodes.
Note: Because sorting algorithms like Counting Sort, Radix Sort, and Quicksort use indexes to modify array members based on their position directly, we are unable to sort linked lists using these algorithms.
Linked Lists vs Arrays
In contrast to arrays, linked lists have the following important properties:
1.Unlike arrays, which must relocate the entire list into a bigger memory space when the fixed memory space fills up, linked lists do not have this requirement because they are not assigned to a specific size in memory.
2.Linked list nodes do not need to be moved up or down in memory when nodes are added or removed since they are not arranged in a continuous manner in memory.
3.In order to store one or more linkages to other nodes, linked list nodes need more memory. Since array elements don’t have links to other items, they don’t require a lot of memory.
4.Because computer languages offer superior built-in support for arrays, linked list operations are typically more complex to implement and involve more lines of code than equivalent array operations.
5.To locate a node at a particular location, we must iterate through a linked list; however, arrays allow us to retrieve an element directly by writing myArray[5].
Note: Although we do not need to write code to handle when an array fills up its memory space or to shift elements up or down in memory when an element is removed or inserted, these things still happen in the background when using arrays in programming languages like Python or Java and can cause issues in time-sensitive applications.
Time Complexity of Linked Lists Operations
In this section, we’ll talk about the time complexity of linked list operations and contrast them with the array methods’ time complexity from earlier in the course.
Keep in mind that, depending on a big amount of data, time complexity only provides an estimate of the number of operations the method will require. n, and does not specify how long a particular algorithmic implementation takes.
This indicates that even though it’s claimed that the time complexity of linear search for arrays is equal to that of linked lists:
O (n) implies that they do not require the same amount of time. The precise amount of time an algorithm takes to execute relies on a number of factors, including the computer hardware, programming language, and the time disparities between operations on linked lists and arrays.
Similar to arrays, linked lists can be searched using linear search.
From the head node, a list of unsorted values is scanned until the node with the desired value is located. Complexity of time is (n)..
Because the technique for binary search relies on skipping straight to distinct array members, which is not allowed with linked lists, binary search is not feasible for linked lists.
The time complexities of sorting algorithms are the same as those of arrays, and they were covered previously in this course. However, keep in mind that sorting algorithms that rely on using an index to directly access an array element will not function on linked lists.
