Python中的链表 - 添加、索引、插入和弹出功能，代码/错误不确定

Question

这个作业要求我们实现一个无序链表的几个方法，包括添加（append）、插入（insert）、查找（index）和弹出（pop）。

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

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

    def AppendNode(self, data):
        new_node = Node(data)

        if self.head == None:
            self.head = new_node

        if self.tail != None:
            self.tail.next = new_node

        self.tail = new_node
    def PrintList( self ):
        node = self.head

        while node != None:
            print (node.data)
            node = node.next

    def PopNode( self, index ):
        prev = None
        node = self.head
        i = 0

        while ( node != None ) and ( i < index ):
            prev = node
            node = node.next
            i += 1

        if prev == None:
            self.head = node.next
        else:
            prev.next = node.next

list = LinkedList()
list.AppendNode(1)
list.AppendNode(2)
list.AppendNode(3)
list.AppendNode(4)
list.PopNode(0)
list.PrintList( )

到目前为止的输出结果：

    2
    3
    4
    Traceback (most recent call last):
      File "<pyshell#32>", line 1, in <module>
        main()
      File "<pyshell#31>", line 50, in main
        list.PrintList( )
      File "<pyshell#31>", line 27, in PrintList
        node = node.next
    AttributeError: 'Node' object has no attribute 'next'

我不太明白为什么会出现错误，因为代码在技术上是可以工作的。另外，关于插入和查找这两个函数的任何建议都非常感谢。

Answer 1

注意，在你定义的Node类中，“next”这个字段是叫“next_node”。所以解释器不知道“next”是什么。因此，应该用node.next_node，而不是node.next。

Answer 2

这段代码是用来处理一些数据的。它的主要目的是从一个地方获取信息，然后对这些信息进行一些操作，最后把结果返回给你。具体来说，它可能会从数据库中提取数据，或者从用户输入中获取信息。

在这段代码中，可能会有一些循环和条件判断，这样可以根据不同的情况做出不同的处理。比如，如果数据满足某个条件，就执行某个操作；如果不满足，就执行另一个操作。

总的来说，这段代码的功能就是帮助你更方便地管理和处理数据，让你能更轻松地得到想要的结果。

def insert(self,item,position):
    if position==0:
        self.add(item)

    elif position>self.size():
        print("Position index is out of range")

    elif position==self.size():
        self.append(item)

    else:
        temp=Node.Node(item,position)
        current=self.head
        previous=None
        current_position=0

        while current_position!=position:
            previous=current
            current=current.next
            current_position+=1

        previous.next=temp
        temp.next=current

Answer 3

下面是我想到的实现方法（已经测试过并且可以正常工作）。这似乎是一个旧帖子，但我在其他地方找不到完整的解决方案，所以我把它发在这里。

# add -- O(1)
# size -- O(1) & O(n)
# append -- O(1) & O(n)
# search -- O(n)
# remove -- O(n)
# index -- O(n)
# insert -- O(n)
# pop -- O(n)  # can be O(1) if we use doubly linked list
# pop(k) -- O(k)

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

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setNext(self, newnext):
        self.next = newnext    

class UnorderedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    def isEmpty(self):
        return self.head is None

    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp
        if self.tail is None:
            self.tail = temp
        self.length += 1

    def ssize(self):  # This is O(n)

        current = self.head
        count = 0
        while current is not None:
            count += 1
            current = current.getNext()
        return count

    def size(self): # This is O(1)
        return self.length

    def search(self, item):
        current = self.head
        found = False
        while current is not None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

    def remove(self,item):
        current = self.head
        previous = None
        found = False
        while current is not None and not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        if previous == None:
            # The item is the 1st item
            self.head = current.getNext()
        else:
            if current.getNext() is None:
                self.tail = previous  # in case the current tail is removed
            previous.setNext(current.getNext())
        self.length -= 1

    def __str__(self):
        current = self.head
        string = '['
        while current is not None:
            string += str(current.getData())
            if current.getNext() is not None:
                string += ', '
            current = current.getNext()
        string += ']'
        return string


    def sappend(self, item):  # This is O(n) time complexity
        current = self.head
        if current:
            while current.getNext() is not None:
                current = current.getNext()
            current.setNext(Node(item))
        else:
            self.head = Node(item)

    def append(self, item): # This is O(1) time complexity
        temp = Node(item)
        last = self.tail
        if last:
            last.setNext(temp)
        else:
            self.head = temp
        self.tail = temp
        self.length += 1

    def insert(self, index, item):
        temp = Node(item)
        current = self.head
        previous = None
        count = 0
        found = False
        if index > self.length-1:
            raise IndexError('List Index Out Of Range')
        while current is not None and not found:
            if count == index:
                found = True
            else:
                previous = current
                current = current.getNext()
                count += 1
        if previous is None:
            temp.setNext(self.head)
            self.head = temp
        else:
            temp.setNext(current)
            previous.setNext(temp)
        self.length += 1

    def index(self, item):
        pos = 0
        current = self.head
        found = False
        while current is not None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
                pos += 1
        if not found:
            raise ValueError('Value not present in the List')
        return pos

    def pop(self, index=None):
        if index is None:
            index = self.length-1
        if index > self.length-1:
            raise IndexError('List Index Out Of Range')
        current = self.head
        previous = None
        found = False
        if current:
            count = 0
            while current.getNext() is not None and not found:
                if count == index:
                    found = True
                else:
                    previous = current
                    current = current.getNext()
                    count += 1
            if previous is None:
                self.head = current.getNext()
                if current.getNext() is None:
                    self.tail = current.getNext()
            else:
                self.tail = previous
                previous.setNext(current.getNext())
        self.length -= 1
        return current.getData()

Answer 4

对于 insert 和 index 这两个方法，你需要在 Node 类里增加一个属性，因为你需要知道每个项目在列表中的位置。我们可以把这个属性叫做 position。现在你的 Node 类看起来应该是这样的：

class Node:
    def __init__(self, data, position = 0):
        self.data = data
        self.next_node = None
        self.position = position

现在获取索引值就变得简单多了：

def index(self,item):
    current = self.head
    while current != None:
        if current.data == item:
            return current.position
        else:
            current = current.next
    print ("item not present in list")

至于修改列表的方法，我建议先从一个简单的 add 方法开始，这个方法可以把项目添加到列表的最左边：

def add(self,item):
        temp = Node(item)           #create a new node with the `item` value
        temp.next = self.head     #putting this new node as the first (leftmost) item in a list is a two-step process. First step is to point the new node to the old first (lefmost) value
        self.head = temp            #and second is to set `LinkedList` `head` attribute to point at the new node. Done!
        current = self.head         #now we need to correct position values of all items. We start by assigning `current` to the head of the list
        self.index_correct(current) #and we'll write helper `index_correct` method to do the actual work.
        current = self.head
        previous = None
        while current.position != self.size() - 1:
             previous = current
             current = current.next
             current.back = previous
        self.tail = current

index_correct 方法应该做什么呢？其实就一件事——遍历列表，以便在我们添加新项目（比如说：add、insert 等）或删除项目（remove、pop 等）时，更新项目的索引位置。所以它应该是这样的：

def index_correct(self, value):
    position = 0
    while value != None:
        value.position = position
        position += 1
        value = value.next

这非常简单。现在，让我们来实现你要求的 insert 方法：

def insert(self,item,position):
    if position == 0:
        self.add(item)
    elif position > self.size():
        print("position index out of range")
    elif position == self.size():
        self.AppendNode(item)
    else:
        temp = Node(item, position)
        current = self.head
        previous = None
        while current.position != position:
            previous = current
            current = current.next
        previous.next = temp
        temp.next = current
        temp.back = previous
        current.back = temp
        current = self.head
        self.index_correct(current)