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)