Refine Linked List Implementation in Python (pop, insert methods)

Question

I've recently learned how to implement linked list in Python. Can anyone help me to refine my code of implementing methods 'insert()', and 'pop()'.

pop(pos) - remove and return item at position pos.

insert(pos, item) - adds a new item to the list at position pos.

Did I consider all the cases? Thank you in advance!

EDITED: I've add test cases for pop and insert

class Node:
 def __init__(self, data):
 '''create a node'''
 self.data = data
 self.next = None
# LINKED LIST IMPLEMENTATION
class LinkedList:
 def __init__(self):
 self.head = None
 
 def isEmpty(self):
 return self.head == None
 
 def __repr__(self):
 '''ll representation
 O(n)'''
 nodes = []
 cur = self.head
 while cur:
 nodes.append(str(cur.data))
 cur = cur.next
 nodes.append("None")
 return '->'.join(nodes)
 
 
 def add(self, item):
 '''add a new item at the head of ll
 O(1)'''
 # create a new node for item
 newNode = Node(item)
 # set newnode to refer to head
 newNode.next = self.head
 # set newnode to be new head
 self.head = newNode
 
 def size(self):
 '''return #nodes
 O(n)'''
 # traverse ll and count nodes
 cur = self.head
 count = 0
 while cur != None:
 count += 1
 cur = cur.next
 return count
 
 def search(self, key):
 '''search for key in ll'''
 # traverse ll to find key
 # O(n)
 cur = self.head
 while cur:
 if cur.data == key:
 return True
 cur = cur.next
 return False
 
 def remove(self, key):
 '''remove key from ll
 O(n)'''
 # if ll empty, raise error
 if self.head == None:
 raise Exception("Linked list is empty!")
 # if head holds key, set a new head
 if self.head.data == key:
 self.head = self.head.next
 return
 
 # otherwise, traverse ll for key
 prev = None
 cur = self.head
 while cur:
 # key found
 if cur.data == key:
 prev.next = cur.next
 return
 # key not found yet, move prev and cur 1 node ahead
 prev = cur
 cur = cur.next
 # cur is None, key not present
 raise Exception('Key not present in ll!')
 
 def append(self, item):
 '''append an item to the end of ll.
 O(n)'''
 # create a new node for item, by default node points to None
 newNode = Node(item)
 # if ll is empty, set head to be new node
 if self.head == None:
 self.head = newNode
 return
 # otherwise, traverse the whole ll
 cur = self.head
 while cur.next:
 cur = cur.next
 cur.next = newNode
 
 def index(self, key):
 '''return idnex of key in ll
 O(n)'''
 # if ll empty, raise error
 if self.head == None:
 raise Exception("LL is empty!")
 # traverse ll to find key
 pos = 0
 cur = self.head
 while cur:
 if cur.data == key:
 return pos # found
 # else, move to next node
 cur = cur.next
 pos += 1
 # key not present
 return -1
 def popLastNode(self):
 '''remove and return last item of ll.
 O(n)'''
 # if ll is empty, cant pop
 if self.head == None:
 raise Exception('ll is empty!')
 # only 1 node, set ll to empty
 if self.head.next == None:
 self.head = None
 return
 # otherwise, traverse ll and remove last node
 cur = self.head
 while cur.next.next:
 cur = cur.next
 
 lastVal = cur.next.data
 cur.next = None
 return lastVal
 
 def pop(self, pos=0):
 '''remove and return item at pos
 O(n)'''
 # invalid pos
 if pos < 0 or pos >= self.size():
 raise IndexError('Index out of range!')
 
 # otherwise, traverse ll to pos
 prev = None
 cur = self.head
 idx = 0 # index of cur node
 while idx < pos:
 prev, cur = cur, cur.next
 # pop at the beginning
 if idx == 0:
 val = self.head.data
 self.head = self.head.next
 return val
 val = cur.data
 prev.next = cur.next
 return val
 
 
 def insert(self, item, pos=0):
 '''insert an item at pos.
 invalid pos > error
 pos == 0, change head'''
 # create a new node for item
 newNode = Node(item)
 # pos == 0, set new head (add method)
 if pos == 0:
 newNode.next = self.head
 self.head = newNode
 return
 
 # invalid pos
 if pos < 0 or pos >= self.size():
 raise IndexError('Index out of range!')
 
 
 # otherwise, traverse ll
 prev = None
 cur = self.head # insert between prev and cur
 idx = 0
 while idx < pos:
 prev = cur
 cur = cur.next
 idx += 1
 prev.next = newNode
 newNode.next = cur
