从链接列表中删除节点

Question

我想创建一个delete_node函数,它将列表中位置的节点删除为第一个节点的计数.到目前为止,这是我的代码:

class node:
    def __init__(self):
        self.data = None # contains the data
        self.next = None # contains the reference to the next node

class linked_list:
    def __init__(self):
        self.cur_node = None

    def add_node(self, data):
        new_node = node() # create a new node
        new_node.data = data
        new_node.next = self.cur_node # link the new node to the 'previous' node.
        self.cur_node = new_node #  set the current node to the new one.

    def list_print(self):
        node = ll.cur_node
        while node:
            print node.data
            node = node.next
    def delete_node(self,location):
        node = ll.cur_node
        count = 0
        while count != location:
            node = node.next
            count+=1
        delete node


ll = linked_list()
ll.add_node(1)
ll.add_node(2)
ll.add_node(3)

ll.list_print()

Answer 1

你不应该delete在Python中实际上是一个节点.如果没有任何东西指向节点(或者更准确地说是在Python中,没有任何东西引用它),它最终会被虚拟机破坏.

如果n是节点并且它有一个.next字段,那么:

n.next = n.next.next 

有效地丢弃n.next,使得指向的.next领域.如果是要删除的节点之前的节点,则相当于在Python中删除它.nn.next.nextn

[PS最后一段可能有点混乱,直到你在纸上画它 - 它应该变得非常清楚]

Answer 2

这是一种方法。

def delete_node(self,location):
    if location == 0:
        try:
            self.cur_node = cur_node.next
        except AttributeError:
            # The list is only one element long
            self.cur_node = None
        finally:
            return 

    node = self.cur_node        
    try:
        for _ in xrange(location):
            node = node.next
    except AttributeError:
        # the list isn't long enough
        raise ValueError("List does not have index {0}".format(location))

    try:
        node.next = node.next.next # Taken from Eli Bendersky's answer.
    except AttributeError:
        # The desired node is the last one.
        node.next = None

您没有真正使用的原因del（这让我在这里绊倒，直到我回来再次查看它）是它所做的只是删除它所调用的特定引用。它不会删除该对象。在 CPython 中，一旦不再有对象的引用，该对象就会被删除。当这里发生什么时

del node

运行时，（至少）有两个对该节点的引用：node我们要删除的命名节点和next前一个节点的属性。由于前一个节点仍在引用它，因此实际对象不会被删除，列表也不会发生任何变化。