Scribd
Upload
5 views17 pages

Code It

The document provides various implementations of data structures and algorithms in Python, including linked lists (singly, doubly, and circular), stacks, queues, and sorting algorithms (bubble sort, insertion sort, selection sort, shell sort, merge sort, quick sort). It also includes examples of traversing, inserting, deleting nodes in linked lists, and performing binary search. Each section contains code snippets demonstrating the functionality and usage of these data structures and algorithms.

Uploaded by

cs0814
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views17 pages

Code It

The document provides various implementations of data structures and algorithms in Python, including linked lists (singly, doubly, and circular), stacks, queues, and sorting algorithms (bubble sort, insertion sort, selection sort, shell sort, merge sort, quick sort). It also includes examples of traversing, inserting, deleting nodes in linked lists, and performing binary search. Each section contains code snippets demonstrating the functionality and usage of these data structures and algorithms.

Uploaded by

cs0814
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Traversal of a Linked List

class Node:

def __init__(self, data):

[Link] = data

[Link] = None

def traverseAndPrint(head):

currentNode = head

while currentNode:

print([Link], end=" -> ")

currentNode = [Link]

print("null")

# Creating nodes

node1 = Node(7)

node2 = Node(11)

node3 = Node(3)

node4 = Node(2)

node5 = Node(9)

# Linking nodes

[Link] = node2

[Link] = node3

[Link] = node4

[Link] = node5

# Traversing and printing the list


traverseAndPrint(node1)

2) Find The Lowest Value in a Linked List

class Node:

def __init__(self, data):

[Link] = data

[Link] = None

def findLowestValue(head):

if head is None:

return None # handle empty list

minValue = [Link]

currentNode = [Link]

while currentNode:

if [Link] < minValue:

minValue = [Link]

currentNode = [Link]

return minValue

# Creating nodes

node1 = Node(7)

node2 = Node(11)

node3 = Node(3)

node4 = Node(2)

node5 = Node(9)
# Linking nodes

[Link] = node2

[Link] = node3

[Link] = node4

[Link] = node5

# Printing the lowest value

print("The lowest value in the linked list is:", findLowestValue(node1))

Delete a Node in a Linked List


class Node:

def __init__(self, data):

[Link] = data

[Link] = None

def traverseAndPrint(head):

currentNode = head

while currentNode:

print([Link], end=" -> ")

currentNode = [Link]

print("null")

def deleteSpecificNode(head, nodeToDelete):

# If the head itself is the node to delete

if head == nodeToDelete:

return [Link]

currentNode = head

# Traverse until we find the node before the one we want to delete
while [Link] and [Link] != nodeToDelete:

currentNode = [Link]

# If the node wasn't found

if [Link] is None:

return head

# Bypass the node to delete

[Link] = [Link]

return head

# Creating nodes

node1 = Node(7)

node2 = Node(11)

node3 = Node(3)

node4 = Node(2)

node5 = Node(9)

# Linking nodes

[Link] = node2

[Link] = node3

[Link] = node4

[Link] = node5

# Before deletion

print("Before deletion:")

traverseAndPrint(node1)

# Deleting node4 (which has value 2)


node1 = deleteSpecificNode(node1, node4)

# After deletion

print("\nAfter deletion:")

traverseAndPrint(node1)

Insert a Node in a Linked List


class Node:

def __init__(self, data):

[Link] = data

[Link] = None

def traverseAndPrint(head):

currentNode = head

while currentNode:

print([Link], end=" -> ")

currentNode = [Link]

print("null")

def insertNodeAtPosition(head, newNode, position):

if position == 1:

[Link] = head

return newNode

currentNode = head

for _ in range(position - 2):

if currentNode is None:

break

currentNode = [Link]
if currentNode is None:

print("Position is out of bounds.")

return head

[Link] = [Link]

[Link] = newNode

return head

# Creating nodes

node1 = Node(7)

node2 = Node(3)

node3 = Node(2)

node4 = Node(9)

# Linking nodes

[Link] = node2

[Link] = node3

[Link] = node4

print("Original list:")

traverseAndPrint(node1)

# Insert a new node with value 97 at position 2

newNode = Node(97)

node1 = insertNodeAtPosition(node1, newNode, 2)

print("\nAfter insertion:")

traverseAndPrint(node1)
IMPLEMENTATION OF DOUBLY LINKED LIST
Insertion at beginning:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

class DoublyLinkedList:
def __init__(self):
[Link] = None

# Insertion at the beginning


def insert_at_beginning(self, data):
new_node = Node(data)
if [Link] is None:
[Link] = new_node
else:
new_node.next = [Link]
[Link] = new_node
[Link] = new_node

# Display the list


def display(self):
temp = [Link]
while temp:
print([Link], end=" <-> ")
temp = [Link]
print("None")

# Example usage
dll = DoublyLinkedList()
dll.insert_at_beginning(6)
dll.insert_at_beginning(8)
dll.insert_at_beginning(7)

print("Doubly Linked List after insertions at beginning:")


