AD3251-LINKED LIST,STACK ADT,QUEUE ADT.docx

Here's a suggestion for a description to upload your document on a website:

"Unlock the power of data structures with our comprehensive guide! Dive into the world of linked lists, Stack ADT (Abstract Data Type), and Queue ADT with our expertly curated document. Whether you're a seasoned programmer or just starting out, our resource provides clear explanations, insightful examples, and practical applications to help you master these fundamental concepts. Explore the intricacies of linked lists for efficient data storage, understand the versatility of Stack ADT for managing data in a Last-In, First-Out (LIFO) fashion, and delve into the functionality of Queue ADT for orderly data processing in a First-In, First-Out (FIFO) manner. Elevate your understanding of data structures and revolutionize your programming skills with our invaluable document. With clear explanations, illustrative examples, and practical exercises, our document equips you with the knowledge and skills needed to conquer data structure challenges with confidence. Whether you're a student embarking on your journey into computer science or a seasoned developer .Seeking to expand your repertoire, our resource is your roadmap to success.

Download our document now and embark on a transformative learning experience that will elevate your programming prowess to new heights!"

1. UNIT II LINEAR STRUCTURES 9
List ADT – array-based implementations – linked list implementations – singly linked lists –
circularly linked lists – doubly linked lists – applications of lists – Stack ADT – Queue ADT –
double-ended queues
List ADT:
List ADT

 The data is generally stored in key sequence in a list which has a head structure
consisting of count, pointers , and address of compare function needed to compare
the data in the list.
 The data node contains the pointer to a data structure and a self-referential
pointer that points to the next node in the list.
 The List of ADT Functions is given below:
 get() – Return an element from the list at any given position.
 insert() – Insert an element at any position of the list.
 remove() – Remove the first occurrence of any element from a non-empty list.
 removeAt() – Remove the element at a specified location from a non-empty list.
 replace() – Replace an element at any position by another element.
 size() – Return the number of elements in the list.
 isEmpty() – Return true if the list is empty, otherwise return false.
 isFull() – Return true if the list is full, otherwise return false.

Program:
class CustomList:
def __init__(self, capacity):
self.capacity = capacity

2. self.elements = [None] * capacity
self.size = 0
def get(self, position):
if position < 0 or position >= self.size:
raise IndexError("Index out of range")
return self.elements[position]
def insert(self, position, element):
if position < 0 or position > self.size:
raise IndexError("Index out of range")
if self.size == self.capacity:
raise Exception("List is full")
for i in range(self.size, position, -1):
self.elements[i] = self.elements[i - 1]
self.elements[position] = element
self.size += 1
def remove(self, element):
for i in range(self.size):
if self.elements[i] == element:
self.removeAt(i)
return
def removeAt(self, position):
if position < 0 or position >= self.size:
raise IndexError("Index out of range")
for i in range(position, self.size - 1):
self.elements[i] = self.elements[i + 1]

3. self.elements[self.size - 1] = None
self.size -= 1
def replace(self, position, new_element):
if position < 0 or position >= self.size:
raise IndexError("Index out of range")
self.elements[position] = new_element
def getSize(self):
return self.size
def isEmpty(self):
return self.size == 0
def isFull(self):
return self.size == self.capacity
# Example usage:
custom_list = CustomList(5)
print("Is the list empty?", custom_list.isEmpty()) # True
custom_list.insert(0, "a")
custom_list.insert(1, "b")
custom_list.insert(2, "c")
print("Is the list full?", custom_list.isFull()) # False
print("List size:", custom_list.getSize()) # 3
print("Element at position 1:", custom_list.get(1)) # b
custom_list.remove("b")
print("List size after removing an element:", custom_list.getSize()) # 2
custom_list.replace(0, "x")
print("Element at position 0 after replacement:", custom_list.get(0)) # x

4. Array Based Implementation:
Static Implementation of ADT List
The simplest method to implement a List ADT is to use an array that is a“linear list” or a
“contiguous list” where elements are stored in contiguous array positions. The
implementation specifies an array of a particular maximum length, and all storage is allocated
before run-time. It is a sequence of n-elements where the items in the array are stored with
the index of the array related to the position of the item in the list.
In array implementation,elements are stored in contiguous array positions (Figure
3.1). An array is a viable choice for storing list elements when the elements are sequential,
because it is a commonly available data type and in general algorithm development is easy.

List Implementation using arrays
In order to implement lists using arrays we need an array for storing entries –
listArray[0,1,2…..m], a variable currto keep track of the number of array elements currently
assigned to the list, thenumber of items in the list, or current size of the list sizeand a variable
to record the maximum length of the array, and therefore of the list – maxsize as shown in
Fix one end of the list at index 0 and elements will be shiftedas needed when an element is
added or removed. Therefore insert and delete operations will take O(n). That is if we want to
insert at position 0 (insert as first element),this requires first pushing the entire array to the
right one spot to make room for the new element. Similarly deleting the element at position
0requires shifting all the elements in the list left one spot.

