从链表中删除节点

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

- pandoragami

---

好的，你有什么问题吗？在 StackOverflow 上提出具体问题 - 不要只给我们一些代码并说“这是我想做的”。例如，你遇到了什么问题？ - Amber

我理解C++中的算法，我的问题是如何删除一个节点对象？基本上就是创建new_node的相反操作。 - pandoragami

如果你只是理解了“C++”中的算法，那么你并没有真正理解这个算法。你只是知道如何在C++中实现它。如果你真正理解了这个算法，那么你会问一个关于Python语法的具体问题。 - aaronasterling

@aaronasterling 没错，删除节点的 Python 语法是什么？ - pandoragami

@lost_with_coding，Python中不存在销毁对象的概念。垃圾回收过程会自动处理不再被引用的对象。但是，由于Python比C++更高级，您无需自己实现这些列表。它已经存在：list()。 - Ber

Answer 1

在Python中，您不应该字面上删除节点。如果没有任何指向该节点的引用（或更准确地说，在Python中没有任何引用它），它最终将被虚拟机销毁。

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

n.next = n.next.next 

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

[附注：最后一段可能有点困惑，直到你在纸上画出它 - 然后它应该变得非常清晰]

- Eli Bendersky

---

最佳答案。 - Galaxy

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属性引用。由于前一个节点仍然引用该节点，因此实际对象不会被删除，列表也不会发生任何变化。

- aaronasterling

---

这之后你如何连接这两部分？ - Keith

@Keith，你不需要这样做，请仔细阅读他写的内容：“我真的会称之为修剪，因为它也删除了它后面的所有节点。” - pandoragami

@lost 但这并不等同于从列表中删除节点，这是最初的问题。因此，这不是一个真正有效的答案。它需要更多的代码。 - Keith

@Keith，就像我说的那样，这只是OP发布的算法。 - aaronasterling

我一定很累，没有注意力。抱歉。 - Keith

Answer 3

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

- norbeen

Answer 4

我使用递归函数来执行pop()函数，因为使用引用的迭代方式不太好。所以下面是代码。希望这能帮到你！ ;)

class Node:

  def __init__(self, data=0, next=None):
    self.data = data
    self.next = next

  def __str__(self):
    return str(self.data)


class LinkedList:

    def __init__(self):
        self.__head = None
        self.__tail = None
        self.__size = 0

    def addFront(self, data):
        newNode = Node(data, self.__head)
        if (self.empty()):
            self.__tail = newNode  
        self.__head = newNode
        self.__size += 1

    def __str__(self):
        # retorno deve ser uma string:
        s = "["
        node = self.__head
        while node:
            s += str(node.data) + ' ' if node.next != None else str(node.data)
            node = node.next
        return s + "]"



    def __recPop(self, no, i, index):
        if (i == index-1):

            if (index == self.size() - 1):
                self.__tail = no
            try:
                no.next = no.next.next; 
            except AttributeError:
                no.next  = None
            
        else: 
            self.__recPop(no.next, i+1, index)

        
    def pop(self, index=0):

        if (index < 0 or index >= self.__size or self.__size == 0):
            return

        if (index == 0):
            try:
                self.__head = self.__head.next
            except AttributeError:
                self.__head  = None
                self.__tail  = None
            
        else:
            self.__recPop(self.__head, 0, index)
        
        self.__size -= 1
                
    def front(self):
        return self.__head.data

    def back(self):
        return self.__tail.data

    def addBack(self, data):
        newNode = Node(data)
        if (not self.empty()):
            self.__tail.next = newNode
        else:
            self.__head = newNode

        self.__tail = newNode
        self.__size += 1

    def empty(self):
        return self.__size == 0

    def size(self):
        return self.__size

    

    def __recursiveReverse(self, No):
        if No == None : return
        self.__recursiveReverse(No.next)
        print(No, end=' ') if self.__head != No else print(No, end='')

    def reverse(self):
        print('[', end='')
        self.__recursiveReverse(self.__head)
        print(']')

- Rafael Guimarães

Answer 5

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;

- ASHISH R

---

虽然这段代码可能回答了问题，但提供有关它如何以及/或为什么解决问题的附加上下文将改善答案的长期价值。请阅读此如何回答以提供高质量的答案。 - thewaywewere

这种情况是当链表以两个或更多节点开始，且这些节点的 .data == data 时被忽略了。 - Pranav Kasetti

Answer 6

这是我做的方法。

def delete_at_index(self, index):
    length = self.get_length()
    # Perform deletion only if the index to delete is within or equal to the length of the list.
    if index<=length:
        itr = self.head
        count = 0

        # If the index to delete is zeroth.
        if count==index:
            self.head = itr.next
            return
        
        while itr.next:
            if count==index-1:
                try:
                    # If the index to delete is any index other than the first and last.
                    itr.next = itr.next.next
                except:
                    # If the index to delete is the last index.
                    itr.next = None
                return
            count+=1
            itr = itr.next

def get_length(self):
    itr = self.head
    count = 0
    while itr:
        count += 1
        itr = itr.next
    return count

- laplace

Answer 7

假设链表有多于1个节点，例如n1->n2->n3，你想要删除n2。

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

如果你想删除头部的n1。

head = n1.next
n1.next = None

- flowera

Answer 8

Python列表是链表。

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

- Keith

---

是的，在Python中不需要构建链表。它们已经在语言核心中提供了。 - Ber

Python的列表不是链表。具体来说，它们没有任何方法可以前进到下一个元素，并且可以通过索引访问。 - aaronasterling

i = iter(thelist); i.next(); i.next(); el3 = thelist[3] 我=iter(thelist); 我.next(); 我.next(); el3=thelist[3] - Keith

@Keith，那是一个 _iterator_。列表是一个 _iterable_，这意味着您可以从中构造一个迭代器。即使使用 i = iter(list_)，它的 next 方法也返回元素而不是节点。也就是说，如果我不能执行 e=i.next(); e2=e.next()。它们是两件不同的事情。我同意在Python中使用链表很愚蠢，但是你的答案事实上是错误的。 - aaronasterling

我知道，但我正在做这个作为练习，你是正确的，但这不是我当前问题所需要的。 - pandoragami