[Link]()

Python Code(Insertion at Nth Position)


class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
class DoublyLinkedList:
def __init__(self):
[Link] = None

def insert_at_position(self, data, position):


new_node = Node(data)
if position == 1:
if [Link]:
new_node.next = [Link]
[Link] = new_node
[Link] = new_node
return

temp = [Link]
for _ in range(position - 2):
if temp is None:
print("Position out of range")
return
temp = [Link]

if temp is None:
print("Position out of range")
return

new_node.next = [Link]
new_node.prev = temp

if [Link]:
[Link] = new_node

[Link] = new_node

def display(self):
temp = [Link]
while temp:
print([Link], end=" <-> ")
temp = [Link]
print("None")

# Example usage
dll = DoublyLinkedList()
dll.insert_at_position(7, 1) # Insert at position 1
dll.insert_at_position(8, 2) # Insert at position 2
dll.insert_at_position(6, 2) # Insert at position 2 (between 7 and 8)
[Link]()
Python Code(Insertion at End)
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

class DoublyLinkedList:
def __init__(self):
[Link] = None

def insert_at_end(self, data):


new_node = Node(data)
if [Link] is None:
[Link] = new_node
else:
temp = [Link]
while [Link]:
temp = [Link]
[Link] = new_node
new_node.prev = temp

def display(self):
temp = [Link]
while temp:
print([Link], end=" <-> ")
temp = [Link]
print("None")

# Example usage
dll = DoublyLinkedList()
dll.insert_at_end(7)
dll.insert_at_end(8)
dll.insert_at_end(6)
dll.insert_at_end(9)
[Link]()

IMPLEMENTATION OF CIRCULAR LINKED LIST


class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

# Creating nodes
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)

# Linking nodes manually


[Link] = node2
[Link] = node1

[Link] = node3
[Link] = node2

[Link] = node4
[Link] = node3

# Forward traversal
print("\nTraversing forward:")
currentNode = node1
while currentNode:
print([Link], end=" -> ")
currentNode = [Link]
print("null")

# Backward traversal
print("\nTraversing backward:")
currentNode = node4
while currentNode:
print([Link], end=" -> ")
currentNode = [Link]
print("null")

Implementation of Stack and Queue ADTs


# Stack (LIFO)
stack = []
[Link]('a')
[Link]('b')
[Link]('c')

print('Initial stack:')
print(stack)

print('\nElements popped from stack:')


print([Link]()) # 'c'
print([Link]()) # 'b'
print([Link]()) # 'a'
print('\nStack after elements are popped:')
print(stack)

# Queue (FIFO)
queue = []
[Link]('a')
[Link]('b')
[Link]('c')

print("\nInitial queue:")
print(queue)

print("\nElements dequeued from queue:")


print([Link](0)) # 'a'
print([Link](0)) # 'b'
print([Link](0)) # 'c'

print("\nQueue after removing elements:")


print(queue)

# List - Extend Operation


List = [1, 2, 3, 4]

print("\nInitial List:")
print(List)

[Link]([8, 'Geeks', 'Always'])

print("\nList after performing Extend Operation:")


print(List)

Bubble sort:
def bubble_sort(alist):
for i in range(len(alist) - 1, 0, -1):
no_swap = True
for j in range(0, i):
if alist[j + 1] < alist[j]:
alist[j], alist[j + 1] = alist[j + 1], alist[j]
no_swap = False
if no_swap: # Optimization: stop early if no swaps
return

# Take input from user


alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist] # Convert input to integers

bubble_sort(alist)
print('Sorted list:', alist)

IMPLEMENTATION OF INSERTION SORT

def insertion_sort(alist):
'''Sorts the list using insertion sort.'''
for i in range(1, len(alist)):
key = alist[i] # Element to be inserted into the sorted part
j=i-1
# Move elements of alist[0..i-1] that are greater than key
while j >= 0 and alist[j] > key:
alist[j + 1] = alist[j]
j -= 1
# Insert the key into the correct position
alist[j + 1] = key

# Example Usage:
alist = input("Enter a list of numbers (space-separated): ").split()
alist = [int(x) for x in alist] # Convert strings to integers
insertion_sort(alist)
print("Sorted list:", alist)

Selection sort:

def selection_sort(alist):
for i in range(0, len(alist) - 1):
smallest = i
for j in range(i + 1, len(alist)):
if alist[j] < alist[smallest]:
smallest = j
# Swap
alist[i], alist[smallest] = alist[smallest], alist[i]

# Take input from user


alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist] # Convert input to integers

selection_sort(alist)
print('Sorted list:', alist)
shell sort
def shell_sort(alist):
'''Sorts the list using the Shell Sort algorithm.'''
n = len(alist)
# Start with a large gap, then reduce the gap
gap = n // 2
while gap > 0:
# Perform an insertion sort with the current gap
for i in range(gap, n):
key = alist[i]
j=i
while j >= gap and alist[j - gap] > key:
alist[j] = alist[j - gap]
j -= gap
alist[j] = key
# Reduce the gap
gap //= 2

