在负索引处设置值

Question

为此 LinkedList class 我正在创建。修复我的 __setitem__ 方法体的最佳方法是什么？

class LinkedList:
    class Node:
        def __init__(self, val, prior=None, next=None):
            self.val = val
            self.prior = prior
            self.next  = next

    def __init__(self):
        self.head = LinkedList.Node(None) # sentinel node (never to be removed)
        self.head.prior = self.head.next = self.head # set up "circular" topology
        self.length = 0


### prepend and append

    def prepend(self, value):
        n = LinkedList.Node(value, prior=self.head, next=self.head.next)
        self.head.next.prior = self.head.next = n
        self.length += 1

    def append(self, value):
        n = LinkedList.Node(value, prior=self.head.prior, next=self.head)
        n.prior.next = n.next.prior = n
        self.length += 1


### subscript-based access ###

    def _normalize_idx(self, idx):
        nidx = idx
        if nidx < 0:
            nidx += len(self)
            if nidx < 0:
                nidx = 0
        return nidx

    def __getitem__(self, idx):
        """Implements `x = self[idx]`"""
        nidx = self._normalize_idx(idx)
        currNode = self.head.next
        for i in range(nidx):
            currNode = currNode.next
        if nidx >= len(self):
            raise IndexError
        return currNode.val


    def __setitem__(self, idx, value):
        """Implements `self[idx] = x`"""
        nidx = self._normalize_idx(idx)
        currNode = self.head.next
        if nidx >= len(self):
            raise IndexError
        for i in range(nidx):
            currNode = currNode.next
        currNode.val = value

    def __delitem__(self, idx):
        """Implements `del self[idx]`"""
        nidx = self._normalize_idx(idx)
        currNode = self.head.next
        if nidx >= len(self):
            raise IndexError
        for i in range(nidx):
            currNode = currNode.next
        currNode.prior.next = currNode.next #unlink currNode from its neighbors
        currNode.next.prior = currNode.prior

使用这个测试用例

     # test subscript-based access
from unittest import TestCase
import random

tc = TestCase()
data = [1, 2, 3, 4]
lst = LinkedList()
for d in data:
    lst.append(d)

for i in range(len(data)):
    tc.assertEqual(lst[i], data[i])

with tc.assertRaises(IndexError):
    x = lst[100]

with tc.assertRaises(IndexError):
    lst[100] = 0

with tc.assertRaises(IndexError):
    del lst[100]

lst[1] = data[1] = 20
del data[0]
del lst[0]

for i in range(len(data)):
    tc.assertEqual(lst[i], data[i])

data = [random.randint(1, 100) for _ in range(100)]
lst = LinkedList()
for d in data:
    lst.append(d)

for i in range(len(data)):
    lst[i] = data[i] = random.randint(101, 200)
for i in range(50):
    to_del = random.randrange(len(data))
    del lst[to_del]
    del data[to_del]

for i in range(len(data)):
    tc.assertEqual(lst[i], data[i])

for i in range(0, -len(data), -1):
    tc.assertEqual(lst[i], data[i])

我会收到断言错误，指出这些随机值最后不相等，178 != 195。如何解决这个问题？

Answer 1

您的 __delitem__ 不会减少您的长度。因此，当您在 _normalize_idx 中使用 self.length 作为负值时，它会中断。如果您在执行 del 测试之前测试负数，您可能会发现它工作正常。

tc.assertEqual(len(lst), len(data))
for i in range(50):
    to_del = random.randrange(len(data))
    del lst[to_del]
    del data[to_del]
tc.assertEqual(len(lst), len(data))   # AssertionError: 100 != 50

所以当你这样做时：

lst[-1]

这转化为从 _normalize_idx 到：

lst[99]

恰好在你的链表附近接近两倍，因为你的哨兵，它差了 1 None:

>>> print('LinkedList([', ', '.join(str(lst[i]) for i in range(len(lst))), '])')
LinkedList([ 137, 138, 101, 186, 138, 156, 126, 195, 172, 128, 119, 193, 
117, 126, 124, 106, 191, 104, 177, 141, 101, 152, 156, 184, 173, 166, 137,
169, 106, 131, 173, 119, 169, 131, 157, 106, 171, 137, 154, 162, 126, 179,
115, 144, 189, 180, 179, 193, 105, 131, None, 137, 138, 101, 186, 138, 156,
                                        ^^^^
126, 195, 172, 128, 119, 193, 117, 126, 124, 106, 191, 104, 177, 141, 101,
152, 156, 184, 173, 166, 137, 169, 106, 131, 173, 119, 169, 131, 157, 106,
171, 137, 154, 162, 126, 179, 115, 144, 189, 180, 179, 193, 105 ])

希望对您有所帮助。

在负索引处设置值

Setting values at negative indexes

python

doubly-linked-list