Linked List Operations - CheatSheet

This is a cheatsheet to review the Linked List data structure operations for the interview or system design. This will include approach, complexity followed by Python code for each operation. When is it appropriate to use Linked List in designing?

Cheat Sheet covers all Linked List Operations -

  • Length of Linked List, Add Node, Find Node, Replace, Delete Node to Linked List
  • Reverse the Linked List
  • Find mid-point of Linked List
  • Find cycle in LinkedList
  • Merge two Linked List

Defining Linked List


Linked List is a simple data structure that is made up of nodes. Each node has two components. One is the value and another is a pointer to the address of the next node. The next pointer of the last node of Linked List is NULL. Head is a pointer that points to the first node of Linked List.

A Linked List.

Below is python code to define Node

class Node: def __init__(self, val=0, next=None): self.val = val #Variable to store value = next #Variable to address of next node


Construct Linked List

Construct Linked List.
  • We use for loop, at each iteration we construct a node and update the next pointer of the previous node to the current node.
def constructLinkedList(arr): if not arr: #If array is empty return NULL return #Create node from 1st element of array and make it head head = Node(val=arr[0]) #copy head to return it later as we should always return head of Linked List curr = head for i in range(1,len(arr)): #create node from ith element and assign it to next of curr element = Node(val=arr[i]) #make next node as current curr = return head #return head

Find a length of Linked List

  • For every linked list problem head is given.
  • Check if head is NULL, if it is that mean Linked List length is 0.
  • To find the length we need to loop through each node until we reach NULL. We use a variable named length which will increment as we traverse through nodes.
def findLength(head): if not head: #if head is NULL return 0 return 0 length = 0 #init length to 0 while head: #run loop until head is NULL length+=1 #increment length head = #make next node as head return length #return length


Find node in a Linked List

def findNode(head, key): if not head: #if head is NULL return -1 return -1 length = 0 #init length to 0 while head: #run loop until head is NULL #if key match value of head return length if head.val == key: return length length+=1 #increment length head = #make next node as head return -1 #return -1, key not found

Insert node in a Linked List

def insertNode(head, pos, val): #if head is NULL and position is 0 #we create node and return it if not head and pos == 0: return Node(val) #if position is 0, add head to next of node created if pos == 0: node = Node(val) = head return node #Track position length = 0 #Assign head curr = head #To store previous node prev = None #Run untill curr is NULL while curr: #if position match to length #create a node, assign next of prev as node #assign next of node as curr, return head if length == pos: node = Node(val) = node = curr return head prev = curr curr = length+=1 #position is greater than length so no insertion return head

Delete node in a Linked List

def removeElements(head, key): if not head: return #Assign empty node to dummy dummy = Node(0) #Assign head as next node of dummy = head #copy dummy to curr curr = dummy #Run a loop untill next of node of curr is NULL while #If val of next node of curr match key #then skip next node by assigning #next to next node of curr to next node of curr if == key: = else: #else just move to next node curr = #return next node of dummy return

Reverse the Linked List



def reverseList(head): #Assign NULL to prev prev = None #Assign head to curr curr = head #Run loop until curr is NULL while curr: #copy next of curr to next variable next = #assign prev to next node of curr = prev #make curr as prev prev = curr #make next as curr curr = next return prev

Find mid-point of Linked List

def middleNode(head): #Assign head to fast fast = head #Run loop untill fast or next node of fast is NULL while fast and #move head by one step head = #move fast node by two step fast = #return head return head

Detect cycle in Linked List

def hasCycle(head): #if head is NULL if not head: return #Assign head to slow slow = head #Assign next node of head to fast fast = #move fast pointer by 2 steps and slow by 1 step #untill fast or next node of fast or next to next node #of fast is NULL while fast and and #if fast = slow, we found node if fast == slow: return True fast = slow = #we ran out of loop without finding cycle return False

Merge two sorted Linked List

def mergeTwoLists(a, b): #Assign empty node to head and dummy head = dummy = Node(0) #Run loop untill we traversed all nodes from a and b while a or b: #incase we run out of nodes in b if a and not b: = a #incase we run out of nodes in a elif b and not a: = b #if b is smaller choose b elif a.val > b.val: = b #else choose else: = a #move head by one node head = #return node next to dummy return