Top List List

Linked list Python vs c

How to Implement a Linked List in Python

Exploring how to write Linked List and Node objects from scratch using Python

Giorgos Myrianthous

Dec 20, 2021·6 min read

Photo by Mael BALLAND on Unsplash

Introduction

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.

A singly linked list Source: Author

On the other hand, in Doubly Linked Lists each node points to the next as well as to the previous node.

A doubly linked list Source: Author

Linked Lists are extremely useful in various scenarios. They are typically preferred over standard arrays when

you need a constant time when adding or removing elements from the sequence
manage memory more efficiently especially when the number of elements is unknown [if arrays you may have to constantly shrink or grow them. Note though that filled arrays usually take up less memory than Linked Lists.
you want to insert items in the middle point more efficiently

Unlike other general purpose languages, Python does not have a built-in implementation of Linked Lists in its standard library. In todays article we will explore how to implement a user-defined Linked List class using Python.

Implementing User Defined Linked Link Class in Python

First, lets 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.

class Node:
def __init__[self, value, next_node=None, prev_node=None]:
self.value = value
self.next = next_node
self.prev = prev_node

def __str__[self]:
return str[self.value]

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.

class LinkedList:
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values]

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.

def add_node[self, value]:
if self.head is None:
self.tail = self.head = Node[value]
else:
self.tail.next = Node[value]
self.tail = self.tail.next
return self.tail

Now lets go through the logic of the method quickly. If the Linked List has no head, then it means its 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.

def add_multiple_nodes[self, values]:
for value in values:
self.add_node[value]

So far, our Linked List class looks like below:

class LinkedList:
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values] def add_node[self, value]:
if self.head is None:
self.tail = self.head = Node[value]
else:
self.tail.next = Node[value]
self.tail = self.tail.next
return self.tail def add_multiple_nodes[self, values]:
for value in values:
self.add_node[value]

Now lets create an additional method thatd be able to insert a new element but this time in the beginning of the Linked List, i.e. as a head.

def add_node_as_head[self, value]:
if self.head is None:
self.tail = self.head = Node[value]
else:
self.head = Node[value, self.head]
return self.head

Now lets override some special methods in our class that could potentially be useful. Firstly, lets 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.

def __str__[self]:
return ' -> '.join[[str[node] for node in self]]

Secondly, lets 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.

def __len__[self]:
count = 0
node = self.head
while node:
count += 1
node = node.next
return count

Finally, lets ensure that LinkedList class is iterable by implementing __iter__ method.

def __iter__[self]:
current = self.head
while current:
yield current
current = current.next

Additionally, we could also create a property called values so that we can access the values of all nodes included in the sequence.

@property
def values[self]:
return [node.value for node in self]

The final class looks like below:

class LinkedList:
def __init__[self, values=None]:
self.head = None
self.tail = None if values is not None:
self.add_multiple_nodes[values] def __str__[self]:
return ' -> '.join[[str[node] for node in self]] def __len__[self]:
count = 0
node = self.head
while node:
count += 1
node = node.next
return count def __iter__[self]:
current = self.head
while current:
yield current
current = current.next @property
def values[self]:
return [node.value for node in self] def add_node[self, value]:
if self.head is None:
self.tail = self.head = Node[value]
else:
self.tail.next = Node[value]
self.tail = self.tail.next
return self.tail def add_multiple_nodes[self, values]:
for value in values:
self.add_node[value] def add_node_as_head[self, value]:
if self.head is None:
self.tail = self.head = Node[value]
else:
self.head = Node[value, self.head]
return self.head

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:

class DoublyLinkedList[LinkedList]:
def add_node[self, value]:
if self.head is None:
self.tail = self.head = Node[value]
else:
self.tail.next = Node[value, None, self.tail]
self.tail = self.tail.next
return self def add_node_as_head[self, value]:
if self.head is None:
self.tail = self.head = Node[value]
else:
current_head = self.head
self.head = Node[value, current_head]
current_head.prev = self.head
return self.head

Full Code for User-Defined Linked Lists in Python

The full code containing the three classes we created as part of todays tutorial is given below as a GitHub Gist.

The full code containing Node, LinkedList and DoublyLinkedList Python classes Source: Author

Final Thoughts

In todays guide we discussed about one of the most fundamental data structures, namely Linked Lists. Given that Pythons 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. Youll also get full access to every story on Medium.

Join Medium with my referral link Giorgos Myrianthous

As a Medium member, a portion of your membership fee goes to writers you read, and you get full access to every story

gmyrianthous.medium.com

You may also like

LeetCode Problem 2: Add Two Numbers Solution in Python

Understanding how to efficiently work out Add Two Numbers problem with Linked Lists in Python

towardsdatascience.com

Augmented Assignments in Python

Understanding how augmented assignment expressions work in Python and why you should be careful when using them with