在 Python 的链表中添加和插入后获取位置

Question

我是一名自学成才的程序员初学者，我正在学习数据结构课程。在运行追加和插入方法之后尝试调用 get_position 方法时，我运行遇到了麻烦，我不明白为什么会这样。参考下面的代码，print(ll.get_position(5).value) 在调用插入方法之前和插入之后打印“5”，我希望 print(ll.get_position(6).value) 会打印“5”，但它打印“3”。此外，我可以在 get_position 方法中将任何数字作为参数传递，即使该数字超出链表范围，它仍会打印“3”或“4”。我假设插入方法的 while 循环被卡住了？如何将 e5 重新附加到链表？为什么会迷路？

谢谢！

class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

    def append(self, new_element):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element

    def get_position(self, position):

        counter = 1
        current = self.head

        while current and counter <= position:
            if counter == position:
                return current

            current = current.next
            counter += 1

    def insert(self, new_element, position):

        counter = 1
        current = self.head

        if position < 1:
            return None

        elif position == 1:
            new_element.next = self.head
            self.head = new_element

        while current and counter < position:
            if counter == position - 1:
                new_element.next = current.next
                current.next = new_element
                return

            current = current.next
            counter += 1


#  Elements in list
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)
e5 = Element(5)

# Linked List Setup
ll = LinkedList(e1)
ll.append(e2)
ll.append(e3)
ll.append(e4)
ll.append(e5)

# Should print 5
print(ll.get_position(5).value)

ll.insert(e4, 3)

# Expected Ouput: 1,2,4,3,4
print(ll.get_position(1).value)
print(ll.get_position(2).value)
print(ll.get_position(3).value)
print(ll.get_position(4).value)
print(ll.get_position(5).value)
# Expected output: 5 (Actual Output 3)
print(ll.get_position(6).value)
# Expected output: Error. (Actual Output 4)
print(ll.get_position(7).value)

Answer 1

您正在使用指向节点 e5 的现有 e4 节点。创建一个值为 4 的新元素，然后将其传递给插入方法。

new_e4 = Element(4)
l1.insert(new_e4, 3)

插入 e4 后，您希望链表看起来像

1 -> 2 -> 4 -> 3 -> 4 -> 5

但实际上链表变成了：

1 -> 2 -> 4 <=> 3 5 ( 5 is lost and 3 is pointing back to 4 and hence infinite loop)

在 Python 的链表中添加和插入后获取位置

Get Position After Append and Insertion in Linked List in Python

python

linked-list