插入有序链表 (Python)

Question

我在为有序链表创建插入函数时遇到问题。这是我目前所拥有的：

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

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next

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

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


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

    def __str__(self):
        output_string = ''

        current = self.head
        while current is not None:
            output_string += str(current.get_data())
            next_node = current.get_next()

            if next_node is not None:
                output_string += "->"

            current = next_node

        return output_string

    def insert(self, data):
        other = self.head
        previous = None
        if other is None:
            new_node = Node(data)
            new_node.set_next(self.head)
            self.head = new_node
        else:
                while data > other.get_data():
                    previous = other
                    other = other.get_next
                previous.set_next(Node(data))

Answer 1

我想改变这个：

    else:
            while data > other.get_data():
                previous = other
                other = other.get_next
            previous.set_next(Node(data))

对此，应该让它起作用。

    else:
            # First condition will short circuit so there won't be exception on calling other.get_data() if other is None
            while other is not None and data > other.get_data():
                previous = other
                other = other.get_next()
            node = Node(data)
            node.set_next = previous.get_next()
            previous.set_next(node)

此外，getter 和 setter 方法在 python 中并不是必需的。如果您需要那种行为，约定是使用 @property 注释，私有成员通常以 _.

作为前缀

Answer 2

您需要将您的项目插入到列表中。这意味着您需要：

在你要插入的地方打断链条
创建一个新节点
再次将你的新节点加入链中。

从技术上讲，您不需要断开链条，因为在 previous 项上设置下一个 link 将清除旧的 link，因此您需要做的就是还在重新上链：

while data > other.get_data():
    previous = other
    other = other.get_next()
new = Node(data)
previous.set_next(new)
new.set_next(other)

我还纠正了一个不同的错误，你没有调用 Node.get_next().

接下来，您需要更多地考虑边缘情况。当您到达链的 end 但未找到 any 节点时会发生什么 node.get_data() 大于您插入的数据？

您需要调整 while 循环以确保您针对该情况进行了测试；对于链的最后一个元素，other 将是 None：

while other is not None and data > other.get_data():
    previous = other
    other = other.get_next()
new = Node(data)
previous.set_next(new)
new.set_next(other)

您还可以做其他事情来改进您的代码。在Python中不需要使用setters和getters；以后将属性转为 @property 是没有成本的，所以在这里使用属性就可以了。

您还可以让您的 Node() 在构造函数中接受下一个元素，这样可以更轻松地插入元素。

您可以使用 str.join() 在序列的元素之间插入固定字符串。将所有 data 属性放入 Python list 并加入该列表。

创建初始元素时无需将self.head设置为下一个节点（当self.head为None时）；这已经是默认值了：

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

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

    def __str__(self):
        data_list = []    
        current = self.head
        while current is not None:
            data_list.append(str(current.data))
            current = current.next
        return '->'.join(data_list)

    def insert(self, data):
        other = self.head
        previous = None
        if other is None:
            self.head = Node(data)
        else:
            while other is not None and data > other.data:
                previous = other
                other = other.next
            previous.next = Node(data, other)

演示：

>>> ll = LinkedList()
>>> str(ll)
''
>>> ll.insert(10)
>>> str(ll)
'10'
>>> ll.insert(20)
>>> str(ll)
'10->20'
>>> ll.insert(15)
>>> str(ll)
'10->15->20'

插入有序链表 (Python)

Insert in Ordered Linked List (Python)

python

python-3.x