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 what I would assume is my getitem or setitem method body.
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[nidx]
if nidx >= len(self):
raise IndexError
currNode = 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+1, len(self)):
self[i-1] = self[i]
del self[len(self)-1]
Testing this code using:
# 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])
I'd get an error saying 1 != 20. 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. And I'm not sure where this 20 value is coming from.
