admin管理员组

文章数量:1331849

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?

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?

Share Improve this question edited Dec 2, 2024 at 13:35 trincot 352k36 gold badges272 silver badges325 bronze badges asked Nov 27, 2024 at 1:41 matemmatem 131 bronze badge 4
  • How to Ask and minimal reproducible example – Julien Commented Nov 27, 2024 at 1:44
  • How is this a linked list? You've got a pair of array-like things (Python calls them lists, but they have nothing to do with linked lists) pointing to each other, but that's not anything resembling an actual linked list, having none of the benefits you'd expect of one (e.g. fixed cost insertion/deletion; your code will have amortized cost insertion/deletion with spikes each time the underlying arrays must be resized). In particular, it should be fixed cost at either end, and your addAtHead here is definitionally O(n), not even amortized O(1). If you want a linked list, this ain't it. – ShadowRanger Commented Nov 27, 2024 at 2:00
  • If you're storing values in a regular list, why do you even need the list of pointers?! – John Gordon Commented Nov 27, 2024 at 2:55
  • In any case, you have not explained the actual problem. Saying the code "doesn't work" is not nearly specific enough. Please show us what this code actually does, and explain what you expected instead. – John Gordon Commented Nov 27, 2024 at 2:59
Add a comment  | 

1 Answer 1

Reset to default 0

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

本文标签: pythonAdd a node to a linked list that is implemented with two listsStack Overflow