singly linked list python code

Question

I have recently tried converting a singly linked list from a C program into my own python program. I have tested the code myself but I am still unsure if the program has been converted properly. I would like someone to peer review my code to see if there are any errors in methodology, too many methods, any missing methods, etc.

I have tried implementing some of my own singly linked list operations based from the advice from this website: https://afteracademy.com/blog/types-of-linked-list-and-operation-on-linked-list

The original C Program: https://people.eng.unimelb.edu.au/ammoffat/ppsaa/c/listops.c

My own python code:

class Node():
 
 # Node for a single linked list
 def __init__(self, data):
 self.data = data
 self.next = None
 
class LinkedList():
 def __init__(self):
 self.head = None
 self.foot = None
 def length(self):
 '''Returns the length of a linked list.'''
 current_node = self.head
 node_total = 0
 while (current_node != None):
 node_total += 1
 current_node = current_node.next
 return node_total
 def is_empty_list(self):
 '''Checks if a linked list is empty.'''
 return self.head == None
 def stack_insert(self, data):
 '''Inserts a node at the HEAD of the list;
 LIFO (Last In, First Out).'''
 new_node = Node(data)
 # Makes new_node.next point to next node (defualt None if 1st insertion)
 new_node.next = self.head
 # Makes the HEAD of linked list point to new node
 self.head = new_node
 if (self.foot == None):
 # First insertion into linked list; node becomes HEAD & FOOT
 self.foot = new_node
 def queue_append(self, data):
 '''Appends a node at the FOOT of the list;
 FIFO (First In, First Out).'''
 new_node = Node(data)
 
 if (self.head == None):
 # First insertion into linked list; node becomes HEAD & FOOT
 self.head = self.foot = new_node
 
 else:
 # Makes the original last node point to the newly appended node
 self.foot.next = new_node
 # Makes the newly appended list as the official FOOT of the linked list
 self.foot = new_node
 def insert_after(self, data, index):
 '''Inserts a NEW node AFTER a specific node indicated by index.'''
 # Need to ensure provided index is within range
 if (index < 0):
 print("ERROR: 'insert_after' Index cannot be negative!")
 return
 elif (index > (self.length() -1)):
 print("ERROR: 'insert_after' Index exceeds linked list range!")
 return
 # Use stack_insert to insert as first item
 elif (self.is_empty_list()) or (index == 0):
 self.stack_insert(data)
 return
 # Use queue_insert to append as last item
 elif (index == (self.length() -1)):
 self.queue_append(data)
 return
 new_node = Node(data)
 prior_node = self.head
 current_node = self.head
 search_index = 0
 
 # Keep traversering through nodes until desired node
 while (search_index != index):
 prior_node = current_node
 current_node = current_node.next
 search_index += 1
 
 # Makes prior node is point to target node
 prior_node = current_node
 # Makes current node point to the node AFTER target node (default None of last node)
 current_node = current_node.next
 # Makes target node point to newly added node
 prior_node.next = new_node
 # Makes newly added node point to original node that WAS AFTER target node
 new_node.next = current_node
 def delete_head(self):
 '''Deletes the HEAD node.'''
 # Linked list is empty
 if self.is_empty_list():
 return
 old_head = self.head
 # Adjusts the head pointer to step past original HEAD
 self.head = self.head.next
 if (self.head == None):
 # The only node just got deleted
 self.foot = None
 def delete_foot(self):
 '''Deletes the FOOT node.'''
 # Linked list is empty
 if self.is_empty_list():
 return
 old_foot = self.foot
 prior_node = self.head
 current_node = self.head
 # Need to keep cycling until final node is reached
 while (current_node.next != None):
 prior_node = current_node
 current_node = current_node.next
 
 # Adjust newly FOOT node to point to nothing
 prior_node.next = None
 # Makes linked list forget about original FOOT node
 self.foot = prior_node
 def delete_node(self, index):
 '''Deletes a target node via index.'''
 # Linked list is empty
 if self.is_empty_list():
 return
 # Need to ensure index is within proper range
 elif (index < 0):
 print("ERROR: 'delete_node' Index cannot be negative!")
 return
 elif (index > (self.length() -1)):
 print("ERROR: 'delete_node' Index exceeds linked list range")
 return
 
 prior_node = self.head
 current_node = self.head
 search_index = 0
 # Keep travsersing though nodes until desired node
 while (search_index != index):
 prior_node = current_node
 current_node = current_node.next
 search_index += 1
 # Adjusts node PRIOR to target node to point to the node the AFTER target node
 prior_node.next = current_node.next
 def update_node(self, new_data, index):
 '''Updates target node data via index.'''
 # Linked list is empty
 if self.is_empty_list():
 print("ERROR: 'update_node' Linked list is empty; no node data to update!")
 return
 
 # Need to ensure index is within proper range
 elif (index < 0):
 print("ERROR: 'update_node' Index cannot be negative!")
 return
 elif (index > (self.length() -1)):
 print("ERROR: 'update_node' Index exceeds linked list range!")
 current_node = self.head
 search_index = 0
 # Keep traversing through nodes until desired node
 while (search_index != index):
 current_node = current_node.next
 search_index += 1
 # Can now change data
 current_node.data = new_data
 def get_node_data(self, index):
 '''Extracts that data from a specific node via index.'''
 # Linked list is empty
 if self.is_empty_list():
 print("ERROR: 'update_node' Linked list is empty; no node data to update!")
 return
 
 # Need to ensure index is within proper range
 elif (index < 0):
 print("ERROR: 'update_node' Index cannot be negative!")
 return
 elif (index > (self.length() -1)):
 print("ERROR: 'update_node' Index exceeds linked list range!")
 # Index matches HEAD or FOOT
 if (index == 0):
 return self.head.data
 elif (index == (self.length() -1)):
 return self.foot.data
 
 current_node = self.head
 search_index = 0
 # Keep traversing though nodes until desired node
 while (search_index != index):
 current_node = current_node.next
 search_index += 1
 
 return current_node.data

