从链表中删除节点

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

# 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, "Jack")

# 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, "Jack"):
    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() 

当然可以！请把你想要翻译的内容发给我，我会帮你用简单易懂的语言解释清楚。

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 属性。由于前一个节点仍然在引用这个节点，所以实际的对象并没有被删除，列表也没有发生任何变化。

Answer 3

在Python中，你不应该直接去delete一个节点。如果没有其他东西指向这个节点（更准确地说，在Python中，没有任何东西引用它），那么这个节点最终会被虚拟机自动销毁。

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

n.next = n.next.next 

实际上是丢弃了n.next，让n的.next字段指向n.next.next。如果n是你想删除的那个节点前面的节点，这样做就相当于在Python中删除了它。

[附注：最后一段可能会让人有点困惑，建议你在纸上画一下，这样就会很清楚了]