0
二重リンクリストクラスを作成すると、リストから値を削除する際に問題が発生しました。私はこのコードを正しく動作させるために__remove__メソッドを修正する方法についてはわかりません。私のセンチネルノードのために更新されていないループがありますか？私はこれを私の__delitem__ボディに似せようとしましたか、代わりにこのメソッドを呼び出そうとするべきですか？以下はクラスのための私のコードです。リンクリストで `__remove__`を実装する
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
### subscript-based access ###
def _normalize_idx(self, idx):
nidx = idx
if nidx < 0:
nidx += len(self)
if nidx < -1:
raise IndexError
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
self.length -= 1 #the del item has to decrease the size by 1 because of sentinel node
### single-element manipulation ###
def insert(self, idx, value):
"""Inserts value at position idx, shifting the original elements down the
list, as needed. Note that inserting a value at len(self) --- equivalent
to appending the value --- is permitted. Raises IndexError if idx is invalid."""
nidx = self._normalize_idx(idx)
currNode = self.head.next
for i in range(nidx):
currNode = currNode.next
newNode = LinkedList.Node(value, currNode.prior, currNode)
newNode.prior.next = newNode
currNode.prior = newNode
self.length += 1
def remove(self, value):
"""Removes the first (closest to the front) instance of value from the
list. Raises a ValueError if value is not found in the list."""
nidx = self._normalize_idx(0)
currNode = self.head.next
for i in range(nidx):
currNode = currNode.next
if currNode.val != value:
raise ValueError
elif currNode.val == value:
currNode.prior.next = currNode.next
currNode.next.prior = currNode.prior
self.length -= 1
def __len__(self):
"""Implements `len(self)`"""
return self.length
このクラスを次のコードを使用してテストすると、私は789というエラーが表示されます。 653デバッガがコピーされたデータは、反復処理をオフに思えるテストケースコードtc.assertEqual(data[i], lst[i])の行を指している=：
# test single-element manipulation
from unittest import TestCase
import random
tc = TestCase()
lst = LinkedList()
data = []
for _ in range(100):
to_ins = random.randrange(1000)
ins_idx = random.randrange(len(data)+1)
data.insert(ins_idx, to_ins)
lst.insert(ins_idx, to_ins)
for _ in range(25):
to_rem = data[random.randrange(len(data))]
data.remove(to_rem)
lst.remove(to_rem)
for i in range(25):
tc.assertEqual(data[i], lst[i])
with tc.assertRaises(ValueError):
lst.remove(9999)