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]