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 |1 Answer
Reset to default 0There 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
pointerslist useless: you can just iterate thevalueslist from left to right to visit the values in the intended order, and you just have a plainlist.pointersbecomes useful when you don't shift values, but keep them where they are, no matter what you add or delete from the list. Thepointerslist 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
版权声明：本文标题：python - Add a node to a linked list that is implemented with two lists - Stack Overflow 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/web/1742273289a2444714.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
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 youraddAtHeadhere is definitionallyO(n), not even amortizedO(1). If you want a linked list, this ain't it. – ShadowRanger Commented Nov 27, 2024 at 2:00