Promoted
Promoted

Linked List Operations - CheatSheet

Topic: Data Structure

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 -

0subheading
  • 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
1list

Defining Linked List

2subheading

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.

3paragraph
A Linked List.
4image

Below is python code to define Node

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

Construct Linked List

7subheading
Construct Linked List.
8image
  • We use for loop, at each iteration we construct a node and update the next pointer of the previous node to the current node.
9list
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 curr.next = Node(val=arr[i]) #make next node as current curr = curr.next return head #return head
10code

Find a length of Linked List

11subheading
  • 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.
12list
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 = head.next #make next node as head return length #return length
13code
Promoted
Promoted

Find node in a Linked List

14subheading
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 = head.next #make next node as head return -1 #return -1, key not found
15code

Insert node in a Linked List

16subheading
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) node.next = 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) prev.next = node node.next = curr return head prev = curr curr = curr.next length+=1 #position is greater than length so no insertion return head
17code

Delete node in a Linked List

18subheading
def removeElements(head, key): if not head: return #Assign empty node to dummy dummy = Node(0) #Assign head as next node of dummy dummy.next = head #copy dummy to curr curr = dummy #Run a loop untill next of node of curr is NULL while curr.next: #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 curr.next.val == key: curr.next = curr.next.next else: #else just move to next node curr = curr.next #return next node of dummy return dummy.next
19code

Reverse the Linked List

20subheading
Promoted
Promoted
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 = curr.next #assign prev to next node of curr curr.next = prev #make curr as prev prev = curr #make next as curr curr = next return prev
21code

Find mid-point of Linked List

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

Detect cycle in Linked List

24subheading
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 = head.next #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 fast.next and fast.next.next: #if fast = slow, we found node if fast == slow: return True fast = fast.next.next slow = slow.next #we ran out of loop without finding cycle return False
25code

Merge two sorted Linked List

26subheading
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: head.next = a a=a.next #incase we run out of nodes in a elif b and not a: head.next = b b=b.next #if b is smaller choose b elif a.val > b.val: head.next = b b=b.next #else choose else: head.next = a a=a.next #move head by one node head = head.next #return node next to dummy return dummy.next
27code