Linked Lists are among the most fundamental data structure that represents a sequence of nodes. The first element of the sequence is called the head of the Linked List while the last element corresponds to the tail. Every node in the sequence has a pointer to the next element and optionally a pointer to the previous element. In Singly Linked Lists each node points to only the next node. On the other hand, in Doubly Linked Lists each node points to the next as well as to the previous node. Linked Lists are extremely useful in various scenarios. They are typically preferred over standard arrays when Unlike other general purpose languages, Python does not have a built-in implementation of Linked Lists in its standard library. In today’s article we will explore how to implement a user-defined Linked List class using Python. First, let’s create a user-defined class for individual nodes in a Linked List. This class will be suitable for both Singly or Doubly Linked Lists. Therefore, the instances of this class should be capable for storing the value of the node, the next as well as the previous node. Note that when an instance of a Node has next set to None then it means that it is essentially the tail of the Linked List (either Singly or Doubly). Similarly, in Doubly Linked Lists, when a node has prev set to None then this indicates that the node is the head of the Linked List. Now that we have created a class for the Nodes, we can now create the class for the Linked List itself. As mentioned already, a Linked List has a head, a tail and the nodes pointing to each other. Now in order to add the values provided in the constructor as nodes in the Linked List we need to define a couple of additional methods. The first method called add_node is used to add a single node to the Linked List. Now let’s go through the logic of the method quickly. If the Linked List has no head, then it means it’s empty and therefore the node to be added will be both the head and the tail of the Linked List. If the head is not empty, then we add the newly created Node as the next element of the current tail and finally move the tail to point to the newly created Node. The second method is called add_multiple_nodes which is called in the constructor and in simply calls the add_node method we defined earlier in order to add multiple values as nodes in the Linked List instance. So far, our Linked List class looks like below: Now let’s create an additional method that’d be able to insert a new element but this time in the beginning of the Linked List, i.e. as a head. Now let’s override some special methods in our class that could potentially be useful. Firstly, let’s implement __str__ method so that the string representation of a Linked List object is human readable. For example, when printing out a Linked List with nodes a, b, c, d the output will bea -> b -> c -> d. Secondly, let’s also implement __len__ method that will return the length of our user-defined class, which is essentially the number of nodes included in the sequence. All we need to do is iterate over every node of the sequence until we reach the tail of the Linked List. Finally, let’s ensure that LinkedList class is iterable by implementing __iter__ method. Additionally, we could also create a property called values so that we can access the values of all nodes included in the sequence. The final class looks like below: Now even our Node class can represent nodes included in either of Singly or Doubly Linked Lists, the LinkedList class we defined can only support Singly Linked Lists. This is because when adding nodes, we are not specifying the previous node. To deal with Doubly Linked Lists, we can simply create an additional class that inherits from LinkedList class and overrides the add_node and add_node_as_head methods: The full code containing the three classes we created as part of today’s tutorial is given below as a GitHub Gist. The full code containing Node, LinkedList and DoublyLinkedList Python classes — Source: AuthorIn today’s guide we discussed about one of the most fundamental data structures, namely Linked Lists. Given that Python’s standard library does not contain any implementation of this specific data structure, we explored how one can implement a user-defined Linked List class from scratch. Become a member and read every story on Medium. Your membership fee directly supports me and other writers you read. You’ll also get full access to every story on Medium. You may also like There are different ways to insert new nodes into a linked list, each with its own implementation and level of complexity. That’s why you’ll see them split into specific methods for inserting at the beginning, end, or between nodes of a list. Inserting a new node at the beginning of a list is probably the most straightforward insertion since you don’t have to traverse the whole list to do it. It’s all about creating a new node and then pointing the head of the list to it. Have a look at the following implementation of add_first() for the class LinkedList: def add_first(self, node): node.next = self.head self.head = node In the above example, you’re setting self.head as the next reference of the new node so that the new node points to the old self.head. After that, you need to state that the new head of the list is the inserted node. Here’s how it behaves with a sample list: >>>>>> llist = LinkedList() >>> llist None >>> llist.add_first(Node("b")) >>> llist b -> None >>> llist.add_first(Node("a")) >>> llist a -> b -> None As you can see, add_first() always adds the node to the head of the list, even if the list was empty before. Inserting a new node at the end of the list forces you to traverse the whole linked list first and to add the new node when you reach the end. You can’t just append to the end as you would with a normal list because in a linked list you don’t know which node is last. Here’s an example implementation of a function for inserting a node to the end of a linked list: def add_last(self, node): if self.head is None: self.head = node return for current_node in self: pass current_node.next = node First, you want to traverse the whole list until you reach the end (that is, until the for loop raises a StopIteration exception). Next, you want to set the current_node as the last node on the list. Finally, you want to add the new node as the next value of that current_node. Here’s an example of add_last() in action: >>>>>> llist = LinkedList(["a", "b", "c", "d"]) >>> llist a -> b -> c -> d -> None >>> llist.add_last(Node("e")) >>> llist a -> b -> c -> d -> e -> None >>> llist.add_last(Node("f")) >>> llist a -> b -> c -> d -> e -> f -> None In the code above, you start by creating a list with four values (a, b, c, and d). Then, when you add new nodes using add_last(), you can see that the nodes are always appended to the end of the list. Inserting between two nodes adds yet another layer of complexity to the linked list’s already complex insertions because there are two different approaches that you can use:
It might seem weird to split these into two methods, but linked lists behave differently than normal lists, and you need a different implementation for each case. Here’s a method that adds a node after an existing node with a specific data value: def add_after(self, target_node_data, new_node): if self.head is None: raise Exception("List is empty") for node in self: if node.data == target_node_data: new_node.next = node.next node.next = new_node return raise Exception("Node with data '%s' not found" % target_node_data) In the above code, you’re traversing the linked list looking for the node with data indicating where you want to insert a new node. When you find the node you’re looking for, you’ll insert the new node immediately after it and rewire the next reference to maintain the consistency of the list. The only exceptions are if the list is empty, making it impossible to insert a new node after an existing node, or if the list does not contain the value you’re searching for. Here are a few examples of how add_after() behaves: >>>>>> llist = LinkedList() >>> llist.add_after("a", Node("b")) Exception: List is empty >>> llist = LinkedList(["a", "b", "c", "d"]) >>> llist a -> b -> c -> d -> None >>> llist.add_after("c", Node("cc")) >>> llist a -> b -> c -> cc -> d -> None >>> llist.add_after("f", Node("g")) Exception: Node with data 'f' not found Trying to use add_after() on an empty list results in an exception. The same happens when you try to add after a nonexistent node. Everything else works as expected. Now, if you want to implement add_before(), then it will look something like this: 1def add_before(self, target_node_data, new_node): 2 if self.head is None: 3 raise Exception("List is empty") 4 5 if self.head.data == target_node_data: 6 return self.add_first(new_node) 7 8 prev_node = self.head 9 for node in self: 10 if node.data == target_node_data: 11 prev_node.next = new_node 12 new_node.next = node 13 return 14 prev_node = node 15 16 raise Exception("Node with data '%s' not found" % target_node_data) There are a few things to keep in mind while implementing the above. First, as with add_after(), you want to make sure to raise an exception if the linked list is empty (line 2) or the node you’re looking for is not present (line 16). Second, if you’re trying to add a new node before the head of the list (line 5), then you can reuse add_first() because the node you’re inserting will be the new head of the list. Finally, for any other case (line 9), you should keep track of the last-checked node using the prev_node variable. Then, when you find the target node, you can use that prev_node variable to rewire the next values. Once again, an example is worth a thousand words: >>>>>> llist = LinkedList() >>> llist.add_before("a", Node("a")) Exception: List is empty >>> llist = LinkedList(["b", "c"]) >>> llist b -> c -> None >>> llist.add_before("b", Node("a")) >>> llist a -> b -> c -> None >>> llist.add_before("b", Node("aa")) >>> llist.add_before("c", Node("bb")) >>> llist a -> aa -> b -> bb -> c -> None >>> llist.add_before("n", Node("m")) Exception: Node with data 'n' not found With add_before(), you now have all the methods you need to insert nodes anywhere you’d like in your list. |
