# Data Structures

## Tutorial

###### What is lInked list ?
• It is a linear data structure like array.
• But unlike arrays, elements are not stored at contiguous location, but are linked using pointers.

###### Operations:
• insert(x): Inserts an element into the list.
• delete(x): Deletes the element from the list.
###### Advantages over arrays:
1. Dynamic size
2. Ease of insertion/deletion
###### Drawbacks:
1. Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists efficiently with its default implementation.
2. Extra memory space for a pointer is required with each element of the list.
3. Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.

#### Representation of Linked List

A linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then value of head is NULL.

Each node in a list consists of at least two parts:

1. data
2. Pointer / Reference to the next node
###### Approach:
• Represent Linked list using Nodes which is a Data Type that consist data and pointer to next node.
• A linked list is initiated using a head which points to None initially.
• We can insert the node in linked list at head using push() method.
• The head starts pointing to most recent node inserted at head and successive nodes points to its next node and last node points to Null.
• We can print the nodes using print_list() function.
• Optionally we can also define list_length() which calculates length of list.
###### Implementation
``````class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def list_length(self):
length = 0
while(temp):
length += 1
temp = temp.next
return length

def print_list(self):
n = self.list_length()
print('''+---+---+    '''*n)

while(temp):
print("| {} | •-|--->".format(temp.data), end="")
temp = temp.next
print("Null")

print('''+---+---+    '''*n)

def push(self, data):
new_node = Node(data)

``````

Output:

###### Complexity:
• Time: O(n)
• Auxilliary Space: O(1)

#### Applications of Linked List

• Implementation of stacks and queues data structures.
• Implementation of graphs : Adjacency list representation of graphs is most popular which is uses linked list to store adjacent vertices.
• Dynamic memory allocation : We use linked list of free blocks.
• Maintaining directory of names
• Performing arithmetic operations on long integers
• Image viewer – Previous and next images are linked, hence can be accessed by next and previous button.
• Previous and next page in web browser – We can access previous and next url searched in web browser by pressing back and next button since, they are linked as linked list.
• Music Player – Songs in music player are linked to previous and next song. you can play songs either from starting or ending of the list.

## 1. Insert a node in linked list

###### Problem:

Given a linked list need to insert a node in it.

Example:

Linked List at Start: 5–>1–>6–>7—>Null

After push(3): 3–>5–>1–>6–>7–>Null

After insert_at(4, 9): 3–>5–>1–>9–>6–>7–>Null

After append(2): 3–>5–>1–>9–>6–>7–>2–>Null

A node can be inserted in 3 ways:

• At the front of the linked list: push(data)
• At a given position: insert_at(position, data)
• At the end of the linked list: append(data)

###### Approach:
• push(data):
• Make a new_node.
• (1) Next of new_node points to node where head was poiting earlier.
• (2) Now, head points to new_node.
• append(data):
• Make a new_node
• (1) Find the last node using temp and make the next of last_node point to new_node.
• insert_at(position, data):
• If position is 0 call push to insert at front.
• Now find position to insert, need to jump only position-2 coz already at 1 and need to go 1 less
• (Example-1: if position=5, already at 1 so ust 3 jumps to reach 4th posittion.)
• Make new_node
• (1) Next of new_node points to next of temp.
• (2) Next of temp points to new_node.
###### Implementation
``````class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def print_list(self):
while(temp):
print("{}-->".format(temp.data), end="")
temp = temp.next
print("Null")

def push(self, data):
# Make a new_node.
new_node = Node(data)
# (1) Next of new_node points to node where head was poiting earlier.
# (2) Now, head points to new_node.

def append(self, data):
# Make a new_node.
new_node = Node(data)

# (1) Find the last node using temp and make the next of last_node point to new_node.
while(temp.next):
temp = temp.next
temp.next = new_node

def insert_at(self, position, data):
# If position is 0 call push to insert at front.
if(position == 0):
self.push(data)
return