Answer 1

Your code looks un-Pythonic because you are using methods like length rather dunder methods like __len__.

Node

Before that we can change Node to use dataclasses. dataclasses will automatically give your class some boiler-plate, like __init__ and __repr__. To use dataclasses.dataclass you need to type your class. To type attributes we can use attr: type.

from typing import Any
class Node:
 data: Any
 next: "Node"
 # ...

There are two important parts to note;

• you should try not to use Any as doing so destroys type information. Here we can instead use typing.TypeVar and typing.Generic. And
• we have encased the type Node in a string. Before Python 3.10 type annotations are eagerly evaluated. Since we're using the name Node before Node has been assigned, if we didn't the type would fail to resolve. We can use from __future__ import annotations to make Python use lazy evalutaion automatically from Python 3.7+.

from __future__ import annotations
from typing import Generic, TypeVar
T = TypeVar("T")
class Node(Generic[T]):
 data: T
 next: Node
 # ...

We can now change the class to use dataclasses.dataclass. Since we want to be able to not provide next in the __init__ we can assign None to next, so that next defaults to None if nothing is provided.

import dataclasses
@dataclasses.dataclass
class Node(Generic[T]):
 data: T
 next: Node = None
ll = Node(0, Node(1)) # example usage
print(ll)

Node(data=0, next=Node(data=1, next=None))

The nice output helps makes debugging much easier as now we can just print self.head (in the LinkedList) to be able to visually debug any incorrect states. The default __repr__ also automatically handles recursion, to aide in debugging.

ll.next.next = ll
print(ll)

Node(data=0, next=Node(data=1, next=...))

Note: ... just means there is recursion here, we would get the same output if we assigned ll.next rather than ll.

Linked List

Iterating

def length(self):
 '''Returns the length of a linked list.'''
 current_node = self.head
 node_total = 0
 while (current_node != None):
 node_total += 1
 current_node = current_node.next
 return node_total

There are some ways length is not Pythonic:

• For consistency, always use """triple double quotes""" around docstrings.

• You should use is when comparing to singletons like None.

• Please don't use unneeded parentheses.

  while current_node is not None:
  

• Your method's name should be __len__ as then you can use len(obj) rather than obj.length(). Doing so can help make LinkedList a drop in replacement for say list.

• I would define a generator function to iterate through the linked list. Using a generator function can make your code much simpler. We can then use standard iterator parts of Python like for and sum instead.

def __iter__(self):
 curr = self.head
 while curr is not None:
 yield curr.data
 curr = curr.next
def __len__(self):
 """Returns the length of a linked list."""
 return sum(1 for _ in self)

Inserting

Rather than defaulting head, and foot, to None we can default to Node(None). We can then make your code simpler by getting rid of all the if self.head is None code.

def queue_append(self, data):
 self.foot.next = Node(data)
 self.foot = self.foot.next

Note: If you do add a default head then you'd need to change __iter__ to not return the default head. However we wouldn't need to change __len__, because __len__ is based off __iter__!

Inserting into the head would also stay simple. The changes we made to Node can also make the code simpler.

def stack_insert(self, data):
 self.head.next = Node(data, self.head.next)
 if self.foot is self.head:
 self.foot = self.head.next

There are some change I'd make to insert_after:

• Rather than using stack_insert and queue_append, the code would be far simpler built from scratch.

• Since length, or __len__, has to iterate through the linked list, calling the function isn't too helpful.

• Any performance gain from queue_append is lost by using length.

• By calling stack_insert with an input of 0 your code is prone to making bugs.

  ll = LinkedList()
  ll.queue_append("a")
  ll.insert_after("b", 0)
  ll.insert_after("c", 1)
  print(ll.head)
  

  Node(data='b', next=Node(data='a', next=Node(data='c', next=None)))
  

• Now that the linked list will always have a root Node we can easily change the function to insert before, rather than after.

• You should raise errors not print.

In all I'd follow KISS.

def insert(self, index, value):
 if index < 0:
 raise IndexError("cannot work with negative indexes")
 curr = self.head
 for _ in range(index):
 curr = curr.next
 if curr is None:
 raise IndexError(f"index, {index}, is out of range")
 curr.next = Node(value, curr.next)
 if curr is self.foot:
 self.foot = curr.next

