Python 从链表中删除节点

Removing a node from a linked list

提问by pandoragami

I would like to create a delete_node function that deletes the node at the location in the list as a count from the first node. So far this is the code I have:

我想创建一个 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()

采纳答案by Eli Bendersky

You shouldn't literally deletea node in Python. If nothing points to the node (or more precisely in Python, nothing references it) it will be eventually destroyed by the virtual machine anyway.

你不应该从字面上看delete是 Python 中的一个节点。如果没有任何内容指向该节点（或者更准确地说，在 Python 中，没有任何内容引用它），无论如何它最终都会被虚拟机销毁。

If nis a node and it has a .nextfield, then:

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

n.next = n.next.next 

Effectively discards n.next, making the .nextfield of npoint to n.next.nextinstead. If nis the node before the one you want to delete, this amounts to deleting it in Python.

有效地丢弃n.next，使指向的.next字段改为。如果是您要删除的节点之前的节点，则相当于在 Python 中删除它。nn.next.nextn

[P.S. the last paragraph may be a bit confusing until you sketch it on paper - it should then become very clear]

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

回答by Keith

Python lists arelinked lists.

Python 列表是链表。

thelist = [1, 2, 3]
# delete the second
del thelist[2]

回答by aaronasterling

Here's one way to do it.

这是一种方法。

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

The reason that you don't really use del(and this tripped me up here until I came back and looked at it again) is that all it does is delete that particular reference that it's called on. It doesn't delete the object. In CPython, an object is deleted as soon as there are no more references to it. What happens here that when

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

del node

runs, there are (at least) two references to the node: the one named nodethat we are deleting and the nextattribute of the previous node. Because the previous node is still referencing it, the actual object is not deleted and no change occurs to the list at all.

运行时，（至少）有两个对节点的引用：node我们要删除的名称和next前一个节点的属性。因为前一个节点仍在引用它，所以实际的对象并没有被删除，列表也没有发生任何变化。

回答by ASHISH RANJAN

def remove(self,data):
 current = self.head;
 previous = None;
 while current is not None:
  if current.data == data:
    # if this is the first node (head)
    if previous is not None:
      previous.nextNode = current.nextNode
    else:
      self.head = current.nextNode
  previous = current
  current = current.nextNode;

回答by flowera

Assume Linked List has more than 1 nodes. such as n1->n2->n3, and you want to del n2.

假设链表有 1 个以上的节点。比如n1->n2->n3，你想删除n2。

n1.next = n1.next.next
n2.next = None

If you want to del n1, which is the head.

如果你想del n1，这是头部。

head = n1.next
n1.next = None

回答by norbeen

# Creating a class node where the value and pointer is stored
# initialize the id and name parameter so it can be passed as Node(id, name)
class Node:
    def __init__(self, id, name):
        # modify this class to take both id and name
        self.id = id
        self.name = name
        self.next = None


# Create a class linkedlist to store the value in a node
class LinkedList:

    # Constructor function for the linkedlist class
    def __init__(self):
        self.first = None

    # This function inserts the value passed by the user into parameters id and name
    # id and name is then send to Node(id, name) to store the values in node called new_node
    def insertStudent(self, id, name):
        # modify this function to insert both id and names as in Q1
        new_node = Node(id, name)
        new_node.next = self.first
        self.first = new_node

    # We will call this function to remove the first data in the node
    def removeFirst(self):
        if self.first is not None:
            self.first = self.first.next

    # This function prints the length of the linked list
    def length(self):
        current = self.first
        count = 0
        while current is not None:
            count += 1
            current = current.next
        return count

    # This function prints the data in the list
    def printStudents(self):
        # modify this function to print the names only as in Q2.
        current = self.first
        while current is not None:
            print(current.id, current.name)
            current = current.next

    # This function lets us to update the values and store in the linked list
    def update(self, id):
        current = self.first
        while current is not None:
            if (current.id == id):
                current.id = current.id.next
            # print(current.value)
            current = current.next

    # This function lets us search for a data and flag true is it exists
    def searchStudent(self, x, y):
        current = self.first
        while current is not None:
            if (current.id == x and current.name == y):
                return True
            current = current.next

    # This function lets us delete a data from the node
    def delStudent(self,key):
         cur = self.node

        #iterate through the linkedlist
        while cur is not None: 

        #if the data is in first node, delete it
            if (cur.data == key):
                self.node = cur.next
                return

        #if the data is in other nodes delete it
            prev = cur
            cur = cur.next
            if (cur.data == key):
                prev.next = cur.next
                return

            # Initializing the constructor to linked list class

my_list = LinkedList()

# Adding the ID and Student name to the linked list
my_list.insertStudent(101, "David")
my_list.insertStudent(999, "Rosa")
my_list.insertStudent(321, "Max")
my_list.insertStudent(555, "Jenny")
my_list.insertStudent(369, "Hyman")

# Print the list of students
my_list.printStudents()

# Print the length of the linked list
print(my_list.length(), " is the size of linked list ")

# Search for a data in linked list
if my_list.searchStudent(369, "Hyman"):
    print("True")
else:
    print("False")

# Delete a value in the linked list
my_list.delStudent(101)

# Print the linked list after the value is deleted in the linked list
my_list.printStudents()