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.

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