I'm creating a LinkedList class to get a better feel for the python language and its doubly linked nodes. My overall task being to not make use of python's built-in list data structure, while also trying to optimize the time efficiency of the code. What would be the best way to go about fixing the getitem, and setitem methods?
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
return currNode.val
else:
raise IndexError
def __setitem__(self, idx, value):
"""Implements `self[idx] = x`"""
assert(isinstance(idx, int))
nidx = self._normalize_idx(idx)
if nidx >= len(self):
raise IndexError
self[nidx] = value
Testing this code using:
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]
I'd get an error saying the IndexError wasn't rasied. Writing these class methods always seems to trip me up, what might I be missing? I'm not exactly sure how this differs from the typical array backed list
Aucun commentaire:
Enregistrer un commentaire