Python 中的链表 - Append、Index、Insert 和 Pop 函数。不确定代码/错误

Linked List in Python- Append, Index, Insert, and Pop functions. Not sure with code/errors

提问by user3398858

This assignment asks us to implement the append, insert, index and pop methods for an unordered linked-list. (What I have so far)

该作业要求我们为无序列表实现 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( )

The output so far:

到目前为止的输出：

    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'

I'm not sure why i'm getting the errors, since the code is technically working. Also any input on the insert, and index functions would be greatly appreciated.

我不确定为什么会出现错误，因为代码在技术上是有效的。对插入和索引函数的任何输入也将不胜感激。

回答by Reloader

For insertand indexmethods you will need another Nodeattribute, because you'll need to keep track of which item is on what position. Let we call it position. Your Nodeclass will now look like this:

对于insert和index方法，您将需要另一个Node属性，因为您需要跟踪哪个项目位于哪个位置。让我们称之为position。你的Node类现在看起来像这样：

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

Retrieving index value now is easy as:

现在检索索引值很容易，因为：

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")

As for the list-altering methods, I would start with a simple addmethod which adds items to the leftmostposition in the 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

What shall the index_correctmethod do? Just one thing - to traverse the list in order to correct index position of items, when we add new items (for example: add, insertetc.), or remove them (remove, pop, etc.). So here's what it should look like:

该index_correct方法将做什么？只有一件事-遍历目录，以项目的正确索引位置，当我们添加新的项目（例如：add，insert等），或删除它们（remove，pop，等）。所以它应该是这样的：

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

It is plain simple. Now, let's implement insertmethod, as you requested:

这很简单。现在，让我们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)

回答by Jahid Apon

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

回答by sloppyhead

Below is the implementation that I could come up with (tested and working). It seems to be an old post, but I couldn't find the complete solution for this anywhere, so posting it here.

下面是我可以想出的实现（经过测试和工作）。这似乎是一个旧帖子，但我在任何地方都找不到完整的解决方案，因此将其发布在这里。

# 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()

回答by xYaelx

Notice that in the Node class you defined the "next" field as "next_node". Therefore the interpreter doesn't know "next". So, instead of node.next it should be node.next_node

请注意，在 Node 类中，您将“next”字段定义为“next_node”。因此，解释器不知道“下一个”。所以，而不是 node.next 它应该是 node.next_node