# Now find position to insert, need to jump only position-2 coz already at 1 and need to go 1 less.
# (Example-1: if position=5, already at 1 so ust 3 jumps to reach 4th posittion.)
while(temp.next and position-2 > 0):
temp = temp.next
position -= 1

# Make new_node
new_node = Node(data)
# (1) Next of new_node points to next of temp.
new_node.next = temp.next
# (2) Next of temp points to new_node.
temp.next = new_node

print("Linked List at Start:")
print("\nAfter push(3):")
print("\nAfter insert_at(4, 9):")
print("\nAfter append(2):")
``````

Output

###### Complexity:
• Time: O(1)
• Auxilliary Space: O(1)

## 2. Delete a node in linked list

###### Problem:

Given a linked list need to delete a node from it. We will only delete the first occurrence of it.

Example:

Linked List at Start: 4–>7–>6–>3–>5–>Null

After delete(6): 4–>7–>3–>5–>Null

After delete(4): 7–>3–>5–>Null

After delete(2): 7–>3–>5–>Null

Element 2 not present in list.

###### Approach:
• Check if first node is the node to be deleted if it is point the head to next of temp and make temp None.
• Search for the node to be deleted using the given data in the nodes using temp and keep prev_node in store.
• Point the next of prev_node to the next of temp and make temp None if temp exists else element not present.
###### Implementation:
``````class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def print_list(self):
while(temp):
print("{}-->".format(temp.data), end="")
temp = temp.next
print("Null")

def push(self, data):
new_node = Node(data)

def delete(self, data):

# Check if first node is the node to be deleted if it is
# point the head to next of temp and make temp None.
if(temp and temp.data == data):
temp = None
return

# Search for the node to be deleted using the given data in the nodes
# using temp and keep prev in store.
while(temp):
if(temp.data == data):
break
prev = temp
temp = temp.next

# Point the next of prev to the next of temp and make temp None
# if temp exists else element not present.
if(temp):
prev.next = temp.next
temp = None
else:
print("Element {} not present in list.".format(data))

print("Linked List at Start:")
print("\nAfter delete(6):")
print("\nAfter delete(4):")
print("\nAfter delete(2):")
``````

Output:

###### Complexity:
• Time: O(n)
• Auxilliary Space: O(1)

## 3. Reverse a linked list

###### Problem:

Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing links between nodes.

Examples:

Input : 4->7->6->3->5->NULL Output : 5->3->6->7->4->NULL

Input : NULL Output : NULL

Input : 1->NULL Output : 1->NULL

###### Approach:
• Start with prev_node as None and current_node as first node.
• While current_node is not None, take the next_node as next of current_node, make the next of current_node point to prev_node and then update the prev_node as current_node and current_node as next_node.
• Make head point to prev_node which was the last node and now in reverse it becomes first.
###### Implementation:
``````class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def print_list(self):
while(temp):
print("{}-->".format(temp.data), end="")
temp = temp.next
print("Null")

def push(self, data):
new_node = Node(data)

def reverse(self):
# Take prev_node as None and current_node as first node.
prev_node = None

# While current_node doesn't become None keep going:
while(current_node):
# Take the next_node as next of current_node.
next_node = current_node.next
# Make the next of current_node point to prev_node
current_node.next = prev_node
# Update the prev_node as current_node and current_node as next_node
prev_node = current_node
current_node = next_node

# Make head point to prev_node which was the last node and now in reverse it becomes first.

print("Linked List at Start:")
print("\nAfter reverse():")
``````

Output:

###### Complexity:
• Time: O(n)
• Auxilliary Space: O(1)

## 4. Merge 2 sorted linked list

###### Problem:

Write a SortedMerge() function that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order.

SortedMerge() should return the new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

list_1: 1->4->5 list_2: is 2->3->6->8->9 merged_list: 1->2->3->4->5->6->8->9

