限制链表中的节点

Question

是否可以限制链表中保存的节点数？

为简单起见，请看下面的例子：

import numpy as np

class LinkedList():
    def __init__(self,data,prev):
        self.data = data
        self.prev = prev

myData_prev = None

for x in range(10):
    data = np.random.random((3,2))
    myData = LinkedList(data,myData_prev)

    myData_prev = myData

print(myData.data)
print(myData.prev.data)
print(myData.prev.prev.data)
print(myData.prev.prev.prev.data)  ## DELETED OR NO LONGER AVAILABLE

假装 'data' 相当大或范围不确定。是否可以限制保存在内存中的节点？为简单起见，假设我只需要最新的 3 个节点或 30%。

我想我有 2 个问题。首先，如何才能完成上述问题，维护链表方法。其次，有没有更好的方法不使用链表。我想我可以使用有限制的 queue/deque 或 heapq，但是相对于另一个获取数据会有点困难，对吗？

Answer 1

class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next
    def __repr__(self):
        return 'Node({}, {})'.format(self.data, self.next)

class LinkedList:      
    def __init__(self, iterable=(), maxlen=3):
        self.head = None
        self.length = 0
        if maxlen < 2:
            raise ValueError
        self.maxlen = maxlen
        for item in iterable:
            self.add(item)
    def add(self, data):
        self._check_and_remove_last()
        self.head = Node(data, self.head)
        self.length += 1
    def _check_and_remove_last(self):
        if self.length < self.maxlen:
            return
        new_tail = self.head
        while new_tail.next.next:
            new_tail = new_tail.next
        # new_tail.next is now the last Node in the Linked List
        new_tail.next = None
        self.length -= 1

删除链表的最后一个元素意味着您要么必须跟踪链表中的倒数第二个节点（这不是一件很自然的事情），要么每次都遍历整个链表.您可以通过使用双向链表并执行 self.tail.prev.next = None 之类的操作来解决此问题，或者仅使用内置的 deque 使这一切变得轻而易举

限制链表中的节点

Limit the nodes in a linked list

python

heap

queue

linked-list