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


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.

Posted by David Hayden

David Hayden is a freelance web developer. In his spare time he tutors students on a wide variety of computer science topics and programming languages. You can find him on twitter as @koderdojo.

Related Posts: