单链列表Python头和尾

Question

我正在学习来自C++的Python，我不知道为什么我在类LinkedList中的插入方法不能工作。我期待我的头节点被链接到我的尾节点，但是我没有得到预期的行为。

class Node:
    value = None
    nextNode = None

    def __init__(self, value=None):
        self.value = value
        self.nextNode = None

class LinkedList:

    head = Node()
    tail = Node()

    def __init__(self):
        self.head = None
        self.tail = Node()

    #insert a node method
    def insert(self, value):
        #if new list
        if self.head == None:
            newNode = Node(value)
            self.head = newNode
            newNode.nextNode = self.tail
        else:
            newNode = Node(value)
            self.tail.nextNode = newNode
            self.tail = newNode
            newNode.nextNode = self.head



list1 = LinkedList()
list1.insert(23)
list1.insert(50)
print(list1.head.nextNode.value) #Expect this to be 50, but this returns None

Answer 1

如果您试图插入一个新节点作为一个尾，那么尝试如下：

class Node:
    def __init__(self, value=None):
        self.value = value
        self.nextNode = None


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

    def insert(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
        elif self.tail:
            self.tail.nextNode = new_node
            self.tail = new_node
        else:
            self.head.nextNode = new_node
            self.tail = new_node


list1 = LinkedList()
list1.insert(23)
list1.insert(50)
list1.insert(40)
list1.insert(99)

node = list1.head
print('(head)', end=' -> ')
while node:
    print(node.value, end=' -> ')
    node = node.nextNode
print('(tail)')

(head) -> 23 -> 50 -> 40 -> 99 -> (tail)

不需要使用类变量。

Answer 2

这门课用哨兵要简单得多，但是头应该是哨兵。

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


class LinkedList:
    def __init__(self):
        self.head = Node(0)  # Store the length, or any other metadata you like
        self.tail = self.head  # The tail is just the last item.

    # the list is empty when the head and the tail are the same
    # node (namely, the sentinel)
    def is_empty(self):
        return self.tail is self.head

    def insert(self, value):
        """Add a value to the end of the list"""
        new_node = Node(value)
        self.tail.next = new_node  # Append the node
        self.tail = new_node  # Advance the tail
        self.head.value += 1  # Update the length

这就是你所需要的。列表保持两个不变量:头总是指向一个前哨节点，而尾总是引用列表的最后一个元素。附加到列表仅仅意味着在尾后追加一个节点，然后更新尾。

head的目的是提供一个迭代列表的入口点。尾是一种方便，可以将O(1)操作追加到列表的末尾，而不必花O(n)时间从头上迭代以找到最后一个节点。

几个练习：

len(ll)

• Your

1. with LinkedList.__len__，因此您可以检索带有insert的列表的长度，这实际上应该被称为append。编写一个“真实”的insert方法，该方法确定一个位置，以指示应该在何处插入新节点。( element.)
2. Write ll.insert(0, x)将创建一个新的第一个元素，ll.insert(n, x)将在n-1 LinkedList.delete之后插入一个新元素以删除指定位置的元素。ll.delete(0)将删除ll的第一个元素。请注意，这永远不会移除哨兵，也就是说，如果True.

返回ll.is_empty()，则为无操作。

Answer 3

你不需要有一个伊莱夫或尾巴。

class Node:
    value = None
    nextNode = None

    def __init__(self, value=None):
        self.value = value
        self.nextNode = None

class LinkedList:

    head = Node()

    def __init__(self):
        self.head = None

    #insert a node method
    def insert(self, value):
        #if new list
        newNode = Node(value)
        if not self.head:
            self.head = newNode
        else:
            #save head's current position
            temp = self.head
            #move head's position until you find a None value for
            #nextNode
            while(temp.nextNode):
                temp = temp.nextNode

            #set the none value to the new node
            temp.nextNode = newNode

    list1 = LinkedList()
    list1.insert(23)
    list1.insert(50)
    list1.insert(50)
    list1.insert(70)
    print(list1.head.value)
    #23
    print(list1.head.nextNode.value)
    #50
    print(list1.head.nextNode.nextNode.value)
    #50
    print(list1.head.nextNode.nextNode.nextNode.value)
    #70