I am implementing a LinkedList in python(3.7.4) and the code of the module is below :-
LinkedList.py
class Node:
def __init__(self,value):
self.value = value
self.ref = None
class LinkedList(Node):
def __init__(self):
self.__head = None
self.__cur = None
self.__count = 0
def add(self,value):
if self.__head is None:
self.__cur = Node(value)
self.__head = self.__cur
else:
self.__cur.ref = Node(value)
self.__cur = self.__cur.ref
self.__count += 1
def getList(self):
temp = self.__head
while temp!=None:
yield temp.value
temp = temp.ref
def delete(self,value):
temp = self.__head
while temp!=None:
if temp.value == value and temp == self.__head:
self.__head = temp.ref
del temp
self.__count -= 1
break
elif temp.ref != None and temp.ref.value == value:
temp_ref = temp.ref.ref
del temp.ref
self.__count -= 1
temp.ref = temp_ref
break
temp = temp.ref
def __getitem__(self,index):
i = 0
temp = self.__head
if type(index) is int:
while temp!=None:
if i == index:
return temp.value
temp = temp.ref
i += 1
elif type(index) is slice:
if index.start is None:
start = 0
else: start = index.start
if index.stop is None:
stop = self.__count
else: stop = index.stop
if index.step is None:
step = 1
else: step = index.step
returningList = list()
while temp!=None:
if start <= i < stop:
returningList.append(temp.value)
if i==0:
i = start
for _ in range(start):
if temp != None:
temp = temp.ref
else:
i+=step
for _ in range(step):
if temp != None:
temp = temp.ref
return returningList
def __len__(self):
return self.__count
All the above functions are working well, there is no any error in this module.
but my problem is __getitem__() method. I am unable to make the exact logic for that and it is going too larger.
also it is not working for negative indices like obj[-1] returning me nothing ( len(obj) is not 0 here).
can anyone give or suggest me proper logic for __getitem__() method for code optimization and complexity reduction.
You can do this, for example:
def __getitem__(self, index):
if isinstance(index, int):
if index < 0:
index = len(self) + index
# check if `index` is valid
# search for the element as you're currently doing.
elif isinstance(index, slice):
return [self[i] for i in range(len(self))[index]]
else:
raise ValueError(f'Linked list cannot be indexed with values of type {type(index)}')
UPDATE: the code above is very concise, but it's also tremendously slow. If I'm not mistaken, it's a bit better than O(n**2), while the code below is at least 71.58 times faster (doing linkedListWith500Elements[::-1]), and it should be about O(n)!
This should be way faster because it doesn't iterate through the list each time to retrieve the next element of the slice:
class LinkedList:
...
def __iter__(self):
temp = self.__head
while temp is not None:
yield temp.value
temp = temp.ref
def __getitem__(self, index):
if isinstance(index, int):
if index < 0:
index = len(self) + index
for i, value in enumerate(self):
if i == index:
return value
raise IndexError(f'{type(self).__name__} index {index} out of range(0, {len(self)})')
elif isinstance(index, slice):
rangeOfIndices = range(len(self))[index]
isRangeIncreasing = rangeOfIndices.start <= rangeOfIndices.stop + 1 and rangeOfIndices.step > 0
rangeOfIndices = iter(rangeOfIndices) if isRangeIncreasing else reversed(rangeOfIndices)
retval = [] # you can preallocate this...
updateRetval = retval.append if isRangeIncreasing else (lambda value: retval.insert(0, value)) # ...and change this accordingly, although I haven't tested whether it'll be faster
try:
searchingForIndex = next(rangeOfIndices)
except StopIteration:
return retval
temp = self.__head
for i, element in enumerate(self):
if temp is None:
break
if i == searchingForIndex:
updateRetval(temp.value)
try:
searchingForIndex = next(rangeOfIndices)
except StopIteration:
return retval
temp = temp.ref
return retval
raise ValueError(f'{type(self).__name__} can only be indexed with integers or slices (not {type(index)})')
Preallocating the list should be around 22% faster:
...
rangeOfIndices = range(len(self))[index]
isRangeIncreasing = rangeOfIndices.start <= rangeOfIndices.stop + 1 and rangeOfIndices.step > 0
# preallocate the list...
retval = [None] * len(rangeOfIndices)
if isRangeIncreasing:
retvalIndex = 0
rangeOfIndices = iter(rangeOfIndices)
# ...and use a different update function
def updateRetval(value):
nonlocal retvalIndex
retval[retvalIndex] = value
retvalIndex += 1
else:
retvalIndex = len(retval) - 1
rangeOfIndices = reversed(rangeOfIndices)
def updateRetval(value):
nonlocal retvalIndex
retval[retvalIndex] = value
retvalIndex -= 1
try:
...