用 Python 理解链表

Question

我正在使用 Python 对链表进行自学。我正在努力尝试将链表的结构和概念可视化。下面是来自自学的代码，要求我添加缺失的代码。有人可以画出或解释我应该如何想象这个。我熟悉常规的 Python 列表、字典和其他常见的数据结构。但例如对于我的思考过程的方法是if current:    return current.valueelse:    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 particularspot in the list."delete" will delete the first element with thatparticular value.Then, use "Test Run" and "Submit" to run the test casesat the bottom."""class Element(object):    def __init__(self, value):        self.value = value        self.next = Noneclass 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 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

Answer 1

对于我的思考过程的方法是......

什么方法？get_position? insert? delete?

正如@JacobIRR 建议的那样，添加一种打印链接列表的方法可能会有所帮助。看一看：

class Element:

    def __init__(self, value):

        self.value = value

        self.next = None

class 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 0

if __name__ == "__main__":

    import sys

    sys.exit(main())

输出：

Foo -> Bar -> Fizz -> Buzz

Answer 2

所有你需要做的：

首先，尝试在将状态更改为该状态时可视化会发生什么，或者将整个可视化写在纸上，甚至在任何在线软件中以了解更改。

最后/最后，确保你了解链表的核心概念，并用它做一些棘手的、一堆不同的操作。或者，您可以在Google上搜索一些资源。

好吧，这是我为您的问题所做的解决方案：

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

        if position < 1:

            return None

        while current and counter <= position:

            if counter == position:

                return current

            current = current.next

            counter += 1

        return None

    def insert(self, new_element, position):

        counter = 1

        current = self.head

        if position > 1:

            while current and counter < position:

                if counter == position - 1:

                    new_element.next = current.next

                    current.next = new_element

                current = current.next

                counter += 1

        elif position == 1:

            new_element.next = self.head

            self.head = new_element

    def delete(self, value):

        current = self.head

        previous = None

        while current.value != value and current.next:

            previous = current

            current = current.next

        if current.value == value:

            if previous:

                previous.next = current.next

            else:

                self.head = current.next

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

# Test delete

ll.delete(1)

# Should print 2 now

print(ll.get_position(1).value)

# Should print 4 now

print(ll.get_position(2).value)

# Should print 3 now

print(ll.get_position(3).value)

再次，任何进一步的问题；拿一张纸，编写代码并可视化正在发生的事情。