###### Approach:
• Take 2 pointers temp_1 and temp_2 to track both lists and a stack to put the data.
• While both temp_1 and temp_2 are exists keep on going:
• If data of temp_1 is lesser temp_1 is selected and incremented else temp_2 is selected and incrmented.
• If elements are left in temp_1, push all of them to stack.
• If elements are left in temp_2, push all of them to stack.
• Now, finally make head point to None and create the linked_list from popping from stack and pushing all nodes to it.
###### Implementation:
``````class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def print_list(self):
while(temp):
print("{}-->".format(temp.data), end="")
temp = temp.next
print("Null")

def push(self, data):
new_node = Node(data)

# Take 2 pointers temp_1 and temp_2 to track both lists and a stack to put the data.
stack = []

# While both temp_1 and temp_2 are exists keep on going:
while(temp_1 and temp_2):
# If data of temp_1 is lesser temp_1 is selected and incremented
# else temp_2 is selected and incrmented.
if(temp_1.data <= temp_2.data):
stack.append(temp_1.data)
temp_1 = temp_1.next
else:
stack.append(temp_2.data)
temp_2 = temp_2.next

# If elements are left in temp_1, push all of them to stack.
while(temp_1):
stack.append(temp_1.data)
temp_1 = temp_1.next

# If elements are left in temp_2, push all of them to stack.
while(temp_2):
stack.append(temp_2.data)
temp_2 = temp_2.next

# Now, finally make head point to None and create the linked_list from popping
# from stack and pushing all nodes to it.
while(stack):
self.push(stack.pop())

print("First Sorted Linked List:")
print("\nSecond Sorted Linked List:")
print("\nMerged List:")
``````

Output:

###### Complexity:
• Time: O(n) : Whosever size is larger
• Auxilliary Space: O(n1+n2): Can be very easily done in O(1) with prev_pointer for linked_list_1.

## 5. Reverse linked list in a group of size***

###### Problem:

Given a linked list, write a function to reverse every k nodes.

Examples:

Inputs: 1->2->3->4->5->6->7->8->NULL and k = 3

Output: 3->2->1->6->5->4->8->7->NULL

Inputs: 1->2->3->4->5->6->7->8->NULL and k = 5

Output: 5->4->3->2->1->8->7->6->NULL

###### Approach:
• Take prev as None, current_node as start node and an empty stack to store at most k items.
• Till the current_node is not None:
• Take at most k elements in stack and keep moving the current_node.
• After k nodes are pushed to stack current_node will point to k+1th node but prev will still be unchanged.
• Now start popping from stack and make new_node and check:
• If prev is None, then set the head to point to prev (it will only happen for the first element when prev is None).
• Else set next of prev as new_node.
• Update the prev as new_node.
###### Implementation:
``````class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def print_list(self):
while(temp):
print("{}-->".format(temp.data), end="")
temp = temp.next
print("Null")

def push(self, data):
new_node = Node(data)

def reverse_in_group_of_size(self, k):
# Take prev as None, start the current_node from first node and
# take an empty stack to store atmost k items.
prev = None
stack = []

# Till the current_node is not None.
while(current_node):
count = 0
# Take at most k elements in stack and keep moving the current_node.
while(count<k and current_node):
stack.append(current_node.data)
current_node = current_node.next
count += 1

# After k nodes are pushed to stack current will point to k+1 the node
# but prev will still be unchanged.
# Now start popping from stack and make new_node and check:
while(stack):
new_node = Node(stack.pop())
# If prev is None, then set the head to point to prev
# (it will only happen for the first element when prev is None).
if(prev is None):
else:     # Else set next of prev as new_node
prev.next = new_node

# Update the prev as new_node.
prev = new_node

print("Linked List at Start:")
print("\nAfter reverse_in_group_of_size(3):")
``````

Output:

###### Complexity:
• Time: O(n)
• Auxilliary Space: O(K)

## 6. Add 2 numbers represented by linked list

###### Problem:

Given two numbers represented by two lists, write a function that returns sum list. The sum list is list representation of addition of two input numbers.

Examples:

