从链表中删除节点

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

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

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

n.next = n.next.next 

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

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

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

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

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;

Answer 6

Python 列表是链接列表。

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

Answer 7

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

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

如果要删除n1，也就是头部。

head = n1.next
n1.next = None

Answer 8

我就是这样做的。

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