Problem
I took this as a challenge and implemented linked list data structure in python
class Node:
def __init__(self, data, nxt=None):
self.data = data
self.next = nxt
class LinkedList:
def __init__(self, arr=None):
if arr in [None, []]:
self.head = None
else:
self.arrayToLinked(arr)
def arrayToLinked(self, arr):
self.head = Node(arr[0])
temp = self.head
for i in range(1, len(arr)):
temp.next = Node(arr[i])
temp = temp.next
def append(self, new_val):
new_node = Node(new_val)
if self.head is None:
self.head = new_node
return
last = self.head
while last.next is not None:
last = last.next
last.next = new_node
def linkedToArray(self):
arr = []
temp = self.head
while temp is not None:
arr.append(temp.data)
temp = temp.next
return arr
def removeDuplicates(self):
pass
def sort(self):
arr = []
temp = self.head
while temp is not None:
arr.append(temp.data)
temp = temp.next
self.arrayToLinked(sorted(arr))
def index(self, val):
temp = self.head
i = 0
while temp is not None:
if temp.data == val: return i
i += 1
return -1
def min(self):
mini = self.head.data
temp = self.head
while temp is not None:
if mini > temp.data:
mini = temp.data
return mini
def max(self):
maxi = self.head.data
temp = self.head
while temp is not None:
if maxi < temp.data:
maxi = temp.data
return maxi
def push(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
@staticmethod
def insertNode(prev_node, new_val):
new_node = Node(new_val)
new_node.next = prev_node.next
prev_node.next = new_node
def insertIndex(self, pos, data):
data = Node(data)
i = 0
temp = self.head
while i < pos:
if temp is None or temp.next is None:
return
temp = temp.next
i += 1
dum = temp
temp = data
temp.next = dum
self.head = temp
def delete(self, key):
temp = self.head
if temp is not None and temp.data == key:
self.head = temp.next
return
prev = None
while temp is not None:
if temp.data == key:
break
prev = temp
temp = temp.next
if temp is None:
return
prev.next = temp.next
def deleteIndex(self, pos):
if self.head is None:
return
temp = self.head
if pos == 0:
self.head = temp.next
return
for i in range(pos - 1):
temp = temp.next
if temp is None:
break
if temp is None or temp.next is None:
return
val = temp.next.next
temp.next = None
temp.next = val
def pop(self, pos):
if self.head is None:
return
temp = self.head
if pos == 0:
self.head = temp.next
return
for i in range(pos - 1):
temp = temp.next
if temp is None:
break
if temp is None or temp.next is None:
return
val = temp.next.next
pop_val = temp.next
temp.next = None
temp.next = val
return pop_val
def count(self, element):
temp = self.head
count = 0
while temp is not None:
if temp.data == element:
count += 1
temp = temp.next
return count
def remove(self, element):
temp = self.head
while temp is not None:
if temp.next is not None and temp.next.data == element:
dum = temp.next.next
temp.next = None
temp.next = dum
temp = temp.next
def isLoop(self):
s = set()
temp = self.head
while temp:
if temp in s:
return True
s.add(temp)
temp = temp.next
return False
def findLoop(self):
s = set()
temp = self.head
while temp:
if temp in s:
return temp
s.add(temp)
temp = temp.next
def createLoop(self, data):
ind = self.index(data)
last = self.head
while last.next is not None:
last = last.next
last.next = self[ind]
def reverse(self):
result = None
temp = self.head
while temp:
result = Node(temp.data, temp)
temp = temp.next
self.head = result
def len(self):
c = 0
temp = self.head
while temp is not None:
c += 1
temp = temp.next
return c
def clear(self):
self.head = None
def copy(self):
return self.arrayToLinked(self.linkedToArray())
def __getitem__(self, index):
arr = []
temp = self.head
while temp is not None:
arr.append(temp)
temp = temp.next
return arr[index]
def getValues(self, index):
arr = []
temp = self.head
while temp is not None:
arr.append(temp.data)
temp = temp.next
return arr[index]
def print(self):
arr = []
m = self.head
while m is not None:
arr.append(str(m.data))
m = m.next
print(' -> '.join(arr))
I want to make the code as short as possible, while maintaining neatness.
Thanks!
Solution
This code is pretty neat. One major improvement would be the addition of some magic methods, like __iter__, __getitem__, __setitem__ and __str__.
iter
The magic method you’ll use the most wil be __iter__. It will allow you to do for node in linked_list
def __iter__(self):
current = self.head
while current:
yield current
current = current.next
If there is the possibility for loops in the linked list, this will go on forever. In that case, it might be best to raise a specific exception
class LoopListError(Exception): pass
...
def __iter__(self):
current = self.head
visited = set()
while current:
if current in visited:
raise LoopListError("f{current} is part of a loop")
set.add(current)
yield current
current = current.next
Make sure never to change the list while iterating over it. This might lead to strange errors.
__len__
len(self) can be renamed to __len_, so you can do len(linked_list) . It can also be implemented like this:
def __len__(self):
return sum(1 for _ in self)
If there is a loop in the list, this wil raise the LoopListError. If, in that case, you want the length of the non-looped part of the list, then you can do:
def __len__(self):
count = 0
try:
for _ in self:
count += 1
except LoopListError:
pass
return count
If you want it to iterate over the nodes values instead of the nodes themselves, you can just change the yield current to yield current.data. Whichever option is best depends on the design of the rest and the use of this list.
I think it’s cleaner to provide a separate iter_values method:
def iter_values(self):
return (node.data for node in self)
You don’t need a specific min and max method any more, but can use the builtins
__getitem__
In your implementation, you load the complete linked list into a builtin list. This is not needed. You can use enumerate to loop over the elements, and keep track of the index
def __getitem__(self, index):
for i, node in enumerate(self):
if i == index:
return node
raise IndexError(f"{index} not found")
This works for positive indices. If you also want to accept negative indices, you need to convert the negative index to a positive one:
def __getitem__(self, index):
if index < 0:
l = len(self)
if abs(index) > l:
raise IndexError(f"{index} out of range")
index = l - index
for i, node in enumerate(self):
if i == index:
return node
raise IndexError(f"{index} out of range")
__bool__
In python, by convention, empty containers are falsey. Their __bool__ function returns False.
def __bool__(self):
return self.head is not None
arrayToLinked
In python, it’s seldomly necessary to loop over an index. Instead of for i in range(1, len(arr)), you can use for value in arr:. This only needs a bit of special handling for the head of the list.
Your arrayToLinked method corresponds to list.extend(iterable) on an ordinary list. I only clears the list first. My suggestion would be to skip the clearing of the list. If the user wants a fresh list, he can either explicitly clear it himself, or call the constructor while providing the iterable:
def extend(self, iterable):
it = iter(iterable)
if not self:
try:
self.head = Node(next(it))
except StopIteration:
self.head = None
for value in it:
self.append(Node(value))
def __init__(self, iterable=None):
self.head = None
if iterable is not None:
self.extend(iterable)
As409_conflict noted in the comments, this might not be the most performant method to use
if you provide a tail method,
def tail(self):
"""
returns the last element in the linked list.
"""
if self.head is None:
return None
for current in self:
pass
return current
def extend(self, iterable):
it = iter(iterable)
if not self:
try:
self.head = Node(next(it))
except StopIteration:
return
current = self.tail()
for value in it:
current.next = current = Node(value)
copy
The copy then becomes as simple as
def copy(self):
return type(self)(self.iter_values())
sort
def sort(self):
sorted_values = sorted(self.iter_values())
self.clear()
self.extend(sorted_values )
Or, If you want to return a new instance
def sort(self):
return type(self)(sorted(self.iter_values()))
In general, I suggest you take a look at the Python data model, and what methods a standard list provides, and thy to mimic those behaviours