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

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

## Defining Linked List | 2 | subheading |

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. | 3 | paragraph |

4 | image | |

Below is python code to define Node | 5 | paragraph |

```
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
``` | 6 | code |

Promoted Promoted ## Construct Linked List | 7 | subheading |

8 | image | |

- We use for loop, at each iteration we construct a node and update the next pointer of the previous node to the current node.
| 9 | list |

```
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
``` | 10 | code |

## Find a length of Linked List | 11 | subheading |

- 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.
| 12 | list |

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

Promoted Promoted ## Find node in a Linked List | 14 | subheading |

```
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
``` | 15 | code |

## Insert node in a Linked List | 16 | subheading |

```
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
``` | 17 | code |

## Delete node in a Linked List | 18 | subheading |

```
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
``` | 19 | code |

## Reverse the Linked List | 20 | subheading |

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
``` | 21 | code |

## Find mid-point of Linked List | 22 | subheading |

```
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
``` | 23 | code |

## Detect cycle in Linked List | 24 | subheading |

```
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
``` | 25 | code |

## Merge two sorted Linked List | 26 | subheading |

```
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
``` | 27 | code |