5. One of the important operations associated with lists is the initialization. In this case we need
to first declare the array of list items with maximum number of items say n. This then
requires an estimate of the maximum size of the list. Once we decide the size, then we
`initialize the list with number of items set at 0.
Finding First Element

Here we define finding the first element by first calling a Boolean function – IsEmpty list. If
IsEmpty listis true that is if the list is empty then there is no question of finding an element
and finding the first element will return a value that is not a valid entry of the list However if
IsEmpty listis false that is the list is not empty the element at the first location position (0) is
returned.
Insertion
What happens if you want to insert an item at a specified position in an existing array?The
item originally at the given index must be moved right one position, and all the items after
that index must be shifted right.
Let us consider a specific case of Insert operation. Insert (3, K, List) In this case, 3 is the
index or the point of Insertion, K is the element to be inserted & List is the list in which
insertion is to be done ( Figure 3.4 (a) & Figure 3.4 (b)).

6. Let us see the steps in the insertion with the example given in Figure 3.4(a) & Figure 3.4 (b).
Let us assume initially that the original list contains 7 elements (that is Size =7) namely A at
array location 0, X at location 1 and so on and finally Rat location 6. The steps involved are
as follows:
Step 1: First check whether there is place to add the new element – in other words whether
the array is full. If so indicate error
size = maxsize – Then error
Step 2: Now we need to make room for the new element at the index position 3. We need to
shift elements from index to curr (curr position of last element of list) one position to the
right.
Loop till curr
Items[index+1] =>tems[index]
Step 3: Write the element into the gap created by shifting the elements to the right
Items[index] => K
Step 4: Update size and curr position of the list
size=> size +1; curr=>curr +1
Deletion from Lists
What happens if you want to remove an item from a specified position in an existing array?
There are two ways in which this can be done:
– Leave gaps in the array, i.e. indices that contain no elements, which in practice, means that
the array element has to be given a special value to indicate that it is “empty”, or
– All the items after the (removed item’s) index must be shifted leftsimilar to what we did
when we wanted to insert – only for insertion we shifted right.
– Delete (3, List). In this case, 3 is the index or the point of Deletion& List is the list from
which deletion is to be done (Figure 3.5 (a) & Figure 3.5 (b)).
Let us see the steps in the deletion with the example given in Figure 3.5(a) & Figure 3.5(b).
Let us assume initially that the original list contains 7 elements (that is Size =7) namely A at
array location 0, X at location 1 and so on and finally R at location 6. The steps involved are
as follows:

7. Step 1: First check whether the list is empty that is whether there are elements in the list.
We cannot perform deletion from an empty list.
size=0 Then error
Step 2: Now we need to shift elements from index position 4 to the left so that an empty
locationis created due to the deletion at location 3 will be filled by elements to the left. We
need to shift elements from index (i) to curr( that is the curr position of last element of list)
one position to the left.
Loop till curr
Items[index] => items[index+1]
Step 4: Update size and curr position of the list
size=>size-1; curr=>curr-1
Advantages of Array-Based Implementation of Lists
Some of the major advantages of using array implementation of lists are:
Array is a natural way to implement lists
Arrays allow fast, random access of elements
Array based implementation is memory efficient since very little memory is required other
than that needed to store the actual contents
Some of the disadvantages of using arrays to implement lists are:
The size of the list must be known when the array is created and is fixed (static)
Array implementations of lists use a static data structure. Often defined at compile-time. This
means the array size or structure cannot be altered while program is running. This requires an
accurate estimate of the size of the array.
This fixing of the size beforehand usually results in overestimation of size which means we
tend to usually waste space rather than have program run out.
The deletion and insertion of elements into the list is slow since it involves shifting of
elements. It also means that data must be added to the end of the list for insertion and deletion
to be efficient. If insertion and deletion is towards the front of the list, all other elements must
shuffle down. This is slow and inefficient. This inefficiency is even more pronounced when
the size of the list is large.
Example Program:
class Node:
def __init__(self, data):

8. self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
def delete(self, data):
current = self.head
if current.data == data:
self.head = current.next
return
while current.next:
if current.next.data == data:
current.next = current.next.next
return
current = current.next
def find_first(self):
if self.head:
return self.head.data
else:
return None
def display(self):
current = self.head
while current:
print(current.data, end=" ")
current = current.next
print()
# Example usage:
ll = LinkedList()
ll.insert(1)
ll.insert(2)
ll.insert(3)
ll.display() # Output: 1 2 3
print("First element:", ll.find_first()) # Output: First element: 1
ll.delete(2)
ll.display() # Output: 1 3

9. Linked List Implementation:
A linked List is a linear data structure, meaning that data elements are arranged in sequence
and that each member element is connected to its next element. It consists of data objects in
the form of nodes connected by links or pointers. Each node of LinkedList has two fields:
 Data: Stores the value of a node in this field.
 Next: Stores the address of the next linked node.
In LinkedList, the first node is considered the Head of the LinkedList, which stores the
address of the LinkedList, and the last node is considered by using the NONE value in the
next field of the node.

Creation of Linked list in Python
LinkedList is created by using the node class. In the Node class, we create a function that is
used to set the value and the next pointer for the node. We pass the values through the node
object to point to the following data elements. In this static example, we manually add 5
nodes in the linked list by adding each node.
Algorithm
# Creation of Node class and inside the class we create a function
# For storing the value and next pointer for the node.
# Assign a value to the first node
node1 = ('elem1')
# Storing the address of the First node into a variable named `head`.
head = node1
# Creating more nodes for the LinkedList
node2 = ('elem2')
node3 = ('elem3')
node4 = ('elem4')
node5 = ('elem5')
# Storing the address of the node to their previous nodes.
node1.next = node2

10. node2.next = node3
node3.next = node4
node4.next = node5
Example:
class node:
def __init__(self, value = None):
self.value = value
self.next = None
node1 = node('elem1')
head = node1
node2 = node('elem2')
node3 = node('elem3')
node4 = node('elem4')
node5 = node('elem5')
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
Explanation of Example
We created a node class, which is the basic unit of LinkedList. Inside it, we created a function
that takes the value for the node as a parameter. Then, we assign the value to the node. And
we place None for the next pointer for that node. Now, we create first node and give it a
value elem1. We stored the address of node1 to the head variable. After that, we will create
some more nodes for our LinkedList. Then we store each node's address in their previous
nodes by using Node.next. For example, the next pointer of node1 will point to node2.
Creating a Node Class
Creating a Node class in Python is fundamental in implementing various data structures like
linked lists, trees, and graphs. A Node class typically represents an individual element in
these data structures and contains a value and a reference to the next (and sometimes
previous) node. Below is an example of how to create a simple Node class in Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
Let's break down the components of this Node class:

11. 1. Class Definition:
o class Node:: This line declares the Node class in Python.
2. Constructor Method (__init__):
o def __init__(self, data):: This method initializes a new instance of the Node
class.
o self refers to the current instance of the class.
o data is the value that the node will hold.
3. Data Attribute:
o self.data: This attribute holds the value of the node.
4. Next Pointer:
o self.next: This attribute is a reference to the next node in a linked list. By
default, it is set to None, indicating that the node currently does not point to
any other node.
With this Node class, you can create individual nodes and link them together to form data
structures like linked lists. Here's an example of how you can create and use nodes:
# Create nodes
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
# Link nodes together
node1.next = node2
node2.next = node3
# Traverse the linked list
current_node = node1
while current_node:
print(current_node.data)
current_node = current_node.next
In this example:
 Three nodes with values 10, 20, and 30 are created.
 The next attribute of each node is assigned to the next node, linking them together.
 Finally, the linked list is traversed starting from the first node (node1), printing the
value of each node along the way.
Traversing a Linked List in Python
A singly LinkedList can only be traversed in one direction(forward direction). This means
that we can't return to the previous element of LinkedList if we pass that element. We have to
traverse the elements of the LinkedList with the help of the pointer assigned to the next node.

12. Algorithm
pointer = head (points to the head)
loop(till pointer.next != None):
print pointer.val for the node
# update pointer after each single interation
pointer = pointer.next


class node:
def __init__ (self, value = None):
self.value = value
self.next = None
node1 = node('elem1')
head = node1
node2 = node('elem2')
node3 = node('elem3')
node4 = node('elem4')
node5 = node('elem5')
node6 = node('elem6')
node1.next = node2
node2.next = node3
node3.next = node4

13. node4.next = node5
node5.next = node6
pointer = head
while(pointer!=None):
print(pointer.value)
pointer=pointer.next
output:
elem1
elem2
elem3
elem4
elem5
elem6
Explanation
First of all, we created a node class so that we can create our basic unit of the LinkedList.
After that, we created the first node & assigned that first node as the head of our LinkedList.
After assigning the value, we store the address of every next node in the previous node.
Lastly, we created a pointer variable that currently stores the head value and gets updated
during every iteration of the loop.
Then, we start writing the code for the traversal of LinkedList. We implement a while loop
until Node.Next does not equal None. As the loop is running, we are printing the value of
each node. After printing the node value, we update the pointer so that it can point to the next
node.
Insertion in a LinkedList
Insertion in a LinkedList means adding elements/nodes to the existing LinkedList. The basic
technique used in inserting the newly created node into a LinkedList is reallocating the next
pointer of an already existing node of the LinkedList.
Orignal LinkedList Before Insertion

14. We can insert a node to 3 different positions of LinkedList. Let's understand each of these
one by one:
1. Insertion at Beginning
While Inserting a node at the beginning of the LinkedList, we have to point the next pointer
of the newly created node to the head of the LinkedList. So, the current head changes to the
second node of the LinkedList and the newly created node changes to the head of the
LinkedList.
Let's understand the algorithm and the example for the insertion of a node at the beginning of
the LinkedList.
Algorithm
nodeInBeginning = ('new node') # create a new node
# allocating the head value to the next pointer of new node
nodeInBeginning.next = head
head = nodeInBeginning # pointing head to the new node
Delete Node in a Linked List
 This operation deletes a node with a given value from the linked list.
 It traverses the list to find the node with the specified value and removes it by
updating the pointers of the previous and next nodes.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def deleteNode(head, val):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == val:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
1. Remove First Node from Linked List:

15. o This operation removes the first node from the linked list.
o It updates the head pointer to the next node in the list.
def removeFirstNode(head):
if not head:
return None
return head.next
2. Remove Last Node from Linked List:
o This operation removes the last node from the linked list.
o It traverses the list to find the second-to-last node and updates its next pointer
to None.
def removeLastNode(head):
if not head or not head.next:
return None
curr = head
while curr.next.next:
curr = curr.next
curr.next = None
return head
3. Delete a Linked List Node at a Given Position:
o This operation deletes the node at a specified position (index) in the linked list.
o It traverses the list to find the node at the specified position and removes it by
updating the pointers of the previous and next nodes.
def deleteNodeAtPosition(head, position):
if position == 0:
return head.next
prev, curr = None, head
for _ in range(position):
prev, curr = curr, curr.next
if not curr:
break
if curr:
prev.next = curr.next
return head

16. class node:
def __init__(self, value=None):
self.value = value
self.next = None
node1 = node('elem1')
head = node1
node2 = node('elem2')
node3 = node('elem3')
node4 = node('elem4')
node5 = node('elem5')

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
# Insertion of New Node In Beginning
nodeInBeginning = node('new node')
nodeInBeginning.next = head
head = nodeInBeginning
pointer = head
while(pointer!=None):
print(pointer.value)

17. pointer=pointer.next
2. Insertion at The End
Insertion at the end of LinkedList is almost the same as that in the middle of the LinkedList.
In this case, we don't have to update the next pointer of the new node, but we just update the
next pointer of the last node with the address of the newly created node, and then our new
node gets added to the LinkedList at the end.
Algorithm
# create a new node
nodeAtEnd = node('value')
# iterate till the point after which the next value of node
# doesn't equals to `None`
loop(till pointer.next != None):
# update the pointer at each iteration
pointer = pointer.next

# After looping, we got the node whose next value is `None`, which
# represents the end of LinkedList.
# It means we have to add the new node after that Node.
# Now we have to update the next pointer of that node with the
# `nodeAtEnd` will add a new node at the end of our LinkedList.

pointer.next = nodeAtEnd

class node:
def __init__(self, value = None):

18. self.value = value
self.next = None
node1 = node('elem1')
head = node1
node2 = node('elem2')
node3 = node('elem3')
node4 = node('elem4')
node5 = node('elem5')
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
# Insertion of New Node at the End
nodeAtEnd = node('new node')
pointer = head
while(pointer.next!=None):
pointer = pointer.next
pointer.next = nodeAtEnd
pointer = head
while(pointer!=None):
print(pointer.value)
pointer=pointer.next
output:
elem1
elem2
elem3
elem4
elem5
new node
Advantages and Disadvantages of Linked List
Advantages of Linked Lists:
1. Dynamic Size: Linked lists can dynamically grow or shrink in size during program
execution, unlike arrays, which have a fixed size.

19. 2. Insertion and Deletion: Insertion and deletion operations can be performed
efficiently at any position within a linked list.
3. Memory Utilization: Linked lists utilize memory efficiently by allocating memory
only when needed.
4. Ease of Implementation: Implementing certain operations, such as inserting or
deleting elements, is often simpler with linked lists compared to arrays due to fewer
constraints on memory allocation.
5. Versatility: Python Linked lists support various linked structures, including singly
linked lists, doubly linked lists, and circular linked lists.
Disadvantages of Linked Lists:
1. Sequential Access: Unlike arrays, linked lists do not support random access to
elements based on their indices.
2. Memory Overhead: Linked lists require extra memory for storing pointers/references
to the next node, increasing memory overhead compared to arrays.
3. Cache Inefficiency: Traversing a linked list in python may lead to cache misses since
elements are not stored contiguously in memory.
4. Extra Space for Pointers: Each node in a linked list requires additional memory for
storing pointers or references to the next node, leading to higher space complexity
than arrays.
5. Complexity in Reversal: Reversing a linked list in Python or performing certain
operations, such as finding the middle node, may require more complex algorithms
than similar operations on arrays.
Implementing a stack with a singly linked list:

class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
self.size = 0
def is_empty(self):
return self.size == 0
def push(self, data):
new_node = Node(data)

20. new_node.next = self.head
self.head = new_node
self.size += 1
def pop(self):
if self.is_empty():
print("Stack is empty")
return None
else:
popped_data = self.head.data
self.head = self.head.next
self.size -= 1
return popped_data
def peek(self):
if self.is_empty():
print("Stack is empty")
return None
else:
return self.head.data
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage

21. stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print("Stack after pushing elements:")
stack.display()
print("Peek:", stack.peek())
print("Popped:", stack.pop())
print("Stack after popping an element:")
stack.display()


Implementing a Queue with a Singly Linked List:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
self.size = 0
def is_empty(self):
return self.size == 0
def enqueue(self, data):
new_node = Node(data)
if self.is_empty():

22. self.front = new_node
else:
self.rear.next = new_node
self.rear = new_node
self.size += 1
def dequeue(self):
if self.is_empty():
print("Queue is empty")
return None
else:
dequeued_data = self.front.data
self.front = self.front.next
if self.front is None:
self.rear = None
self.size -= 1
return dequeued_data
def peek(self):
if self.is_empty():
print("Queue is empty")
return None
else:
return self.front.data
def display(self):
current = self.front
while current:

23. print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print("Queue after enqueueing elements:")
queue.display()
print("Peek:", queue.peek())
print("Dequeued:", queue.dequeue())
print("Queue after dequeuing an element:")
queue.display()
Implementing a Queue with a circular linked list:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularQueue:
def __init__(self):
self.front = None
self.rear = None
def is_empty(self):
return self.front is None

24. def enqueue(self, data):
new_node = Node(data)
if self.is_empty():
self.front = new_node
else:
self.rear.next = new_node
self.rear = new_node
self.rear.next = self.front
def dequeue(self):
if self.is_empty():
print("Queue is empty")
return None
dequeued_data = self.front.data
if self.front == self.rear:
self.front = None
self.rear = None
else:
self.front = self.front.next
self.rear.next = self.front
return dequeued_data
def peek(self):
if self.is_empty():
print("Queue is empty")
return None
return self.front.data

25. def display(self):
if self.is_empty():
print("Queue is empty")
return
current = self.front
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.front:
break
print()
# Example usage
queue = CircularQueue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print("Queue after enqueueing elements:")
queue.display()
print("Peek:", queue.peek())
print("Dequeued:", queue.dequeue())
print("Queue after dequeuing an element:")
queue.display()

26. SINGLY-LINKED LIST:
DOUBLY LINKED LIST:
A doubly linked list is a type of linked list in which each node consists of 3 components:
 *prev - address of the previous node
 data - data item
 *next - address of next node

Representation of Doubly Linked List
Let's see how we can represent a doubly linked list on an algorithm/code. Suppose we have a
doubly linked list:

Insertion on a Doubly Linked List
Pushing a node to a doubly-linked list is similar to pushing a node to a linked list, but extra
work is required to handle the pointer to the previous node.
We can insert elements at 3 different positions of a doubly-linked list:
Insertion at the beginning
Insertion in-between nodes
Insertion at the End
Suppose we have a double-linked list with elements 1, 2, and 3.

Insertion at the Beginning
Let's add a node with value 6 at the beginning of the doubly linked list we made above.
1. Create a new node

allocate memory for newNode

27. assign the data to newNode.

Set prev and next pointers of new node
point next of newNode to the first node of the doubly linked list
point prev to null

Make new node as head node
Point prev of the first node to newNode (now the previous head is the second
node)
Point head to newNode.

2. Insertion in between two nodes
Let's add a node with value 6 after node with value 1 in the doubly linked list.
1. Create a new node
allocate memory for newNode
assign the data to the newNode.

2. Set the next pointer of new node and previous node

28. assign the value of next from previous node to the next of newNode
assign the address of newNode to the next of previous node

3. Set the prev pointer of new node and the next node
assign the value of prev of next node to the prev of newNode
assign the address of newNode to the prev of next node

The final doubly linked list is after this insertion is:

3. Insertion at the End
Let's add a node with value 6 at the end of the doubly linked list.
1. Create a new node

2. Set prev and next pointers of new node and the previous node

If the linked list is empty, make the newNode as the head node. Otherwise, traverse to
the end of the doubly linked list and

29. The final doubly linked list looks like this.

Deletion from a Doubly Linked List
 Similar to insertion, we can also delete a node from 3 different positions of a
doubly linked list.
 Suppose we have a double-linked list with elements 1, 2, and 3.

Delete the First Node of Doubly Linked List
If the node to be deleted (i.e. del_node) is at the beginning

Reset value node after the del_node (i.e. node two)

Finally, free the memory of del_node. And, the linked will look like this

2. Deletion of the Inner Node
If del_node is an inner node (second node), we must have to reset the value of
next and prev of the nodes before and after the del_node.
For the node before the del_node (i.e. first node)
Assign the value of next of del_node to the next of the first node.
For the node after the del_node (i.e. third node)

30. Assign the value of prev of del_node to the prev of the third node.

Finally, we will free the memory of del_node. And, the final doubly linked list looks like this.

3. Delete the Last Node of Doubly Linked List
In this case, we are deleting the last node with value 3 of the doubly linked list.
Here, we can simply delete the del_node and make the next of node before del_node
point to NULL.

The final doubly linked list looks like this.

Doubly Linked List Complexity
Doubly Linked List Complexity Time Complexity Space Complexity
Insertion Operation O(1) or O(n) O(1)
Deletion Operation O(1) O(1)

Example Program:
class Node:
def __init__(self, data):
self.data = data
self.prev = None

31. self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
# Insertion at the beginning
def insert_at_beginning(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
# Insertion at the end
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
# Insertion at specific position
def insert_at_position(self, position, data):
if position < 0:
print("Invalid position")
return
if position == 0:
self.insert_at_beginning(data)

32. return
new_node = Node(data)
current = self.head
count = 0
while current:
if count == position - 1:
new_node.next = current.next
new_node.prev = current
if current.next:
current.next.prev = new_node
current.next = new_node
break
current = current.next
count += 1
else:
print("Position out of range")
# Deletion at front
def delete_at_front(self):
if not self.head:
print("List is empty")
return
if self.head == self.tail:
self.head = None
self.tail = None
return
self.head = self.head.next
self.head.prev = None
# Delete inner node
def delete_inner_node(self, data):
if not self.head:
print("List is empty")
return

33. current = self.head
while current:
if current.data == data:
if current == self.head:
self.head = current.next
if self.head:
self.head.prev = None
elif current == self.tail:
self.tail = current.prev
self.tail.next = None
else:
current.prev.next = current.next
current.next.prev = current.prev
return
current = current.next
print("Node not found")
# Delete at the end
def delete_at_end(self):
if not self.head:
print("List is empty")
return
if self.head == self.tail:
self.head = None
self.tail = None
return
self.tail = self.tail.prev
self.tail.next = None
# Display the doubly linked list
def display(self):
if not self.head:
print("List is empty")
return

34. current = self.head
while current:
print(current.data, end=" <-> ")
current = current.next
print()
# Example usage:
if __name__ == "__main__":
dll = DoublyLinkedList()
dll.insert_at_beginning(10)
dll.insert_at_end(20)
dll.insert_at_end(30)
dll.insert_at_beginning(5)
dll.insert_at_position(2, 15)
dll.display() # Output: 5 <-> 10 <-> 15 <-> 20 <-> 30 <->
dll.delete_at_front()
dll.display() # Output: 10 <-> 15 <-> 20 <-> 30 <->
dll.delete_inner_node(20)
dll.display() # Output: 10 <-> 15 <-> 30 <->
dll.delete_at_end()
dll.display() # Output: 10 <-> 15 <->
CIRCULAR LINKED LIST:
A circular linked list is a type of linked list in which the first and the last nodes
are also connected to each other to form a circle.
There are basically two types of circular linked list:
1. Circular Singly Linked List
Here, the address of the last node consists of the address of the first node.

Circular Doubly Linked List

35. Here, in addition to the last node storing the address of the first node, the first
node will also store the address of the last node.

Representation of Circular Linked List
Let's see how we can represent a circular linked list on an algorithm/code.
Suppose we have a linked list:

Insertion on a Circular Linked List
We can insert elements at 3 different positions of a circular linked list:
Insertion at the beginning
Insertion in-between nodes
Insertion at the end
Suppose we have a circular linked list with elements 1, 2, and 3.

36. Let's add a node with value 6 at different positions of the circular linked list
we made above. The first step is to create a new node.
 allocate memory for newNode
 assign the data to newNode

Insertion at the Beginning
 store the address of the current first node in the newNode (i.e. pointing
the newNode to the current first node)
 point the last node to newNode (i.e making newNode as head)


Insertion in between two nodes
Let's insert newNode after the first node.
 travel to the node given (let this node be p)
 point the next of newNode to the node next to p
 store the address of newNode at next of p

37. Insertion at the end
 store the address of the head node to next of newNode
(making newNode the last node)
 point the current last node to newNode
 make newNode as the last node

Deletion on a Circular Linked List
Suppose we have a double-linked list with elements 1, 2, and 3.

If the node to be deleted is the only node
free the memory occupied by the node
store NULL in last
2. If last node is to be deleted
find the node before the last node (let it be temp)
store the address of the node next to the last node in temp
free the memory of last
make temp as the last node

38. if any other nodes are to be deleted
 travel to the node to be deleted (here we are deleting node 2)
 let the node before node 2 be temp
 store the address of the node next to 2 in temp
 free the memory of 2

Complexity of Insertion Operation
The insertion operations that do not require traversal have the
time complexity of O(1).
And, an insertion that requires traversal has a time complexity
of O(n).
The space complexity is O(1).
2. Complexity of Deletion Operation
All deletion operations run with a time complexity of O(1).
And, the space complexity is O(1).
Example program:
class Node:
def __init__(self, data):
self.data = data

39. self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
# Insertion at the beginning
def insert_at_beginning(self, data):
new_node = Node(data)
if not self.head:
new_node.next = new_node # Circular reference for the first node
else:
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = new_node
new_node.next = self.head
self.head = new_node
# Insertion in between two nodes
def insert_after_node(self, node_data, data):
new_node = Node(data)
temp = self.head
while temp:
if temp.data == node_data:
break
temp = temp.next
if temp == self.head:
print("Node not found")
return
new_node.next = temp.next
temp.next = new_node
# Insertion at the end
def insert_at_end(self, data):

40. new_node = Node(data)
if not self.head:
new_node.next = new_node # Circular reference for the first node
self.head = new_node
else:
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = new_node
new_node.next = self.head
# Deletion
def delete(self, data):
if not self.head:
print("List is empty")
return
temp = self.head
prev = None
while True:
if temp.data == data:
if prev:
prev.next = temp.next
if temp == self.head:
self.head = temp.next
else:
last = self.head
while last.next != self.head:
last = last.next
if last == self.head:
self.head = None
else:
last.next = temp.next

41. self.head = temp.next
temp = None
return
elif temp.next == self.head:
print("Element not found in the list")
return
prev = temp
temp = temp.next
if temp == self.head:
break
# Display the circular linked list
def display(self):
if not self.head:
print("List is empty")
return
temp = self.head
while True:
print(temp.data, end=" -> ")
temp = temp.next
if temp == self.head:
break
print()
# Example usage:
if __name__ == "__main__":
cll = CircularLinkedList()
cll.insert_at_beginning(10)
cll.insert_at_beginning(5)
cll.insert_at_end(20)
cll.insert_after_node(10, 15)
cll.display() # Output: 5 -> 10 -> 15 -> 20 ->
cll.delete(15)

42. cll.display() # Output: 5 -> 10 -> 20 ->
PREVIOUS YEAR UNIVERSITY QUESTIONS ANSWERS:
when singly linked list can be represented as circular linked list?
A singly linked list can be represented as a circular linked list when you want to
perform operations that involve cycling through the list repeatedly or when you need efficient
access to both ends of the list. Here's a real-time example and a programming example:
Real-Time Example:
Imagine a music playlist where each song is represented as a node in a linked list. You want
the playlist to loop back to the beginning once it reaches the end so that it continuously plays.
In this case, representing the playlist as a circular linked list would be appropriate. When the
last song finishes playing, it would loop back to the first song seamlessly.
PROGRAM:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.head.next = self.head
else:
current = self.head
while current.next != self.head:

43. current = current.next
current.next = new_node
new_node.next = self.head
def display(self):
if not self.head:
print("List is empty")
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print()
# Example usage
playlist = CircularLinkedList()
playlist.append("Song 1")
playlist.append("Song 2")
playlist.append("Song 3")
playlist.append("Song 4")
print("Playlist:")
playlist.display()

when sdoubly linked list can be represented as circular linked list?
A doubly linked list can be represented as a circular linked list when you want bidirectional
traversal with the added feature of looping back from the last node to the first node. Here's a
real-time example and a programming example:
Real-Time Example:

44. Consider a browser history functionality where you want to navigate both forward and
backward through visited web pages. Each web page can be represented as a node in a doubly
linked list. By making this doubly linked list circular, you can seamlessly navigate from the
first page to the last page and vice versa.
PROGRAM:
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class CircularDoublyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.head.prev = self.head
self.head.next = self.head
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.prev = current
new_node.next = self.head
self.head.prev = new_node
def display_forward(self):
if not self.head:

45. print("List is empty")
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print()
def display_backward(self):
if not self.head:
print("List is empty")
return
current = self.head.prev
while True:
print(current.data, end=" -> ")
current = current.prev
if current == self.head.prev:
break
print()
# Example usage
history = CircularDoublyLinkedList()
history.append("google.com")
history.append("wikipedia.org")
history.append("github.com")
history.append("youtube.com")
print("Forward Navigation:")
history.display_forward()
print("\nBackward Navigation:")
history.display_backward()

46. STACK ADT
stack is a linear data structure where elements are stored in the LIFO (Last In First Out)
principle where the last element inserted would be the first element to be deleted. A stack is an
Abstract Data Type (ADT), that is popularly used in most programming languages. It is named
stack because it has the similar operations as the real-world stacks, for example − a pack of
cards or a pile of plates, etc.
Stack Representation
A stack allows all data operations at one end only. At any given time, we can only access the
top element of a stack.
The following diagram depicts a stack and its operations −


Basic Operations on Stacks
Stack operations are usually performed for initialization, usage and, de-initialization of the
stack ADT.
The most fundamental operations in the stack ADT include: push(), pop(), peek(), isFull(),
isEmpty(). These are all built-in operations to carry out data manipulation and to check the
status of the stack.
Stack uses pointers that always point to the topmost element within the stack, hence called as
the top pointer.
PROGRAM:
class Stack:
def __init__(self, max_size):
self.max_size = max_size # Maximum size of the stack
self.stack = [] # List to store stack elements
def push(self, item):
"""Add an item to the top of the stack."""

47. if not self.is_full(): # Check if the stack is not full
self.stack.append(item) # Append the item to the stack
else:
print("Stack is full. Cannot push more elements.")
def pop(self):
"""Remove and return the top item from the stack."""
if not self.is_empty(): # Check if the stack is not empty
return self.stack.pop() # Remove and return the top item
else:
print("Stack is empty. Cannot pop from an empty stack.")
return None
def peek(self):
"""Return the top item from the stack without removing it."""
if not self.is_empty(): # Check if the stack is not empty
return self.stack[-1] # Return the top item of the stack
else:
print("Stack is empty. Cannot peek from an empty stack.")
return None
def is_full(self):
"""Check if the stack is full."""
return len(self.stack) == self.max_size # Return True if stack size equals max_size
def is_empty(self):
"""Check if the stack is empty."""
return len(self.stack) == 0 # Return True if stack is empty
# Example usage
stack = Stack(max_size=5) # Create a stack with maximum size of 5
# Push elements onto the stack
stack.push(1)
stack.push(2)
stack.push(3)

48. # Peek at the top element
print("Top element:", stack.peek())
# Pop elements from the stack
print("Popped element:", stack.pop())
print("Popped element:", stack.pop())
print("Popped element:", stack.pop())
print("Popped element:", stack.pop()) # Attempt to pop from an empty stack
# Reverse Data using Stack
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
def is_empty(self):
return len(self.items) == 0

def reverse_data(data):
stack = Stack()
for item in data:
stack.push(item)
reversed_data = []
while not stack.is_empty():
reversed_data.append(stack.pop())
return reversed_data
# Function to get array elements from the user
def get_array_from_user():
array = []

49. n = int(input("Enter the number of elements in the array: "))
print("Enter the elements of the array:")
for i in range(n):
element = int(input())
array.append(element)
return array
# Example usage:
data = get_array_from_user()
reversed_data = reverse_data(data)
print("Original data:", data)
print("Reversed data:", reversed_data)

# matching paranthesis
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
def is_empty(self):
return len(self.items) == 0

def is_matching_parentheses(expression):
stack = Stack()
opening_brackets = "([{"
closing_brackets = ")]}"
for char in expression:
if char in opening_brackets:

50. stack.push(char)
elif char in closing_brackets:
if stack.is_empty():
return False
top = stack.pop()
if opening_brackets.index(top) != closing_brackets.index(char):
return False
return stack.is_empty()
# Example usage:
expression = input("Enter an expression: ")
if is_matching_parentheses(expression):
print("The parentheses in the expression are balanced.")
else:
print("The parentheses in the expression are not balanced.")

MATCHING HTML TAGS
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self, item):
self.items.append(item)

def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
def size(self):
return len(self.items)

51. def is_matched_html(html):
stack = Stack()
balanced = True
index = 0
while index < len(html) and balanced:
symbol = html[index]
if symbol == '<':
stack.push(symbol)
elif symbol == '>':
if stack.is_empty():
balanced = False
else:
stack.pop()
index += 1
return balanced and stack.is_empty()
# Test the function
html1 = "<html><head><title>Hello</title></head><body><h1>Test</h1></body></html>"
html2 = "<html><head><title>Hello</title></head><body><h1>Test</h1></body>"
html3 =
"<html><head><title>Hello</title></head><body><h1>Test</h1></body></html>>"
print(is_matched_html(html1)) # True
print(is_matched_html(html2)) # False
print(is_matched_html(html3)) # False

EVALUATING ARITHMETIC EXPRESSIONS
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self, item):

52. self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
def size(self):
return len(self.items)
def evaluate_expression(expression):
stack = Stack()
operators = {'+': lambda x, y: x + y, '-': lambda x, y: x - y, '*': lambda x, y: x * y, '/': lambda x, y: x /
y}
for token in expression.split():
if token.isdigit():
stack.push(float(token))
elif token in operators:
operand2 = stack.pop()
operand1 = stack.pop()
result = operators[token](operand1, operand2)
stack.push(result)
else:
raise ValueError("Invalid token in expression: {}".format(token))
if stack.size() == 1:
return stack.pop()
else:
raise ValueError("Invalid expression")
# Test the function
expression1 = "3 4 + 2 *"
expression2 = "5 1 2 + 4 * + 3 -"
print("Result of {}: {}".format(expression1, evaluate_expression(expression1))) # 14.0
print("Result of {}: {}".format(expression2, evaluate_expression(expression2))) # 14.0