如何使用 OOP 实现链表？

Question

我正在尝试使用 OOP 和私有变量来实现一个链表。但是，'str' object has no attribute 'get_data'当我调用类的display方法时，我得到了LinkedList。另外，我觉得add方法也不对。当我打印self.__head和self.__tail输入时add()，代码永远不会进入 else 部分，它输出：Sugar SugarMilk MilkTea TeaBiscuit Biscuit下面是我的代码：class LinkedList:    def __init__(self):        self.__head=None        self.__tail=None    def get_head(self):        return self.__head    def get_tail(self):        return self.__tail    def add(self,data): # Skeptical about it        if self.__tail is None:            self.__head=Node(data).get_data()            self.__tail = self.__head            print(self.__head,self.__tail)        else:            b=Node(data)            self.__tail= b.get_data()            self.__head = self.__tail            b.set_next(self.__tail)            self.__tail = b.get_next()            print(self.__head,self.__tail)    def display(self): # Gives the error        temp = self.__head        msg = []        c = Node(temp)        while (temp is not None):            print(temp.get_data())            msg.append(str(temp.get_data()))            temp = temp.get_next()        msg = ''.join(msg)        print(msg)class Node:    def __init__(self,data):        self.__data=data        self.__next=None    def get_data(self):        return self.__data    def set_data(self,data):        self.__data=data    def get_next(self):        return self.__next    def set_next(self,next_node):        self.__next=next_nodelist1=LinkedList()list1.add("Sugar")#print(list1.get_head())#print("Element added successfully")list1.add("Milk")list1.add("Tea")list1.add("Biscuits")list1.display()

Answer 1

这似乎很可疑：

self.__head = Node(data).get_data()

考虑到您甚至不再引用节点...然后尝试调用 Node 对象的方法。即便如此，您的实现仍然是错误的。

我确定还有其他问题，但你可以谷歌这个或实际做你自己的项目/家庭作业。

Answer 2

所以，我已经为我的问题找到了答案。谢谢大家的帮助。这个我还不是很清楚：

我知道与 Java 等语言相比，python 默认不带有私有变量，但我相信 python 是关于尊重约定的，而“__”是告诉另一个开发人员这个特定实体是私有的约定。

但是，在我的情况下，我将无法直接访问 Node 类表单 LinkedList 类的数据和下一个属性，反之亦然，因为在使用私有变量时，名称会解析为_Classnmae__attribute_name。所以更好的解决方案是使用 getter 和 setter，因为它们是通用的。

def add(self,data):

    #Remove pass and write the logic to add an element

    new_node = Node(data)

    if self.__head is None:

        self.__head = self.__tail = new_node

    else:

        self.__tail.set_next(new_node)

        self.__tail = new_node

def display(self):

    #Remove pass and write the logic to display the elements

    temp = self.__head       

    msg = []

    c = Node(temp)

    while (temp is not None):

        msg.append(str(temp.get_data()))

        temp = temp.get_next()

    msg = ' '.join(msg)

    print(msg)

算法：

添加（数据）

用数据创建一个新节点

如果链表为空（头节点不引用任何其他节点），则使头节点和尾节点引用新节点

除此以外，

一种。使尾节点的链接指向新节点

湾 将新节点称为尾节点

Answer 3

这是一种通过使用我知道的几个单链表实现“技巧”来更简洁地做到这一点的方法。

链表总是由至少一个自动创建并存储在实例属性中的哨兵节点组成self._tail。拥有它有几个好处。

1. 知道在哪里tail可以快速轻松地添加一些东西。

2. 该列表永远不会为空，因此无需检查特殊情况。这样做的一个很好的副作用意味着迭代列表的元素只需要跟随self._next直到它是哨兵节点——一个单一的条件表达式。

另一个“技巧”是在当前哨兵节点之前添加一个新的最后一个元素——这在单链表中听起来很慢，因为它似乎需要修改Node要添加的元素。为了达到这样做的效果，但避免实际这样做，它所做的是将现有的哨兵节点转换为新的哨兵节点Node，并将其_next属性设为它创建的新哨兵节点，以替换之前被重用的哨兵节点。

这如何有助于理解以下代码中发生的事情：

class LinkedList:

    def __init__(self):

        self._tail = Node()

        self._head = self._tail

    def add(self, data):

        """ Add an item to the end of the linked list. """

        new_tail = Node()

        self._tail.set_data(data)  # Convert existing tail into a data node.

        self._tail.set_next(new_tail)

        self._tail = new_tail

        print('adding:', data)

    def display(self):

        """ Traverse linked list and print data associated with each Node. """

        print('\nLinked list contents:')

        curr = self._head

        while curr is not self._tail:

            print('  ' + curr.get_data())

            curr = curr.get_next()

class Node:

    def __init__(self, data=None):

        self._data = data

        self._next = None

    def get_data(self):

        return self._data

    def set_data(self, data):

        self._data = data

    def get_next(self):

        return self._next

    def set_next(self, next_node):

        self._next = next_node

if __name__ == '__main__':

    list1 = LinkedList()

    list1.add("Sugar")

    list1.add("Milk")

    list1.add("Tea")

    list1.add("Biscuits")

    list1.display()

输出：

adding: Sugar

adding: Milk

adding: Tea

adding: Biscuits

Linked list contents:

  Sugar

  Milk

  Tea

  Biscuits