Now stack_insert looks quite unneeded; we can just use LinkedList.insert(0, ...) instead. Also if we changed __len__ to return from a constant then we could change the code so there is no appreciable gain from queue_append.

Deleting

Rather than falling for the same problems as insert we should just ignore delete_head and delete_foot.

Since the code for finding the current node, or previous node for delete, is exactly the same, we can make a function to return a desired node.

def _index(self, index):
 if index < 0:
 raise IndexError("cannot work with negative indexes")
 curr = self.head
 for _ in range(index):
 curr = curr.next
 if curr is None:
 raise IndexError(f"index, {index}, is out of range")
 return curr

Now we just need to ensure the next value is is not None as the index would be out of range. And ensure we update self.foot.

def delete_node(self, index):
 prev = self._index(index)
 if prev.next is None:
 raise IndexError(f"index, {index}, is out of range")
 if prev.next is self.foot:
 self.foot = prev
 prev.next = prev.next.next

Getting / Updating

There should be no suprise. We just call self._index and handle the node however is needed.

Pythonisms

• We can use the container dunder methods:

  • get_node_data -> __getitem__
  • update_node -> __setitem__
  • delete_node -> __delitem__

• A common Python idiom is negative numbers mean 'go from the end'. We can easily change _index to handle negatives rather than error.

• You should rename is_empty_list to __bool__ to allow truthy testing your linked list.

• You should mimic the names of existing datatypes, like list or collections.deque. Note: you should not mimic the names of queue.Queue or multiprocessing.Queue; both classes are used for a different pattern than your code is for.

  • stack_insert -> appendleft.
  • queue_append -> append.
  • delete_head -> popleft.
  • delete_foot -> pop.

from __future__ import annotations
import dataclasses
from typing import Generic, TypeVar
T = TypeVar("T")
@dataclasses.dataclass
class Node(Generic[T]):
 data: T
 next: Node = None
class LinkedList:
 def __init__(self):
 self.head = self.foot = Node(None)
 self._length = 0
 
 def __iter__(self):
 curr = self.head.next
 while curr is not None:
 yield curr
 def __len__(self):
 return self._length
 def __bool__(self):
 return self.head.next is None
 # You don't need max if you don't want to make a doubly
 # linked list with a foot node like the head node
 def _norm_index(self, index, min=0, max=0):
 index += min if 0 <= index else max
 index = len(self) + 1 + index if index < 0 else index
 if index < min:
 raise IndexError("out of range min")
 if len(self) + max < index:
 raise IndexError("out of range max")
 return index
 def _index(self, index, min=0, max=0):
 try:
 _index = self._norm_index(index, min, max)
 if _index == len(self):
 return self.foot
 curr = self.head
 for _ in range(_index):
 curr = curr.next
 if curr is None:
 raise IndexError("curr is None")
 return curr
 except IndexError as e:
 raise IndexError(f"index, {index}, is out of range").with_traceback(e.__traceback__) from None
 def __getitem__(self, index):
 return self._index(index, min=1).data
 def __setitem__(self, index, value):
 curr = self._index(index, min=1)
 curr.data = value
 def __delitem__(self, index):
 prev = self._index(index - 1 if index < 0 else index)
 if prev.next is None:
 raise IndexError(f"index, {index}, is out of range")
 if prev.next is self.foot:
 self.foot = prev
 self._length -= 1
 prev.next = prev.next.next
 def insert(self, index, value):
 curr = self._index(index)
 self._length += 1
 curr.next = Node(value, curr.next)
 if curr is self.foot:
 self.foot = curr.next
 def append(self, value):
 self.insert(-1, value)
 def appendleft(self, value):
 self.insert(0, value)
 def pop(self):
 del self[-1]
 def popleft(self):
 del self[0]

• nan: May I kindly check why TypeVar('T') is better than Any? I am unsure how to use TypeVar('T') properly here.
• Peilonrayz: @nan Take list, you can provide a type for the objects inside - a: list[str]. This tells us we have a list of strings. From here we can then know using " ".join(a) would work, where b: list[int] would fail. As str.join only accepts joining strings. Any means we wouldn't know if the data in the list is a str or an int, meaning we can't be sure whether or not " ".join will work. As list[Any] can contain strings, integers, well anything.
• nan: Ah got it, now I am busy changing all my codes from Any to Generic, as I can already see why it is useful in type hinting. Thanks!
• Peilonrayz: @nan Happy to help! :) One thing to note, from my understanding tools like mypy assume you will be slowly moving from a large untyped project to a typed one. This means a lot of the checks are turned off by default. Because no-one likes seeing errors in the thousands to hundreds of thousands. If you use these tools to help find possible bugs then you'll want to check for a --strict mode. When I got over the learning curve with --strict Python's typing system has become very simple and second nature to use.
• nan: Yes mypy is painful sometimes, especially when I use tuple([10, 10, 10]), it refuses to treat it as Tuple[int, int, int] for example.