# TEST CASES
# pop method
l5 = LinkedList()
# l5.pop(-1) - error, index out of range
# l5.pop(0) - error, index out of range
# l5.pop(5) - error, index out range
l5.add(1)
print(l5.pop()) # 1
l5.add(2)
l5.add(3)
l5.add(4)
print(l5)
# print(l5.pop(4)) - error, idx out of range
print(l5.pop(2))
print(l5)
#%%
# insert
l6 = LinkedList()
# l6.insert(2, 1) - error, index out of range
l6.insert(2)
print(l6)
# l6.insert(3, 2) - error, index out of range
# l6.insert(3, 1) - error, index out of range
l6.insert(3)
l6.insert(4, 1)
print(l6)
l6.insert(5, 1)
print(l6)

Answer 1

What you requested advice on

LinkedList.insert

You probably want to do your boundary-checking as the first thing, before any manipulation.

This is not very easily readable in my opinion:

 prev = None
 cur = self.head # insert between prev and cur
 idx = 0
 while idx < pos:
 prev = cur
 cur = cur.next
 idx += 1
 prev.next = newNode
 newNode.next = cur

I think it's better if you're more explicit with the variable names, but more importantly I think this would all be more clear with a for-loop.

This would lead to something like:

def insert(self, item, pos=0) -> None:
 """Insert `item` at `pos`.
 :raises IndexError: If position is out of range
 """
 if pos < 0 or pos >= self.size():
 raise IndexError
 elif pos == 0:
 temp = self.head
 self.head = Node(item)
 self.head.next = temp
 return
 previous, current = None, self.head
 for _ in range(pos):
 previous, current = current, current.next
 previous.next = Node(item)
 previous.next.next = current

LinkedList.pop

Here you should be able to do basically the same, so it should look something like:

def pop(self, pos=0) -> Node:
 """Remove and return `item` at `pos`.
 :raises IndexError: If position is out of range
 """
 if pos < 0 or pos >= self.size():
 raise IndexError
 elif pos == 0:
 temp = self.head
 self.head = temp.next
 return temp
 previous, current = None, self.head
 for _ in range(pos):
 previous, current = current, current.next
 previous.next = current.next
 return current

---

Other things

• Try to stick with conventions. In python people tend to use (and expect) snake_case for variables and functions, instead of camelCase.

• next is a builtin; try to avoid naming things the same as builtins (or keywords for that matter).

• Try to avoid implementing methods like size in python and rely on __len__ instead. Same goes for your boolean search method, which probably just should have been a __contains__.

• Offer a way to construct a linked list with actual contents, instead of first having to create the list and then subsequently having to add all elements to it.

• Write tests to figure out if your implementations are correct or not, instead of asking people to do so through inspection of the code. ;)

---

I'd also recommend not having custom implementations of linked lists in the first place, and instead relying on existing (standard library) data models. But I suspect that this is for school or for self-learning.

--

Finally, for your later added tests, I'd strongly recommend using a framework like pytest or unittest. You could then convert this

l5 = LinkedList()
# l5.pop(-1) - error, index out of range
# l5.pop(0) - error, index out of range
# l5.pop(5) - error, index out range

into this

def test_pop_nonexisting_index_raises_exception():
 lst = LinkedList()
 with pytest.raises(IndexError):
 lst.pop(-1)
 lst.pop(0)
 lst.pop(5)

• virus tous: Thank you for your very detailed answer. Yes I have written some test cases. i'll post right now. I considered the case pos = 0 cuz when pos=0 previous node will still be None after the while loop, hence previous.next will raise an error as None has no next attribute.
• ades: Ah, fair enough @virus-tous. I can fix that in my reply - do you want feedback also on your test cases? For future reference, by the way, it's better to make a new post instead of adding to your existing one.
• virus tous: Yes please do. I'm not sure if I consider all the cases.
• ades: @virustous I've fixed the bugs and have added some advice on test. I'm not gonna care about coverage/all cases - that would basically require me to rewrite all of your code for you, which isn't what a code review is for.
• virus tous: I got it. Thank you for your time!!