Promoted
Promoted

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

• Find mid-point of Linked List
1list

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
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

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

• 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
13code

Promoted
Promoted

15code

17code

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

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

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