Search code examples
pythondata-structureslinked-list

Add a node to a linked list that is implemented with two lists


I am implementing a linked list in Python using two lists - one to store values and one to store pointers, so that a node has its value in values and the value it points to is stored in its corresponding index in the pointers array.

I wrote a function that adds a node to the head of a linked list. It bumps up every element in both arrays while remembering the last element, so that it can be appended at the end, and then inserting the new node at the 0 index of the lists.

I left the indices of self.pointers in terms of self.values because they are the same size and are adjusted in the same way.

My code:

class LinkedList:
    def __init__(self):
        self.values = []
        self.pointers = []
        
    def addAtHead(self, val):
        if not self.values:
            self.values.append(val)         
            self.pointers.append(None)      
            return
        
        append_val = self.values[-1]
        
        for i in range(1, len(self.values)):
            self.values[len(self.values) - i] = self.values[len(self.values) - i-1]
            self.pointers[len(self.values) - i] = self.pointers[len(self.values) - i-1]
    
    
        self.values[0] = val
        self.pointers[0] = self.values[1]
    
        self.values.append(append_val)
        self.pointers.append(None)
        

ll = LinkedList()
ll.addAtHead(10)
ll.addAtHead(20)

When I run this, I get the following error:

Traceback (most recent call last):
  File "/main.py", line 29, in <module>
    ll.addAtHead(2)
  File "/main.py", line 20, in addAtHead
    self.pointers[0] = self.values[1]
                       ~~~~~~~~~~~^^^
IndexError: list index out of range

But this statement is needed to attach the first node...

What is my mistake?


Solution

  • There are several issues here:

    • Your code does not store any pointers. In the context of using lists, a "pointer" to a list entry would be an index. But with self.pointers[0] = self.values[1] you assign a value, not an index.

    • The approach to shift all entries one place forward to make room for the new head is an inefficient one. It kills the benefit you would expect to get from linked lists, which are supposed to allow a new node to be added as head without any loop, in constant time (no matter how many elements there are already in the linked list).

    • This approach also makes that the index at which a value is stored is also its order in the linked list. But that makes the pointers list useless: you can just iterate the values list from left to right to visit the values in the intended order, and you just have a plain list. pointers becomes useful when you don't shift values, but keep them where they are, no matter what you add or delete from the list. The pointers list is then responsible for indicating their relative order in the linked list.

    This also means that if you remove an item from the linked list, you should not have to shift any other values. You should instead update the impacted pointers so that this node is skipped and no longer part of the linked list.

    Implementation

    It is a bit awkward to implement a linked list with two lists, as Python is an object-based language, and so an OOP approach is the more natural one. But if you really want to do this with two lists, then also maintain a "free list", i.e. a linked list of nodes that were previously removed and could be reused for storing new values.

    To have a kind of demo, I added two more methods: one to make the linked list iterable (which facilitates printing), and a remove method to remove a first occurrence of a given value from the linked list.

    class LinkedList:
        def __init__(self):
            self.values = []
            self.pointers = []
            self.free = None
            self.head = None
            
        def add_head(self, val):
            if self.free is None:  # There is no free slot
                # Create a free slot
                self.free = len(self.values)
                self.values.append(None)
                self.pointers.append(None)
            # Get the index of a free slot
            i = self.free
            self.free = self.pointers[i]  # Update to link the next free slot
            # Populate the newly occupied slot
            self.values[i] = val
            self.pointers[i] = self.head  # link to what was previously the head
            self.head = i  # The new node is now the head
            
        def __iter__(self):
            i = self.head
            while i is not None:
                yield self.values[i]
                i = self.pointers[i]
    
        def remove(self, val):
            prev = None
            # Find first occurrence of val 
            i = self.head
            while i is not None and self.values[i] != val:
                prev = i  # Keep track of the node that precedes it
                i = self.pointers[i]
            if i is not None:  # Value was found
                # Exclude the node
                if prev is None:  # The node to remove is the head node
                    self.head = self.pointers[i]
                else:
                    self.pointers[prev] = self.pointers[i]
                # Prepend this slot to the free list
                self.pointers[i] = self.free
                self.free = i
    
    # demo
    ll = LinkedList()
    ll.add_head(5)
    ll.add_head(3)
    ll.add_head(2)
    print(*ll)  # 2 3 5
    ll.remove(3)
    print(*ll)  # 2 5
    ll.remove(2)
    print(*ll)  # 5
    ll.add_head(4)
    print(*ll)  # 4 5
    ll.add_head(8)
    print(*ll)  # 8 4 5