Inputs: Num1 = 984 (4->8->9) Num2 = 978 (8->7->9) sum = 1962 (1->9->6->2)

Inputs: Num1 = 64957 7->5->9->4->6 Num2 = 48 8->4 sum = 65005 (6->5->0->0->5)

###### Approach:
• Take 2 pointers to track both the lists, take carry = 0 and also initialize result list.
• Now while any of temp_1 or temp_2 is there keep going.
• Get the sum: carry + first_list digit sum if exists else 0 + second_list digit sum if exists else 0.
• If sum geater than 10 then get the digit and carry separated.
• Push the digit to result list and update the temp_1 and temp_2 pointers if exists else None.
• At the end if carry still is not zero, then push carry also to the result list.
• Lastly, set the head of the list as result list’s head.
###### Implementation:
``````class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def print_list(self):
while(temp):
print("{}-->".format(temp.data), end="")
temp = temp.next
print("Null")

def push(self, data):
new_node = Node(data)

# Take 2 pointers to track both the lists, take carry = 0 and also initialize result list.
carry = 0

# Now while any of temp_1 or temp_2 is there keep going.
while(temp_1 or temp_2):
# Get the sum: carry + first_list digit sum if exists
# else 0 + second_list digit sum if exists else 0.
digit_sum = carry + (0 if not temp_1 else temp_1.data) + (0 if not temp_2 else temp_2.data)
# If sum geater than 10 then get the digit and carry separated.
if(digit_sum >= 10):
carry = 1
digit_sum -= 10
else:
carry = 0

# Push the digit to result list and update the temp_1 and temp_2 pointers if exists else None.
result.push(digit_sum)
temp_1 = None if not temp_1 else temp_1.next
temp_2 = None if not temp_2 else temp_2.next

# At the end if carry still is not zero, then push carry also to the result list.
if(carry != 0):
result.push(carry)

# Lastly, set the head of the list as result list's head.

print("Example-1:")
print("First Number: {}".format(984))
number_1.push(9)
number_1.push(8)
number_1.push(4)
print("Second Number: {}".format(978))
number_2.push(9)
number_2.push(7)
number_2.push(8)
print("Sum of both:")
number_1.print_list()

print("\nExample-2:")
print("First Number: {}".format(64957))
number_1.push(6)
number_1.push(4)
number_1.push(9)
number_1.push(5)
number_1.push(7)
print("Second Number: {}".format(48))
number_2.push(4)
number_2.push(8)
print("Sum of both:")
number_1.print_list()
``````

Output:

###### Complexity:
• Time: O(n) : Whosever size is larger
• Auxilliary Space: O(n):

## 7. Detect and remove loop in linked list***

###### Problem:

Check whether a given Linked List contains loop and if loop is present then removes the loop and returns true. And if the list doesn’t contain loop then returns false.

Examples:

Input: 1->2->3->4->5->2 Output: 1->2->3->4->5->Null

Input: 1->2->3->4. Output: False

###### Approach:
• If only 0 node or 1 node and that too has no self loop the cycle doesn’t exist.
• Initialize fast_ptr and slow_ptr to detect the loop.
• If both are equal then cycle exists and then just start the slow_ptr from head and fast_ptr from same place at same speed and check the next of both.
• The point at where next of both meet makes the loop just break using fast_ptr as we were checking next so we still have fast_ptr.
• To break loop just make next of fast_ptr as None.
###### Implementation:
``````class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def print_list(self):
while(temp):
print("{}-->".format(temp.data), end="")
temp = temp.next
print("Null")

def push(self, data):
new_node = Node(data)

def detect_and_remove_loop(self):
# If only 0 nodes or 1 node and that too  has no self.loop then cycle doesn’t exist.
if(self.head is None or self.head.next is None):
print("Cycle doesn't exist!")
return

# Initialize fast and slow pointers
slow_ptr = fast_ptr = self.head
slow_ptr = slow_ptr.next
fast_ptr = fast_ptr.next.next

