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)