Earlier I demonstrated how to search a linked list using linear search, which is a popular technical interview question and programming challenge to test one's knowledge of computer science data structures and algorithms. Another popular coding challenge is to insert a new value in a linked list, which is what I would like to demonstrate in this tutorial. However, let's add a twist. Let's insert integer values so that the linked list maintains the list of integers in ascending numerical value.
Inserting New Nodes in a Linked List
As mentioned in the previous article, linked lists are typically comprised of a chain of nodes, with each node containing a value and a link to the next node in the chain. Let's create a basic Node class that holds a value and a pointer to the next node in the linked list. For simplicity, the nodes will hold an integer value in this case, but a linked list can hold any type of data.
class Node(object):
def __init__(self, value: int, next_node: "Node" = None):
self.value = value
self.next = next_node
def __repr__(self):
return 'Node <{}>'.format(self.value)
Now that we have a Node class, we need to create a function that inserts a value in a chain of nodes (linked list) such that the chain maintains the integer values in numerical order. This adds a bit of a twist to what you might find in a technical interview question or programming challenge. We can't just insert the value at the head of the linked list in O(1) and be done. We need to loop through the current values in the linked list in O(n) and compare each node value to the new value being inserted into the linked list. Once we find the location to add the new value, we can insert it in O(1) and return the new linked list.
When searching a linked list in the previous tutorial, we only kept track of the current node as we looped through the linked list. When inserting a node, however, we want to keep track of both the previous node and the current node, because we will be inserting the new value between these two nodes. The next pointer of the previous node will be set to the new node and the next pointer of the new node will be set to the current node.
Here is one solution in Python to insert a new value into a linked list while maintaining the integer values in ascending order.
def insert(head: Node, value: int) -> Node:
"""
Inserts value in linked list in ascending order.
:param head: Head Node of the linked list.
:param value: Value to insert in linked list.
:return: New head of the linked list.
"""
new_node = Node(value)
if head is None or value < head.value:
new_node.next = head
return new_node
previous_node, current_node = head, head.next
while current_node is not None and current_node.value < value:
previous_node = current_node
current_node = current_node.next
previous_node.next = new_node
new_node.next = current_node
return head
Unit Testing Helper Function
We have our algorithm, but let's create a helper function to convert the linked list to a Python list so we can easily test this function using assert statements. This is only for testing purposes, but it's a great exercise on retrieving the values of a linked list.
def convert_to_list(head: Node) -> list:
"""
Converts a linked list to a list.
:param head: Head Node of the linked list.
:return: list
"""
a_list = []
current_node = head
while current_node is not None:
a_list.append(current_node.value)
current_node = current_node.next
return a_list
Automated Tests
It's always good to have automated tests so we know our code works. This will improve maintainability in case we refactor it later. Rather than using doctests or unittest, I created a script that performs a few inserts and evaluates the new linked list to make sure the new insert function works as expected.
if __name__ == '__main__':
linked_list = Node(5, Node(10, Node(15, Node(20, Node(25)))))
linked_list = insert(linked_list, 3)
assert (convert_to_list(linked_list) == [3, 5, 10, 15, 20, 25])
linked_list = insert(linked_list, 30)
assert (convert_to_list(linked_list) == [3, 5, 10, 15, 20, 25, 30])
linked_list = insert(linked_list, 5)
assert (convert_to_list(linked_list) == [3, 5, 5, 10, 15, 20, 25, 30])
linked_list = insert(linked_list, 4)
assert (convert_to_list(linked_list) == [3, 4, 5, 5, 10, 15, 20, 25, 30])
linked_list = insert(linked_list, 6)
assert (convert_to_list(linked_list) == [3, 4, 5, 5, 6, 10, 15, 20, 25, 30])
linked_list = insert(linked_list, 17)
assert (convert_to_list(linked_list) == [3, 4, 5, 5, 6, 10, 15, 17, 20, 25, 30])
linked_list = insert(linked_list, 12)
assert (convert_to_list(linked_list) == [3, 4, 5, 5, 6, 10, 12, 15, 17, 20, 25, 30])
linked_list = insert(linked_list, 32)
assert (convert_to_list(linked_list) == [3, 4, 5, 5, 6, 10, 12, 15, 17, 20, 25, 30, 32])
When you run the code it will silently quit if all is well, but raise an error if the code fails. I called my module main.py and can run it using python main.py.
Conclusion
I will continue to write tutorials on linked lists as they are a fundamental data structure for use in computer science. Much of my code will be written in Python as it is a very popular computer science programmin language and intuitive to those new to programming. However, as time permits, I will add solutions in other programming languages.
