Python Linked List Class Definitions

I ran into something interesting whilst learning about Data Structures and Algorithms in Python - particularly the implementation of Linked Lists. While defining the Class Definitions for the Linked List’s Node and the Linked List itself, I noticed some examples define the Node Class with both the “Value” and the “Next” Properties as Arguments in the Initialization Method, and other examples define said Node Class with only the “Value” Property as an Argument in the Initialization Method - keeping the “Next” Property as a Locally Defined Variable from the perspective of the Node Class itself.

I am hypothesizing that the latter is more accurate and secure since it should be the role and responsibility of the Linked List Class to modify the Node’s “Next” property, making the code more secure and removing the possibility of accidental modification.

Could someone confirm this for me and please tell me if my assumptions are accurate? If they are not, could someone break this down for me a little more and correct my hypothesis?

I tried looking up examples of how to properly define Classes for Linked Lists and Nodes.

The following are excerpts of the examples I was referring to…

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)
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

Compared to…

class Node:
def __init__(self, data):
    self.data = data
    self.next = None

def __repr__(self):
    return self.data

class LinkedList:
def __init__(self):
    self.head = None

def __repr__(self):
    node = self.head
    nodes = []
    while node is not None:
        nodes.append(node.data)
        node = node.next
    nodes.append("None")
    return " -> ".join(nodes)

You're asking whether it is more "accurate and secure" to have a Node constructor that does not take a next argument, and give the following in defence:

> it should be the role and responsibility of the Linked List Class to modify the Node’s “Next” property

This is a true statement, but whether or not the Node constructor has this extra parameter does not really have an impact on that. The LinkedList class will need a way to link nodes together, which means that the Node class has to expose a way to do that, either via a method, or by directly setting its next attribute, or ... via the constructor. For instance, if the LinkedList has a method to insert a value at a given index, then two Node-referencing attributes will need to be set: the new node's next attribute and the next attribute of the new node's predecessor (or the head reference of the linked list).

> making the code more secure and removing the possibility of accidental modification.

The LinkedList class should of course be designed so that there is no room for accidents. The risk is more at the side of the code that will use the LinkedList class.

The two implementations you have provided can hardly be compared, as the second one doesn't even offer methods to manipulate the linked list -- it doesn't have code that creates/adds nodes to its list. Apparently the user of these classes is supposed to create the Node instances themselves, which really is a bad idea. The first one implements a doubly linked list, and also maintains a reference to the tail node. As it provides methods for managing the linked list, it is superior to the second implementation. On the negative side, the first implementation has methods that return Node instances to the caller, who could then (accidentally?) set the next attribute of this node potentially breaking the linked list.

To better protect the linked list from "accidents", you could decide to not expose any Node reference to the code that instantiates a LinkedList. This you don't achieve by removing the next parameter fro the Node constructor, but by forbidding (or at least discouraging) the user of your LinkedList class to tamper with the nodes that are in the list. You can achieve that by taking the following measures:

• Make clear that the head reference (and tail reference, if there is one) is an internal implementation detail. In Python you do this by naming it with an underscore (_head).
• Don't have methods in the LinkedList class that take a Node reference as argument, nor that return or yield a Node reference.

This way the user of LinkedList will never access the nodes directly, but will only communicate values with the LinkedList class.

Having the next parameter in the Node constructor can actually help to make the LinkedList implementation more concise.

Here is a possible implementation of such "protective" LinkedList class:

class LinkedList:
    class Node:
        def __init__(self, value, next=None):
            self.value = value
            self.next = next
    
        def get(self, index):
            if index >= 0:
                for _ in range(index):
                    self = self.next
                    if not self:
                        break
                return self
    
    def __init__(self, *values):
        self._head = None
        for value in reversed(values):
            self.push(value)

    def isempty(self):
        return not self._head
    
    def push(self, value):
        self._head = self.Node(value, self._head)

    def pop(self):
        if not self.isempty():
            value = self._head.value
            self._head = self._head.next
            return value

    def insert(self, index, value):
        if index == 0:
            return self.push(value)
        prev = self._head.get(index - 1)
        if prev:
            prev.next = self.Node(value, prev.next)
        
    def delete(self, index):
        if index == 0:
            return self.pop()
        prev = self._head.get(index - 1)
        if prev and prev.next:
            value = prev.next.value
            prev.next = prev.next.next
            return value
        
    def __iter__(self):
        node = self._head
        while node:
            yield node.value  # don't expose nodes; only values
            node = node.next


lst = LinkedList(10, 20, 30, 40)
print(lst.pop())       # 10
print(*lst)            # 20 30 40
lst.insert(1, 10)
print(*lst)            # 20 10 30 40
lst.insert(4, 50)
print(*lst)            # 20 10 30 40 50
lst.delete(4)
print(*lst)            # 20 10 30 40
lst.delete(0)
print(*lst)            # 10 30 40