Loading lesson path
Concept visual
Start at both ends
Basic things we can do with linked lists are:
For simplicity, singly linked lists will be used to explain these operations below.
Traversing a linked list means to go through the linked list by following the links from one node to the next. Traversal of linked lists is typically done to search for a specific node, and read or modify the node's content, remove the node, or insert a node right before or after that node. To traverse a singly linked list, we start with the first node in the list, the head node, and follow that node's next link, and the next node's next link and so on, until the next address is null, like in the animation below:
next 11 next
next
next
next null
The code below prints out the node values as it traverses along the linked list, in the same way as the animation above.
Traversal of a singly linked list in Python: class Node:
def __init__(self, data):Formula
self.data = data self.next = Nonedef traverseAndPrint(head):Formula
currentNode = head while currentNode:print(currentNode.data, end=" -> ")
currentNode = currentNode.next print("null")Formula
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)Formula
node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5traverseAndPrint(node1) Find The Lowest Value in a Linked List Let's find the lowest value in a singly linked list by traversing it and checking each value. Finding the lowest value in a linked list is very similar to how we found the lowest value in an array, except that we need to follow the next link to get to the next node. This is how finding the lowest value in a linked list works in principle:
next 11 next
next
next
next null
To find the lowest value we need to traverse the list like in the previous code. But in addition to traversing the list, we must also update the current lowest value when we find a node with a lower value. In the code below, the algorithm to find the lowest value is moved into a function called findLowestValue.
Finding the lowest value in a singly linked list in Python: class Node:
def __init__(self, data):Formula
self.data = data self.next = Nonedef findLowestValue(head):Formula
minValue = head.data currentNode = head.next while currentNode:
if currentNode.data < minValue:minValue = currentNode.data currentNode = currentNode.next return minValueFormula
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)Formula
node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5print("The lowest value in the linked list is:", findLowestValue(node1))The marked lines above is the core of the algorithm. The initial lowest value is set to be the value of the first node. Then, if a lower value is found, the lowest value variable is udated.
In this case we have the link (or pointer or address) to a node that we want to delete. It is important to connect the nodes on each side of the node before deleting it, so that the linked list is not broken. So before deleting the node, we need to get the next pointer from the previous node, and connect the previous node to the new next node before deleting the node in between. In a singly linked list, like we have here, to get the next pointer from the previous node we actually need traverse the list from the start, because there is no way to go backwards from the node we want to delete. The simulation below shows the node we want to delete, and how the list must be traversed first to connect the list properly before deleting the node without breaking the linked list.
next 11 next
next
next
next null
Also, it is a good idea to first connect next pointer to the node after the node we want to delete, before we delete it. This is to avoid a 'dangling' pointer, a pointer that points to nothing, even if it is just for a brief moment. In the code below, the algorithm to delete a node is moved into a function called deleteSpecificNode.
Deleting a specific node in a singly linked list in Python: class Node:
def __init__(self, data):Formula
self.data = data self.next = Nonedef traverseAndPrint(head):Formula
currentNode = head while currentNode:print(currentNode.data, end=" -> ")
currentNode = currentNode.next print("null")def deleteSpecificNode(head, nodeToDelete):if head == nodeToDelete:
return head.nextFormula
currentNode = head while currentNode.next and currentNode.next != nodeToDelete:
currentNode = currentNode.nextif currentNode.next is None:
return headFormula
currentNode.next = currentNode.next.nextreturn headFormula
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)Formula
node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5print("Before deletion:")
traverseAndPrint(node1)Formula
# Delete node4 node1 = deleteSpecificNode(node1, node4)print("\nAfter deletion:")
traverseAndPrint(node1)
In the deleteSpecificNode function above, the return value is the new head of the linked list. So for example, if the node to be deleted is the first node, the new head returned will be the next node.Inserting a node into a linked list is very similar to deleting a node, because in both cases we need to take care of the next pointers to make sure we do not break the linked list. To insert a node in a linked list we first need to create the node, and then at the position where we insert it, we need to adjust the pointers so that the previous node points to the new node, and the new node points to the correct next node. The simulation below shows how the links are adjusted when inserting a new node.
next 97 next
next
next
next null
Inserting a node in a singly linked list in Python: class Node:
def __init__(self, data):Formula
self.data = data self.next = Nonedef traverseAndPrint(head):Formula
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 newNodeFormula
currentNode = head for _ in range(position - 2):
if currentNode is None:
break currentNode = currentNode.nextnewNode.next = currentNode.next currentNode.next = newNode return headFormula
node1 = Node(7)
node2 = Node(3)
node3 = Node(2)
node4 = Node(9)Formula
node1.next = node2 node2.next = node3 node3.next = node4print("Original list:")
traverseAndPrint(node1)Formula
# Insert a new node with value 97 at position 2 newNode = Node(97)
node1 = insertNodeAtPosition(node1, newNode, 2)print("\nAfter insertion:")
traverseAndPrint(node1)
In the insertNodeAtPosition function above, the return value is the new head of the linked list. So for example, if the node is inserted at the start of the linked list, the new head returned will be the new node.