了解Python中的链接列表实现

I have found an implementation of a Linked List in Python, online, but it doesn't have any explanation or comments.

我在线发现了Python链接列表的实现,但它没有任何解释或注释。

I understand the underlying concepts of a Linked List, but there is one key part of the code I don't understand:

我理解链接列表的基本概念,但是我不理解的代码中有一个关键部分:

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

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next

    def set_data(self, data):
        self.data = data

    def set_next(self, next):
        self.next = next

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

    def is_empty(self):
        return self.head == None

    def add(self, item):
        temp = Node(item)
        temp.set_next(self.head)
        self.head = temp

    def size(self):
        current = self.head
        count = 0

        while current != None:
            count += 1
            current = current.get_next()

        return count

    def search(self, item):
        current  = self.head

        while current != None:
            if current.get_data() == item:
                return True
            else:
                current = current.get_next()

        return False

    def remove(self, item):
        current = self.head
        previous = None
        found = False

        while not found:
            if current.get_data() == item:
                found = True
            else:
                previous = current
                current = current.get_next()

        if previous == None:
            self.head = current.get_next()
        else:
            previous.set_next(current.get_next())

I don't understand how the size, search and remove methods in the LinkedList class are able to call functions from the Node class via the current variable, after setting it to self.head, which seems to be contained within the scope of the LinkedList class.

我不明白LinkedList类中的大小,搜索和删除方法如何能够通过当前变量调用Node类中的函数,然后将其设置为self.head,这似乎包含在LinkedList的范围内类。

Is it because the add method sets self.head = temp, where temp is a Node object?

是因为add方法设置self.head = temp,其中temp是Node对象?

If possible, could someone explain how this works?

如果可能,有人可以解释这是如何工作的吗?

1 个解决方案

#1

You stated that:

你声明:

I don't understand how the size, search and remove methods in the LinkedList class are able to call functions from the Node class via the current variable, after setting it to self.head, which seems to be contained within the scope of the LinkedList class.

我不明白LinkedList类中的大小,搜索和删除方法如何能够通过当前变量调用Node类中的函数,然后将其设置为self.head,这似乎包含在LinkedList的范围内类。

You can see that in the code, initializing a LinkedList performs this line of code:

您可以在代码中看到,初始化LinkedList会执行以下代码行:

self.head = None

Since the head is set to none, the size, search, and remove methods will not run through the whole code. Rather, it will stop when the self.head == None, which is pretty much in the beginning.

由于head设置为none,因此size,search和remove方法不会贯穿整个代码。相反,它会在self.head == None时停止,这几乎在开始时。

For example, let's take a look at the size method.

例如,让我们看一下size方法。

def size(self):

    current = self.head
    count = 0

    while current != None:
        count += 1
        current = current.get_next()

    return count

In this function, current is set to self.head which is null unless you have added any nodes by calling the add() method. More on that later.

在此函数中,current设置为self.head,除非您通过调用add()方法添加了任何节点,否则该值为null。稍后会详细介绍。

count is set equal to 0. Then a while loop begins which only runs if the current is not None. But since the current is set to self.head which is None, the while loop will not run and the function will return count which is 0. This is a correct implementation because there are currently no nodes in the linkedlist.

count设置为0.然后while循环开始,仅在当前不是None时运行。但由于当前设置为self.head为None,因此while循环不会运行,函数将返回0的计数。这是一个正确的实现,因为链表中当前没有节点。

Now onto how you can add nodes.

现在了解如何添加节点。

The add method:

添加方法:

    def add(self, item):
        temp = Node(item)
        temp.set_next(self.head)
        self.head = temp

Here, the add method takes in itself and an item. The item is an object of some sort whether it be a string, integer, float, etc. Now a variable temp is created and set to a new node which is finally using something from the Node class. Then, temp's next node is set to head and the head is set to temp. What this does is that the linked list continuously updates the head.

这里,add方法接收一个项目。该项是某种对象,无论是字符串,整数,浮点数等。现在创建一个变量temp并将其设置为一个新节点,该节点最终使用Node类中的某些内容。然后,将temp的下一个节点设置为head,将head设置为temp。这样做的是链表不断更新头部。

Like this:

(head) NODE1

ADD ONE MORE NODE

添加更多节点

(head) NODE2 NODE1

(头)NODE2 NODE1

And so on...

等等...

Happy Coding!