Implementation of Singly Linked List in Python

Question

I am learning basic data structures in Python. I'm not confident enough if my implementations are OK or I miss any corner cases. So please check my code for Singly Linked List and Let me know where I can improve.

"""
Singly Linked List Implementation 
"""
class Node:
 """
 Constructor for Node class
 takes 3 arguments. 'value' for Node's value and 'next' for next Node.
 Default are Node.
 Return Node object
 """
 def __init__(self, value=None, next=None):
 self.value = value
 self.next: Node = next
 def __repr__(self):
 return str(self.value)
 '''
 returns the string of the node value
 '''
 def __str__(self) -> str:
 return str(self.value)
class LinkedList:
 '''
 Constructor requires a value
 '''
 def __init__(self, value):
 self.head = Node(value=value)
 '''
 returns iterator to iterate through the LinkedList
 '''
 def __iter__(self):
 current = self.head
 while current:
 yield current
 current = current.next
 '''
 To print the LinkedList object like
 4 -> 5 -> 7 -> 10
 '''
 def __repr__(self) -> str:
 values = []
 current = self.head
 while current:
 values.append(str(current.value))
 current = current.next
 return " -> ".join(values)
 '''
 append at the end of the LinkedList
 '''
 def append(self, value):
 if not self.head:
 self.head = Node(value=value)
 return
 current = self.head
 while current.next:
 current = current.next
 current.next = Node(value=value)
 def prepend(self, value):
 new_head = Node(value=value)
 new_head.next = self.head
 self.head = new_head
 def delete(self, value):
 if not self.head:
 return
 
 '''
 if HEAD is the desired Node then unlink it and make next Node as HEAD
 '''
 if self.head.value == value:
 self.head = self.head.next
 return
 '''
 Bypass the Node with value to unlink it.
 If next Node has the desired value to delete, then 
 make next.next as next Node unlink next
 4->5->7
 4->7
 '''
 current = self.head
 while current.next:
 if current.next.value == value:
 current.next = current.next.next
 return
 current = current.next

Test code:

# 4->5->7->10
a = LinkedList(4)
a.append(5)
a.append(7)
a.append(10)
print("after adding")
print(a)
a.delete(7)
print("after deleting 7")
print(a)
a.prepend(2)
print("after prepending 2")
print(a)
a.delete(10)
print("after deleting 10")
print(a)
a.delete(10)

Output

after adding
4 -> 5 -> 7 -> 10
after deleting 7
4 -> 5 -> 10
after prepending 2
2 -> 4 -> 5 -> 10
after deleting 10
2 -> 4 -> 5

• vnp: __iter__ is badly broken.
• eNipu: Hi @vnp, Thank you! Please share your test code that is failed. I could not reproduce the problem.
• Nate T: I would implement the __next__() method as well. Like a m, it is hey function that iterable objects are required to implement. Besides, a linked list class isn't very helpful without a method for traversing the links.

Answer 1

Docstrings

A docstring for a class or function needs to be the first statement in the body of the class/function (see PEP 257). Thus, it should look as follows:

class MyClass:
 """
 This is a very useful class. 
 """
 def my_function(self):
 """
 This is a function. 
 """
 return None

This is used by the Python help system. For example, if you execute help(MyClass) you will get:

 Help on class MyClass in module __main__:
 
 class MyClass(builtins.object)
 | This is a very useful class.
 | 
 | Methods defined here:
 | 
 | my_function(self)
 | This is a function.

Instead, in your code comments are entered before definitions of classes and functions.

Docstrings for __init__(), __repr__() and __str__() are usually not needed, since these methods have standard functionality.

Arguments of __init__() should be described in the docstring for the class e.g.:

class Node:
 """ 
 Node of a single linked list. 
 
 Parameters
 ----------
 value : Value of the node.
 next_node : Next node.
 """
 def __init__(self, value=None, next_node=None):
 self.value = value
 self.next = next_node

Then, executing help(Node) gives:

