用 Python 理解链表

Question

我正在使用 Python 对链表进行自学。我正在努力尝试将链表的结构和概念可视化。下面是来自自学的代码，要求我添加缺失的代码。有人可以画出或解释我应该如何想象这个。我熟悉常规的 Python 列表、字典和其他常见的数据结构。但例如对于我的思考过程的方法是

if current:

    return current.value

else:

    return None

但这是不正确的。我是否在检查构造函数是否初始化了一个列表并有一个元素变量 current？以下是完整代码。谢谢你。

"""The LinkedList code from before is provided below.

Add three functions to the LinkedList.

"get_position" returns the element at a certain position.

The "insert" function will add an element to a particular

spot in the list.

"delete" will delete the first element with that

particular value.

Then, use "Test Run" and "Submit" to run the test cases

at the bottom."""

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):

        """Get an element from a particular position.

        Assume the first position is "1".

        Return "None" if position is not in the list."""

        return None

    def insert(self, new_element, position):

        """Insert a new node at the given position.

        Assume the first position is "1".

        Inserting at position 3 means between

        the 2nd and 3rd elements."""

        pass

    def delete(self, value):

        """Delete the first node with a given value."""

        pass

# Test cases

# Set up some Elements

e1 = Element(1)

e2 = Element(2)

e3 = Element(3)

e4 = Element(4)

# Start setting up a LinkedList

ll = LinkedList(e1)

ll.append(e2)

ll.append(e3)

# Test get_position

# Should print 3

print ll.head.next.next.value

# Should also print 3

print ll.get_position(3).value

# Test insert

ll.insert(e4,3)

# Should print 4 now

print ll.get_position(3).value

Answer 1

对于我的思考过程的方法是......什么方法？get_position? insert? delete?正如@JacobIRR 建议的那样，添加一种打印链接列表的方法可能会有所帮助。看一看：class Element:    def __init__(self, value):        self.value = value        self.next = Noneclass LinkedList:    def __init__(self):        self.head = None    def append(self, value):        element = Element(value)        if self.head is None:            self.head = element            return        cursor = self.head        while cursor.next is not None:            cursor = cursor.next        cursor.next = element    def __str__(self):        values = []        cursor = self.head        while cursor is not None:            values.append(cursor.value)            cursor = cursor.next        return " -> ".join(values)def main():    linked_list = LinkedList()    linked_list.append("Foo")    linked_list.append("Bar")    linked_list.append("Fizz")    linked_list.append("Buzz")    print(linked_list)    return 0if __name__ == "__main__":    import sys    sys.exit(main())输出：Foo -> Bar -> Fizz -> Buzz

Answer 2

所有你需要做的：首先，尝试在将状态更改为该状态时可视化会发生什么，或者将整个可视化写在纸上，甚至在任何在线软件中以了解更改。最后/最后，确保你了解链表的核心概念，并用它做一些棘手的、一堆不同的操作。或者，您可以在Google上搜索一些资源。好吧，这是我为您的问题所做的解决方案：class Element(object):&nbsp; &nbsp; def __init__(self, value):&nbsp; &nbsp; &nbsp; &nbsp; self.value = value&nbsp; &nbsp; &nbsp; &nbsp; self.next = Noneclass LinkedList(object):&nbsp; &nbsp; def __init__(self, head=None):&nbsp; &nbsp; &nbsp; &nbsp; self.head = head&nbsp; &nbsp; def append(self, new_element):&nbsp; &nbsp; &nbsp; &nbsp; current = self.head&nbsp; &nbsp; &nbsp; &nbsp; if self.head:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while current.next:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current = current.next&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current.next = new_element&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.head = new_element&nbsp; &nbsp; def get_position(self, position):&nbsp; &nbsp; &nbsp; &nbsp; counter = 1&nbsp; &nbsp; &nbsp; &nbsp; current = self.head&nbsp; &nbsp; &nbsp; &nbsp; if position < 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return None&nbsp; &nbsp; &nbsp; &nbsp; while current and counter <= position:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if counter == position:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return current&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current = current.next&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; counter += 1&nbsp; &nbsp; &nbsp; &nbsp; return None&nbsp; &nbsp; def insert(self, new_element, position):&nbsp; &nbsp; &nbsp; &nbsp; counter = 1&nbsp; &nbsp; &nbsp; &nbsp; current = self.head&nbsp; &nbsp; &nbsp; &nbsp; if position > 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while current and counter < position:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if counter == position - 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new_element.next = current.next&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current.next = new_element&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current = current.next&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; counter += 1&nbsp; &nbsp; &nbsp; &nbsp; elif position == 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new_element.next = self.head&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.head = new_element&nbsp; &nbsp; def delete(self, value):&nbsp; &nbsp; &nbsp; &nbsp; current = self.head&nbsp; &nbsp; &nbsp; &nbsp; previous = None&nbsp; &nbsp; &nbsp; &nbsp; while current.value != value and current.next:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; previous = current&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current = current.next&nbsp; &nbsp; &nbsp; &nbsp; if current.value == value:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if previous:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; previous.next = current.next&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.head = current.next# Test cases# Set up some Elementse1 = Element(1)e2 = Element(2)e3 = Element(3)e4 = Element(4)# Start setting up a LinkedListll = LinkedList(e1)ll.append(e2)ll.append(e3)# Test get_position# Should print 3print(ll.head.next.next.value)# Should also print 3print(ll.get_position(3).value)# Test insertll.insert(e4,3)# Should print 4 nowprint(ll.get_position(3).value)# Test deletell.delete(1)# Should print 2 nowprint(ll.get_position(1).value)# Should print 4 nowprint(ll.get_position(2).value)# Should print 3 nowprint(ll.get_position(3).value)再次，任何进一步的问题；拿一张纸，编写代码并可视化正在发生的事情。