Linked List implementation in python 3.x

Question

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!

Answer 1

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

• 301_Moved_Permanently: Due to the linear complexity of append, your extend complexity is squared. Better incorporate the looping there or introduce self._last.