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?
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.
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