Help on class Node in module __main__:
class Node(builtins.object)
 | Node(value=None, next_node=None)
 | 
 | Node of a single linked list. 
 | 
 | Parameters
 | ----------
 | value : Value of the node.
 | next_node : Next node.
 | ...

Notice that Python automatically uses __init__ to show how to construct a class instance and what the default values of the constructor arguments are.

By the way, in the __init__ method I replaced the argument next with next_node. next is a name of a built-in Python function, and variable names in your code should not clash with it.

String representations

The return value of __repr__() is supposed be a string representation of the object. To the extent possible, it should look like a valid Python code which, if it was executed, would produce the represented object. For example, in the Node class I would define __repr__() as follows:

def __repr__(self):
 if self.next is None:
 repr_next = repr(None)
 else:
 repr_next = super(Node, self.next).__repr__()
 return f"Node(value={repr(self.value)}, next_node={repr_next})"

Then executing

node1 = Node(4)
repr(node1)

one gets:

'Node(value=4, next_node=None)'

The code

node2 = Node(10, next_node=node1)
repr(node2)

gives:

'Node(value=10, next_node=<__main__.Node object at 0x1194813d0>)'

In this case we can’t return code that would link node2 to node1, but we can at least include a string describing the next node of node2.

The rules for the return value of __str__() are more flexible. It is supposed to be a user-friendly representation of the object. Still, in the Node class returning str(self.value) is misleading, since a Node instance is not the same thing as its value. If a user of your code who executes print(node1) sees 4, they may get an impression that they are dealing with an integer-like object and that something like 5 * node1 + 2 should work. I would use instead something like this:

def __str__(self):
 return f"[{str(self.value)}] -> {str(None) if self.next is None else '...'}"

Then print(node1) gives

[4] -> None

and print(node2) yields

[10] -> ...

The three dots are intended to convey the information that the node is followed by another node. This is not the only (and possibly not the best) option, but it gives a better representation of what a node is than the value of the node alone.

__repr__() and __str__() in the LinkedList class should be redefined to be compatible with string representations of Node objects. An additional issue in this case is, that a linked list may consist of many nodes, and if __repr__() and __str__() try to list all of them, the resulting strings can be huge. I would print, say, up to three nodes and somehow indicate if the list continues beyond that. For example:

def __str__(self):
 if self.head is None:
 return str(None)
 llist_str = ""
 N = 2
 for i, node in enumerate(self):
 if node.next is not None:
 s = str(node)[:-3]
 else:
 s = str(node)
 llist_str += s
 if i >= N:
 break
 if node.next is not None:
 llist_str += "..."
 return llist_str 

Then the code

llist = LinkedList(4)
llist.append(5)
llist.append(7)
llist.append(10)
print(list)

Gives:

[4] -> [5] -> [7] -> ...

Appending and deleting

It is rather inconvenient that the constructor of LinkedList allows one to create linked lists with precisely one node only. In particular, an empty list can be created only indirectly, using something like

llist = LinkedList(1).delete(1)

It is better to modify __init__ so it accepts an iterable as an argument, and creates a linked list using values produced by the iterable:

def __init__(self, values):
 self.head = None
 for v in values:
 self.append(v) 

Additionally, I would change the append() method as follows:

def append(self, value):
 if self.head is None: 
 self.head = Node(value)
 else:
 for current in self:
 pass
 current.next = Node(value)

In particular I would use if self.head is None instead of if not self.head as it is done in your code. It is more explicit. Also, it will work even if at some point you decide to implement __bool__() in the Node class to redefine what the boolean value of a node is. Both this version of append() and yours are not efficient, since they need to traverse the whole list in order to append a node. It would be better to keep track which node is the tail of the list, and use it to append new nodes.

prepend() can be simplified to

def prepend(self, value):
 self.head = Node(value, next=self.head)

Finally, I would probably rename the delete() method to remove(), since its functionality is analogous to remove() for Python lists: it removes the first node with the specified value.

• eNipu: Thanks a lot I will update the existing code and share it here.