# Example Usage:
alist = input("Enter a list of numbers (space-separated): ").split()
alist = [int(x) for x in alist] # Convert strings to integers
shell_sort(alist)
print("Sorted list:", alist)

IMPLEMENTATION OF MERGE SORT


def merge_sort(alist, start, end):
'''Sorts the list from indexes start to end - 1 inclusive.'''
if end - start > 1:
mid = (start + end) // 2
merge_sort(alist, start, mid)
merge_sort(alist, mid, end)
merge_list(alist, start, mid, end)

def merge_list(alist, start, mid, end):


left = alist[start:mid]
right = alist[mid:end]
k = start
i=0
j=0

# Merge the two halves


while (start + i < mid and mid + j < end):
if (left[i] <= right[j]):
alist[k] = left[i]
i += 1
else:
alist[k] = right[j]
j += 1
k += 1

# If there are any remaining elements in the left half


while start + i < mid:
alist[k] = left[i]
i += 1
k += 1

# If there are any remaining elements in the right half


while mid + j < end:
alist[k] = right[j]
j += 1
k += 1

# Taking input from the user


alist = input('Enter the list of numbers (space-separated): ').split()
alist = [int(x) for x in alist] # Convert input to integers

# Perform merge sort on the entire list


merge_sort(alist, 0, len(alist))

# Output the sorted list


print('Sorted list:', alist)

QUICK SORT:
def quicksort(alist, start, end):
'''Sorts the list from indexes start to end - 1 inclusive.'''
if end - start > 1: # Only proceed if there are at least two elements
p = partition(alist, start, end) # Partition the list
quicksort(alist, start, p) # Recursively sort the left part
quicksort(alist, p + 1, end) # Recursively sort the right part

def partition(alist, start, end):


pivot = alist[start] # Choose the pivot element (first element)
i = start + 1 # Start pointer
j = end - 1 # End pointer
while True:
# Move i to the right
while i <= j and alist[i] <= pivot:
i += 1
# Move j to the left
while i <= j and alist[j] >= pivot:
j -= 1
if i <= j:
# Swap i and j
alist[i], alist[j] = alist[j], alist[i]
else:
# Place pivot in the correct position
alist[start], alist[j] = alist[j], alist[start]
return j # Return the position of the pivot

# Input and execution


alist = input('Enter the list of numbers (space-separated): ').split()
alist = [int(x) for x in alist] # Convert input to list of integers
quicksort(alist, 0, len(alist)) # Perform quicksort
print('Sorted list: ', alist)

binary search:
def binarySearch(target, lst):
left = 0
right = len(lst) - 1
iterations = 0 # local counter instead of global
while left <= right:
iterations += 1
mid = (left + right) // 2
if target == lst[mid]:
return mid, iterations
elif target < lst[mid]:
right = mid - 1
else:
left = mid + 1
return -1, iterations

if __name__ == '__main__':
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14]
target = 12
answer, iterations = binarySearch(target, lst)
if answer != -1:
print(f'Target {target} found at position {answer} in {iterations} iterations')
else:
print('Target not found')
LINEAR SEARCH
def linearSearch(target, lst):
position = 0
iterations = 0 # local counter instead of global
while position < len(lst):
iterations += 1
if target == lst[position]:
return position, iterations
position += 1
return -1, iterations

if __name__ == '__main__':
lst = [1, 2, 3, 4, 5, 6, 7, 8]
target = 3
answer, iterations = linearSearch(target, lst)
if answer != -1:
print(f'Target found at index: {answer} in {iterations} iterations')
else:
print('Target not found in the list')
HASH TABLE
class Hash(object):
def __init__(self, bucket):
# Number of buckets
self.__bucket = bucket
# Hash table of size bucket
self.__table = [[] for _ in range(bucket)]

# Hash function to map values to key


def hash_function(self, key):
return (key % self.__bucket)

def insert_item(self, key):


# Get the hash index of key
index = self.hash_function(key)
self.__table[index].append(key)

def delete_item(self, key):


# Get the hash index of key
index = self.hash_function(key)
# Check the key in the hash table
if key not in self.__table[index]:
print(f"Key {key} not found in the hash table.")
return
# Delete the key from the hash table
self.__table[index].remove(key)
print(f"Key {key} deleted from the hash table.")

# Function to display hash table


def display_hash(self):
for i in range(self.__bucket):
print(f"[{i}]", end='')
for x in self.__table[i]:
print(f" --> {x}", end='')
print()
# Driver Program
if __name__ == "__main__":
# Array that contains keys to be mapped
a = [15, 11, 27, 8, 12]
BUCKET_SIZE = 5 # Define the size of the hash table

# Create an empty hash table with the given BUCKET_SIZE


h = Hash(BUCKET_SIZE)

# Insert the keys into the hash table


for x in a:
h.insert_item(x)

# Delete 12 from the hash table


h.delete_item(12) # Explicitly delete 12

# Display the hash table


h.display_hash()

You might also like