Python链表-插入方法

Question

我对DataStructure有点陌生，我正在尝试编写LinkedList，但我不明白为什么我的insert方法不起作用。如果你有任何改进的建议，请写信给我

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

class LinkedList:
def __init__(self):
self.start_node = None
self.index = 0
def append(self, val):
new = Node(val)
if not self.start_node:
self.start_node = new
return
last = self.start_node
while last.ref:
last = last.ref
last.ref = new
self.index += 1
def insert(self, index, value):
start_counting = 0
start = self.start_node
while start_counting < index:
start = start.ref
start_counting += 1
NewNode = Node(value)
tmp = start.ref
start = NewNode
start.ref = tmp
def display(self):
ls = []
last = self.start_node
while last:
ls.append(last.item)
last = last.ref
return ls

Answer 1

插入函数替换当前节点，而不是链接它

我有以下链接列表：1->2->3.我想插入一个元素"；4〃；在位置1(位置1中的当前数字为2(。迭代将是：

start_counting = 0
start = self.start_node (node with value 1)

---

第一次迭代：

start_counting < 1 -> true
start = start.ref (node with value 2)
start_counting += 1 (actual count 1)

第二次迭代：

start_counting < 1 -> false
start = (node with value 2)

---

之后代码继续如下：

We create the new Node (4 in my example) and we do:
tmp = start.ref (which is 3)
start = NewNode (we are replacing the node completely, we are not linking the node with another) <- here is the error
start.ref = tmp (which in this case is 3)

---

要修复错误，您应该考虑两件事：

1. 迭代到上一个节点，而不是下一个节点
2. 处理要将节点作为链表的头插入的情况，换句话说，插入位置为0

代码类似于：

def insert(self, index, value):
start_counting = 0
start = self.start_node
NewNode = Node(value)
if index == 0: # Handling the position 0 case.
NewNode.ref = start
self.start_node = NewNode
else:
while start_counting < index - 1: # Iterating until the previous node.
start_counting += 1
start = start.ref
NewNode.ref = start.ref
start.ref = NewNode

使用以下代码进行了测试，它正在工作：

a = LinkedList()
a.append(1)
a.append(2)
a.append(3)
a.insert(0, 4)
a.insert(1, 5)
print(a.display())

Answer 2

链表没有索引，所以不需要从index=0开始。对于链表，还有3种插入方法，insert_to_first、insert_to_last或insert_toany_position。您正在执行insert_to_any位置。

def insert(self, index, value):
start_counting = 0
start = self.start_node
while start_counting < index:
start = start.ref
start_counting += 1
# so far no issue
NewNode = Node(value,None) # new Node accepts 2 args
# Let's write a linked list to visualize
# A->B->C-> adding_Node_Here ->D->E... make sure we dont lose ref to D when we inser
# after while loop, we end up start=C
NewNode.ref=start.ref # we keep the ref to D
start.ref=NewNode # now C refs to NewNode
self.index+=1 # again linked list is not indexed. "size" is better term