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

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

def __init__(self):

def isEmpty(self):

def __repr__(self):
'''ll representation
O(n)'''
nodes = []
while cur:
nodes.append(str(cur.data))
cur = cur.next
nodes.append("None")
return '->'.join(nodes)

O(1)'''
# create a new node for item
newNode = Node(item)
# set newnode to refer to head
# set newnode to be new head

def size(self):
'''return #nodes
O(n)'''
# traverse ll and count nodes
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)
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
return

# otherwise, traverse ll for key
prev = None
while cur:
# key found
if cur.data == key:
prev.next = cur.next
return
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
return
# otherwise, traverse the whole ll
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
raise Exception("LL is empty!")
# traverse ll to find key
pos = 0
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
raise Exception('ll is empty!')
# only 1 node, set ll to empty
return
# otherwise, traverse ll and remove last node
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
idx = 0 # index of cur node
while idx < pos:
prev, cur = cur, cur.next
# pop at the beginning
if idx == 0:
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
# create a new node for item
newNode = Node(item)
if pos == 0:
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.pop(-1) - error, index out of range
# l5.pop(0) - error, index out of range
# l5.pop(5) - error, index out range
print(l5.pop()) # 1
print(l5)
# print(l5.pop(4)) - error, idx out of range
print(l5.pop(2))
print(l5)

#%%
# insert
# 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)


#### 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:
return

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:
return temp

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():
with pytest.raises(IndexError):
lst.pop(-1)
lst.pop(0)
lst.pop(5)

• 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. Jan 5 at 17:36
• 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.