# Detecting the Loop
while(slow_ptr and fast_ptr and fast_ptr.next):
if(slow_ptr == fast_ptr):
# Loop detected start removing the loop using fast_ptr and slow_ptr at same speed
# and starting slow_ptr from head and fast_ptr from meet point
while(slow_ptr.next != fast_ptr.next):
slow_ptr = slow_ptr.next
fast_ptr = fast_ptr.next

print("Cycle exists from Node-{} to Node-{}!".format(fast_ptr.data, fast_ptr.next.data))
# Make next of fast_ptr None to break loop
fast_ptr.next = None
return

slow_ptr = slow_ptr.next
fast_ptr = fast_ptr.next.next

# If reaches here mean cycle not exists
print("Cycle doesn't exist!")

print("Detect and Remove Loop Example-1:")
#Create a loop for testing
print ("After removing loop:")

print("\nDetect and Remove Loop Example-2:")
``````

Output:

###### Complexity:
• Time: O(n)
• Auxilliary Space: O(1)

Note: The problem can also be solved in O(n) using hashing the visited node address but it will take O(N) space.

## 8. Circular linked list insertion

###### Problem:

Insert a node in circular linked list.

Example:

Input: 1->2->3->4->5->1 num=6 Output: 6->1->2->3->4->5->6

###### Approach:
• Make a new_node and take current_node as starting node.
• Case-1: If this is first node being inserted make the self loop.
1. Make the next of new_node point to new_node itself (self-loop).
2. Point the head to new_node.
• Case-2: Insert at starting before head.
1. Make the next of new_node point to where head was pointing earlier.
2. Find the last node and make last_node’s next point to new_node.
3. Point the head to new_node.
###### Implementation:
``````class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def push(self, data):
new_node = Node(data)

#### Case-1: If this is first node being inserted make the self loop.
if current_node is None:
# (1) Make the next of new_node point to new_node itself (self-loop).
new_node.next = new_node
# (2) Point the head to new_node.
#### Case-2: Insert at starting before head.
else:
# (1) Make the next of new_node point to where head was pointing earlier.
# (2) Find the last node and make last_node's next point to new_node.
last_node = last_node.next
last_node.next = new_node
# (3) Point the head to new_node.

def print_list(self):
print("{}-->".format(temp.data), end="")
temp = temp.next
print("{}-->{}".format(temp.data, temp.next.data))

print("Original Circular Linked List:")
cll.push(5)
cll.push(4)
cll.push(3)
cll.push(2)
cll.push(1)
cll.print_list()
print("\nCircular Linked List After Insertion of 6:")
cll.push(6)
cll.print_list()

``````

Output:

###### Complexity:
• Time: O(1)
• Auxilliary Space: O(1)

## 9. Split a circular linked list in 2 halves***

###### Problem:

Split a circular linked list into 2 circular list of equal sizes.

If there are odd number of nodes, then first list should contain one extra.

###### Approach:
• If no nodes then just return.
• Use hare & tortoise approach to find the middle and last node using fast_ptr = fast_ptr.next.next and slow_ptr = slow_ptr.next both starting from head.
• If Even no. of nodes shift the fast_ptr to point to last using fast_ptr = fast_ptr.next.
• Make second half circular:
• start = slow_ptr.next and end = fast_ptr
• cll_2.head = fast_ptr.next = slow_ptr.next
• Make first half circular
• start = head and end = slow_ptr
###### Implementation:
``````class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def push(self, data):
new_node = Node(data)
# new_node's next will point to the previous_first_node which head was pointing earlier

# Only 1 node : self loop
if self.head is None:
new_node.next = new_node
else:
# last_node's next will point to new_node
last_node = last_node.next
last_node.next = new_node

# Now the head will point to new_node

def print_list(self):
print("{}-->".format(temp.data), end="")
temp = temp.next
print("{}".format(temp.data))

def split_into_halves(self, second_cll):
return

