如何在链表前插入元素？Python

Question

我一直在尝试把一个项目插入到链表的最前面，结果有点成功，但还不完全。下面是我目前的代码（在LinkedList类里还有其他方法，但我省略了，因为它们没有问题）：

class _Node():
    def __init__(self, data=None, link=None):
        self.data = data
        self.link = link

class LinkedList():
    def __init__(self):
        self.first = None
        self.size = 0

    def insert(self, ind, item):
        if self.first is None:
            self.first = _Node(item)
        elif ind == 0:                   # this is where the problem is. When I try to 
            temp = self.first            # insert a node to the front, it seems to
            temp.link = self.first.link  # forget about the rest of the nodes.
            self.first = _Node(item)
            self.first.link = temp  
        else:
            count = 0
            while count != ind - 1:
                count += 1
                self.first = self.first.link
            self.first.link = _Node(item, self.first.link)
        self.size += 1

假设我在命令行里有这个：

    >>> L = LinkedList()
    >>> L.insert(0, 5)
    >>> L.insert(1, 10)
    >>> L.insert(0, 20)
    >>> L[0]
    20
    >>> L[1]
    5
    >>> L[2]
    # and here is an error message, it says NoneType object has no attribute 'data'

在我上面的代码中，我想做的是创建一个临时的节点对象，这个临时节点和第一个节点是一样的。我把这个临时节点链接到第一个节点的链接上，然后我创建一个新的节点，并把这个新节点链接到临时节点上，但这样做并没有成功。希望能得到一些帮助，谢谢！

Answer 1

首先，注意这里其实不需要特别处理空列表的情况：

def insert(self, ind, item):
    if ind == 0:
        newnode = _Node(item, self.first)
        self.first = newnode

其次，这并不是问题所在。这段代码：

    else:
        count = 0
        while count != ind - 1:
            count += 1
            self.first = self.first.link
        self.first.link = _Node(item, self.first.link)
    self.size += 1

直接修改了 self.first 的值，所以它 忘记 了之前第一个节点是什么。要修复这个问题，最简单的办法是：

    else:
        count = 0
        insert_point = self.first # use a local variable to walk the list
        while count != ind - 1:
            count += 1
            insert_point = insert_point.link
        insert_point.link = _Node(item, insert_point.link)
    self.size += 1

Answer 2

看起来你之前忽略的那些函数，因为它们“不是问题”，实际上可能就是你的问题...

如果你以这种方式请求每个节点中的数据，你的代码就能正常工作：

>>> L = LinkedList()
>>> L.insert(0,5)
>>> L.insert(1,10)
>>> L.insert(0,20)
>>> print L.first.data
20
>>> print L.first.link.data
5
>>> print L.first.link.link.data
10

你可能在定义 __getitem__ 的时候遇到了问题。此外，你提到的那部分可以用一行代码来重写，这样可能更符合Python的风格。

temp = self.first
temp.link = self.first.link
self.first = _Node(item)
self.first.link = temp

前两行代码其实没什么用，因为 temp 就是 self.first，所以你说的其实就是 self.first.link = self.first.link。接下来的两行可以这样写：

self.first = _Node(item, self.first)