删除链表指定索引范围内的项目

Question

在我的链表中，我编写了一个函数drop_between，用于删除指定范围内的节点。

除drop_between功能外的所有功能都可以正常工作。

我的预期输出：

sample = Deque()
sample.push_front(3)
sample.push_front(2)
sample.push_front(1)
sample.push_front(0)
linked list = [0, 1, 2, 3]
sample.drop_between(1,3)
linked list = [0, 3] # 1, 2 removed

但是，我的函数会删除drop_between中指定的所有内容，除了传入的第一个数字(即开头(。

我的链表函数文件：

class Node:
    """
    Initialize empty node
    """
    def __init__(self, data, prev = None, next = None):
        self.data = data
        self.next = next
        self.prev = prev
class Deque:
    """
    A double-ended queue
    """
    def __init__(self):
        """
        Initializes an empty Deque
        """
        self.head = None
        self.tail = None
        self.size = 0
    def __len__(self):
        """
        Computes the number of elements in the Deque
        :return: The size of the Deque
        """
        return self.size
    def push_front(self, e): 
        """
        Inserts an element at the front of the Deque
        :param e: An element to insert
        """
        new_head = Node(data = e, next = self.head)
        if len(self) == 0:
            self.tail = new_head
        if self.head:
            self.head.prev = new_head
        self.head = new_head
        self.size += 1
    def drop_between(self, start, end): #need help with this function
        """
        Deletes elements from the Deque that within the range [start, end)
        :param start: indicates the first position of the range
        :param end: indicates the last position of the range(does not drop this element)
        """
        cur_index = 0
        if (start > end):
            raise IndexError
        if (start < 0):
            raise IndexError
        curr = self.head
        while curr.next:
            last_node = curr
            curr = curr.next
            if ((cur_index >= start) and (cur_index < end)):
                print("here", cur_index)
                last_node.next = curr.next.next
                curr.next.next.prev = last_node.next
            cur_index += 1
    def listprint(self, node):
        """
        Prints each element of the node front to back
        :param node:
        """
        while (node is not None):
            print(node.data)
            last = node
            node = node.next

我的主要文件：

def main():
    D = Deque()
    D.push_front(9)
    D.push_front(8)
    D.push_front(7)
    D.push_front(6)
    D.push_front(5)
    D.push_front(4)
    D.push_front(3)
    D.push_front(2)
    D.push_front(1)
    D.push_front(0)
    D.drop_between(4,7)
    D.listprint(D.head)

我的 main 的输出显示数字 0-4 和 7-9(包括 0-4 和 7-9(，但 4 的输出出乎意料。如何正确取消链接链表中的 4 个？

Answer 1

请注意

，collections已经实现了deque

考虑到这一点，您的任务最终非常简单：

from collections import deque
def drop_between(d, start, end):
    d.rotate(-start)
    for __ in range(end-start):
        d.popleft()
    d.rotate(+start)

d = deque(n for n in range(20))
print(d)
drop_between(d, 5, 9)
print(d)

但是，如果您不被允许使用此外部源，我建议您编写类似的逻辑。

Answer 2

将

drop_between函数替换为：

def drop_between(self, start, end): #need help with this function
    """
    Deletes elements from the Deque that within the range [start, end)
    :param start: indicates the first position of the range
    :param end: indicates the last position of the range(does not drop this element)
    """
    cur_index = 0
    if (start > end):
        raise IndexError
    if (start < 0):
        raise IndexError
    #assumption: start node != head
    prev_to_start_node = self.get_node_by_index(start-1)
    end_node = self.get_node_by_index(end)
    prev_to_start_node.next = end_node
    end_node.prev = prev_to_start_node
def get_node_by_index(self,index):
    i = 0
    curr = self.head
    while i < index and curr.next:
        curr = curr.next
        i+=1
    return curr

请注意，我添加了get_node_by_index，因此，如果要删除它，则需要相应地替换代码。