fast_ptr = slow_ptr = self.head
# If Odd no. of nodes in then fast_ptr->next becomes head and
# if Even no. of nodes fast_ptr->next->next becomes head
fast_ptr = fast_ptr.next.next
slow_ptr = slow_ptr.next

#======== Making 2nd half circular ========#
# Start of 2nd half: slow_ptr.next
# End of 2nd half : fast_ptr (Odd no. of nodes) || fast_ptr.next (Even no. of nodes)
if fast_ptr.next.next == self.head:
fast_ptr = fast_ptr.next
fast_ptr.next = slow_ptr.next

#======== Making 1st half circular ========#
# End of 1st half : slow_ptr)

print("Example-1(Odd Nodes): Original Circular Linked List:")
cll.push(5)
cll.push(4)
cll.push(3)
cll.push(2)
cll.push(1)
cll.print_list()
print("Circular Linked List after Splitting:")
cll.split_into_halves(second_cll)
cll.print_list()
second_cll.print_list()

print("\nExample-2(Even Nodes): Original Circular Linked List:")
cll.push(6)
cll.push(5)
cll.push(4)
cll.push(3)
cll.push(2)
cll.push(1)
cll.print_list()
print("Circular Linked List after Splitting")
cll.split_into_halves(second_cll)
cll.print_list()
second_cll.print_list()
``````

Output:

###### Complexity:
• Time: O(n)
• Auxilliary Space: O(1)

## 10. Sorted insert in circular linked list

###### Problem:

Write a function to insert a new value in a sorted Circular Linked List.

Examples:

Input: 2->4->7->8->2

Insert: 1 Output: 1-2->4->7->8->1 (At beginning)

Insert: 5 Output: 1->2->4->5->7->8->1 (In between)

Input: 9 Output: 1->2->4->5->7–>8->9->1 (At last)

###### Approach:
• Make a new_node and take current_node as starting node.
• Case-1: If this is first node being inserted make the self loop.
1. Make the next of new_node point to new_node itself (self-loop).
2. Point the head to new_node.
• Case-2: Insert at starting before head.
1. Make the next of new_node point to where head was pointing earlier.
2. Find the last node and make last_node’s next point to new_node.
3. Point the head to new_node.
• Case-3: Insert by searching (linear search) the appropriate place to insert.
1. Make the next of new_node point to where current was pointing earlier (current.next).
2. Make the next of current_node point to new_node.
###### Implementation:
``````class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def sorted_insert(self, data):
new_node = Node(data)

#### Case-1: If this is first node being inserted make the self loop.
if current_node is None:
# (1) Make the next of new_node point to new_node itself (self-loop).
new_node.next = new_node
# (2) Point the head to new_node.

#### Case-2: Insert at starting before head.
elif(data <= current_node.data):
# (1) Make the next of new_node point to where head was pointing earlier.

# (2) Find the last node and make last_node's next point to new_node.
last_node = last_node.next
last_node.next = new_node

# (3) Point the head to new_node.

#### Case-3: Insert by searching (linear search) the appropriate place to insert.
else:
while( current_node.next != self.head and data > current_node.next.data):
current_node = current_node.next

# (1) Make the next of new_node point to where current was pointing earlier (current.next).
new_node.next = current_node.next
# (2) Make the next of current_node point to new_node.
current_node.next = new_node

def print_list(self):
print("{}-->".format(temp.data), end="")
temp = temp.next
print("{}-->{}".format(temp.data, temp.next.data))

print("Original Circular Linked List:")
cll.sorted_insert(4)
cll.sorted_insert(2)
cll.sorted_insert(8)
cll.sorted_insert(7)
cll.print_list()
print("\nInsertion at Beginning (1):")
cll.sorted_insert(1)
cll.print_list()
print("\nInsertion in Between (5):")
cll.sorted_insert(5)
cll.print_list()
print("\nInsertion at Last(9):")
cll.sorted_insert(9)
cll.print_list()

``````

Output:

###### Complexity:
• Time: O(n)
• Auxilliary Space: O(1)