Unit - 2
Abstract Data Types (ADTs) Stack
Q1) What is the abstract data type?
A1) The abstract data type is a special kind of datatype, whose behavior is defined by a set of values and set of operations. The keyword “Abstract” is used as we can use these data types, we can perform different operations. But how those operations are working is totally hidden from the user. The ADT is made of primitive data types, but operation logics are hidden.
Here we will see the stack ADT. These are a few operations or functions of the Stack ADT.
● isFull(), This is used to check whether stack is full or not
● isEmpty(), This is used to check whether stack is empty or not
● push(x), This is used to push x into the stack
● pop(), This is used to delete one element from top of the stack
● peek(), This is used to get the top most element of the stack
● size(), this function is used to get number of elements present into the stack
Example
#include<iostream>
#include<stack>
Using namespace std;
Main(){
Stack<int> stk;
If(stk.empty()){
Cout << "Stack is empty" << endl;
} else {
Cout << "Stack is not empty" << endl;
}
//insert elements into stack
Stk.push(10);
Stk.push(20);
Stk.push(30);
Stk.push(40);
Stk.push(50);
Cout << "Size of the stack: " << stk.size() << endl;
//pop and display elements
While(!stk.empty()){
Int item = stk.top(); // same as peek operation
Stk.pop();
Cout << item << " ";
}
}
Output
Stack is empty
Size of the stack: 5
50 40 30 20 10
Q2) What do you mean by push and pop?
A2) PUSH operation
The steps involved in the PUSH operation is given below:
● Before inserting an element in a stack, we check whether the stack is full.
● If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.
● When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
● When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, and the element will be placed at the new position of the top.
● The elements will be inserted until we reach the max size of the stack.
Fig 1: Push Operation Example
POP operation
The steps involved in the POP operation is given below:
● Before deleting the element from the stack, we check whether the stack is empty.
● If we try to delete the element from the empty stack, then the underflow condition occurs.
● If the stack is not empty, we first access the element which is pointed by the top
● Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.
Fig 2: Pop Operation example
Q3) How to represent a stack using an array?
A3) The stack is created using the array in array implementation. Arrays are used to accomplish all of the operations on the stack. Let's look at how each operation can be accomplished utilizing an array data structure on the stack.
Adding an element onto the stack (push operation)
A push operation occurs when an element is added to the top of a stack. Two steps are involved in a push operation.
- Increase the value of the variable Top to allow it to refer to the next memory address.
- Add an element to the top of the incremented list. Adding a new element to the top of the stack is referred to as this.
When we try to put an element into a totally loaded stack, the stack overflows. As a result, our main function must always avoid stack overflow.
Algorithm
Begin
If top = n then stack full
Top = top + 1
Stack (top) : = item;
End
Implementation in C language
Void push (int val,int n) //n is size of the stack
{
If (top == n )
Printf("\n Overflow");
Else
{
Top = top +1;
Stack[top] = val;
}
}
Deletion of an element from a stack (Pop operation)
The pop action removes an element from the top of the stack. When an item is removed from the stack, the value of the variable top is increased by one. The stack's topmost element is saved in a separate variable, and then the top is decremented by one. As a result, the operation returns the removed value that was previously saved in another variable.
When we try to delete an element from an already empty stack, we get an underflow condition.
Algorithm
Begin
If top = 0 then stack empty;
Item := stack(top);
Top = top - 1;
End;
Implementation in C language
Int pop ()
{
If(top == -1)
{
Printf("Underflow");
Return 0;
}
Else
{
Return stack[top - - ];
}
}
Visiting each element of the stack (Peek operation)
Returning the element at the top of the stack without removing it is known as a peek operation. If we try to return the top piece from an already empty stack, we may encounter an underflow problem.
Algorithm
PEEK (STACK, TOP)
Begin
If top = -1 then stack empty
Item = stack[top]
Return item
End
Implementation in C language
Int peek()
{
If (top == -1)
{
Printf("Underflow");
Return 0;
}
Else
{
Return stack [top];
}
}
Q4) How to represent stack using linked list?
A4) To implement stack, we can use a linked list instead of an array. The memory is dynamically allocated with a linked list. However, the temporal complexity of all operations, such as push, pop, and peek, is the same in all scenarios.
The nodes in a linked list implementation of a stack are kept in memory in a non-contiguous manner. Each node on the stack has a pointer to its immediate successor node. If there isn't enough room in the memory heap to create a node, the stack is said to have overflown.
Fig 3: Linked list
Adding a node to the stack (Push operation)
The address field of the topmost node in the stack is always null. Let's look at how each action is carried out in the stack's linked list implementation.
The push action is used to add a node to the stack. Pushing an element to a stack in a linked list differs from pushing an element to a stack in an array. The following procedures are required to push an element onto the stack.
- First, make a node and allocate memory to it.
- If the list is empty, the item should be moved to the top as the list's first node. This involves giving the data component of the node a value and giving the address part of the node a null value.
- If the list already has some nodes, we must place the new element at the beginning of the list (to not violate the property of the stack). Assign the address of the starting element to the address field of the new node for this purpose, and make the new node the list's starting node.
C Implementation
Void push ()
{
Int val;
Struct node *ptr =(struct node*)malloc(sizeof(struct node));
If(ptr == NULL)
{
Printf("not able to push the element");
}
Else
{
Printf("Enter the value");
Scanf("%d",&val);
If(head==NULL)
{
Ptr->val = val;
Ptr -> next = NULL;
Head=ptr;
}
Else
{
Ptr->val = val;
Ptr->next = head;
Head=ptr;
}
Printf("Item pushed");
}
}
Deleting a node from the stack (POP operation)
The pop operation is used to remove a node from the top of the stack. The deletion of a node from the stack's linked list implementation differs from the array implementation. To remove an element from the stack, we must first perform the following steps:
- Check for the underflow condition - When we try to pop from an already empty stack, we get an underflow problem. If the list's head pointer points to null, the stack will be empty.
- Adjust the head pointer accordingly - Because the elements in a stack are only popped from one end, the value stored in the head pointer must be removed, and the node must be released. The head node's next node now serves as the head node.
C Implementation
Void pop()
{
Int item;
Struct node *ptr;
If (head == NULL)
{
Printf("Underflow");
}
Else
{
Item = head->val;
Ptr = head;
Head = head->next;
Free(ptr);
Printf("Item popped");
}
}
Q5) Write the application of stack?
A5) The following are the applications of the stack:
● Balancing of symbols: Stack is used for balancing a symbol. For example, we have the following program:
- Int main()
- {
- Cout<<"Hello";
- Coût<<"java point";
- }
As we know, each program has an opening and closing braces; when the opening braces come, we push the braces in a stack, and when the closing braces appear, we pop the opening braces from the stack. Therefore, the net value comes out to be zero. If any symbol is left in the stack, it means that some syntax occurs in a program.
● String reversal: Stack is also used for reversing a string. For example, we want to reverse a "java point" string, so we can achieve this with the help of a stack.
First, we push all the characters of the string in a stack until we reach the null character. After pushing all the characters, we start taking out the character one by one until we reach the bottom of the stack.
● UNDO/REDO: It can also be used for performing UNDO/REDO operations. For example, we have an editor in which we write 'a', then 'b', and then 'c'; therefore, the text written in an editor is abc. So, there are three states, a, ab, and abc, which are stored in a stack. There would be two stacks in which one stack shows UNDO state, and the other shows REDO state.
If we want to perform a UNDO operation, and want to achieve an 'ab' state, then we implement a pop operation.
● Recursion: The recursion means that the function is calling itself again. To maintain the previous states, the compiler creates a system stack in which all the previous records of the function are maintained.
● DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the stack data structure.
● Backtracking: Suppose we have to create a path to solve a maze problem. If we are moving in a particular path, and we realize that we come on the wrong way. In order to come at the beginning of the path to create a new path, we have to use the stack data structure.
● Expression conversion: Stack can also be used for expression conversion. This is one of the most important applications of stack. The list of the expression conversion is given below:
● Infix to prefix
● Infix to postfix
● Prefix to infix
● Prefix to postfix
● Postfix to infix
● Memory management: The stack manages the memory. The memory is assigned in the contiguous memory blocks. The memory is known as stack memory as all the variables are assigned in a function called stack memory. The memory size assigned to the program is known to the compiler. When the function is created, all its variables are assigned in the stack memory. When the function completes its execution, all the variables assigned in the stack are released.
Q6) Define recursion with example?
A6) The process through which a function calls itself is known as recursion. We utilize recursion to break down larger issues into smaller ones. One thing to keep in mind is that the recursive technique can only be used if each sub-problem follows the same patterns.
There are two pieces to a recursive function. The recursive case and the base case. The basic case is utilized to finish the repeating task. If the base case isn't specified, the function will repeat indefinitely.
When we call a function in a computer program, the value of the program counter is saved in the internal stack before we jump into the function area. It pulls out the address and assigns it to the program counter after completing the operation, then resumes the task. It will save the address several times throughout a recursive call and then jump to the next function call statement. If one of the base cases isn't declared, it will repeat over and over, storing the address in the stack. If the stack runs out of space, it will throw an error called "Internal Stack Overflow."
Finding the factorial of a number is an example of a recursive call. The factorial of an integer n = n! is the same as n * (n-1)!, as we can see. , which is same to n * (n - 1) * (n - 2)! So, if factorial is a function, it will be run repeatedly, but the parameter will be reduced by one. It will return 1 if the parameter is 1 or 0. This could be the recursion's starting point.
Example
#include<iostream>
Using namespace std;
Long fact(long n){
If(n <= 1)
Return 1;
Return n * fact(n-1);
}
Main(){
Cout << "Factorial of 6: " << fact(6);
}
Output
Factorial of 6: 720
Q7) How to represent a queue using an array?
A7) Using linear arrays, we can easily describe a queue. In the case of every queue, there are two variables to consider: front and back. In a queue, the front and back variables indicate the location from which insertions and deletions are made. The initial value of front and queue is -1, which indicates that the queue is empty. The next figure shows an array representation of a queue with 5 elements and their respective front and rear values.
Fig 5: Queue
The line of characters that make up the English word "HELLO" is depicted in the diagram above. Because no deletions have been made in the queue to date, the value of front remains -1. When an insertion is performed in the queue, however, the value of rear increases by one. After entering one element into the queue depicted in the above picture, the queue will appear as follows. The value of the rear will increase to 5, while the value of the front will remain unchanged.
Fig 6: Queue after inserting element
The value of front will grow from -1 to 0 if an element is deleted. The queue, on the other hand, will resemble the following.
Fig 7: Queue after deleting element
Algorithm to insert any element in a queue
Compare rear to max - 1 to see if the queue is already full. If this is the case, an overflow error will be returned.
If the item is to be inserted as the first element in the list, set the front and back values to 0 and insert the item at the back end.
Otherwise, keep increasing the value of rear and inserting each element with rear as the index one by one.
Algorithm
Step 1: IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: Set QUEUE[REAR] = NUM
Step 4: EXIT
C function
Void insert (int queue[], int max, int front, int rear, int item)
{
If (rear + 1 == max)
{
Printf("overflow");
}
Else
{
If(front == -1 && rear == -1)
{
Front = 0;
Rear = 0;
}
Else
{
Rear = rear + 1;
}
Queue[rear]=item;
}
}
Algorithm to delete an element from the queue
Write an underflow message and leave if the value of front is -1 or greater than the value of rear.
Otherwise, keep increasing the front's value and returning the item at the front of the queue each time.
Algorithm
● Step 1: IF FRONT = -1 or FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
● Step 2: EXIT
C function
Int delete (int queue[], int max, int front, int rear)
{
Int y;
If (front == -1 || front > rear)
{
Printf("underflow");
}
Else
{
y = queue[front];
If(front == rear)
{
Front = rear = -1;
Else
Front = front + 1;
}
Return y;
}
}
Q8) How to represent a queue using a linked list?
A8) The array method cannot be used for large scale applications when queues are established due to the limitations. The linked list version of queue is one of the alternatives to array implementation.
Each node of a linked queue is made up of two parts: the data part and the link part.
In the memory of the linked queue, there are two pointers: front pointer and rear pointer. The front pointer contains the location of the queue's first element, while the back pointer contains the address of the queue's last member.
The linked depiction of the queue is depicted in the diagram below.
Fig 8: Linked queue
Q9) Write about insertion operation?
A9) By adding an element to the end of the queue, the insert operation appends it. The new element will be the queue's last element.
To begin, use the following line to allocate memory for the new node ptr.
Ptr = (struct node *) malloc (sizeof(struct node));
There are two possible scenarios for adding this new node ptr to the connected queue.
We inject an element into an empty queue in the first scenario. The condition front = NULL gets true in this scenario.
The queue in the second scenario has more than one element. The condition front = NULL is no longer true. We need to change the end pointer rear in this case such that the next pointer of rear points to the new node ptr. Because this is a linked queue, the rear pointer must also point to the newly inserted node ptr. We must additionally set the rear pointer's next pointer to NULL.
Algorithm
● Step 1: Allocate the space for the new node PTR
● Step 2: SET PTR -> DATA = VAL
● Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
● Step 4: END
C function
Void insert(struct node *ptr, int item; )
{
Ptr = (struct node *) malloc (sizeof(struct node));
If(ptr == NULL)
{
Printf("\nOVERFLOW\n");
Return;
}
Else
{
Ptr -> data = item;
If(front == NULL)
{
Front = ptr;
Rear = ptr;
Front -> next = NULL;
Rear -> next = NULL;
}
Else
{
Rear -> next = ptr;
Rear = ptr;
Rear->next = NULL;
}
}
}
Q10) What is deletion operation in queue?
A10) The deletion action removes the initial inserted element from all queue elements. To begin, we must determine whether the list is empty or not. If the list is empty, the condition front == NULL becomes true; in this case, we simply write underflow on the console and quit.
Otherwise, the element pointed by the pointer front will be deleted. Copy the node pointed by the front pointer into the pointer ptr for this purpose. Shift the front pointer to the next node and release the node referenced by node ptr. The following statements are used to do this.
Algorithm
● Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
● Step 2: SET PTR = FRONT
● Step 3: SET FRONT = FRONT -> NEXT
● Step 4: FREE PTR
● Step 5: END
C function
Void delete (struct node *ptr)
{
If(front == NULL)
{
Printf("\nUNDERFLOW\n");
Return;
}
Else
{
Ptr = front;
Front = front -> next;
Free(ptr);
}
}
Q11) Why was the concept of the circular queue introduced?
A11) There was one limitation in the array implementation of Queue. If the rear reaches to the end position of the Queue then there might be the possibility that some vacant spaces are left in the beginning which cannot be utilized. So, to overcome such limitations, the concept of the circular queue was introduced.
Fig 9: Circular queue
As we can see in the above image, the rear is at the last position of the Queue and the front is pointing somewhere rather than the 0th position. In the above array, there are only two elements and the other three positions are empty. The rear is at the last position of the Queue; if we try to insert the element then it will show that there are no empty spaces in the Queue. There is one solution to avoid such wastage of memory space by shifting both the elements at the left and adjust the front and rear end accordingly. It is not a practically good approach because shifting all the elements will consume lots of time. The efficient approach to avoid the wastage of the memory is to use the circular queue data structure.
Q12) What is a Circular Queue?
A12) A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out) principle except that the last position is connected to the first position in a circular queue that forms a circle. It is also known as a Ring Buffer.
Operations on Circular Queue
The following are the operations that can be performed on a circular queue:
● Front: It is used to get the front element from the Queue.
● Rear: It is used to get the rear element from the Queue.
● enQueue(value): This function is used to insert the new value in the Queue. The new element is always inserted from the rear end.
● deQueue(): This function deletes an element from the Queue. The deletion in a Queue always takes place from the front end.
Applications of Circular Queue
The circular Queue can be used in the following scenarios:
● Memory management: The circular queue provides memory management. As we have already seen in the linear queue, the memory is not managed very efficiently. But in case of a circular queue, the memory is managed efficiently by placing the elements in a location which is unused.
● CPU Scheduling: The operating system also uses the circular queue to insert the processes and then execute them.
● Traffic system: In a computer-control traffic system, traffic lights are one of the best examples of the circular queue. Each traffic light gets ON one by one after every interval of time. Like red light gets ON for one minute then yellow light for one minute and then green light. After the green light, the red light gets ON.
Q13) Describe dequeue?
A13) The dequeue stands for Double Ended Queue. In the queue, the insertion takes place from one end while the deletion takes place from another end. The end at which the insertion occurs is known as the rear end whereas the end at which the deletion occurs is known as the front end.
Fig 10: Dequeue
Deque is a linear data structure in which the insertion and deletion operations are performed from both ends. We can say that deque is a generalized version of the queue.
Let's look at some properties of deque
● Deque can be used both as stack and queue as it allows the insertion and deletion operations on both ends.
● In deque, the insertion and deletion operation can be performed from one side. The stack follows the LIFO rule in which both the insertion and deletion can be performed only from one end; therefore, we conclude that deque can be considered as a stack.
● In deque, the insertion can be performed on one end, and the deletion can be done on another end. The queue follows the FIFO rule in which the element is inserted on one end and deleted from another end. Therefore, we conclude that the deque can also be considered as the queue.
There are two types of Queues, Input-restricted queue, and output-restricted queue.
- Input-restricted queue: The input-restricted queue means that some restrictions are applied to the insertion. In input-restricted queue, the insertion is applied to one end while the deletion is applied from both the ends.
2. Output-restricted queue: The output-restricted queue means that some restrictions are applied to the deletion operation. In an output-restricted queue, the deletion can be applied only from one end, whereas the insertion is possible from both ends.
Operations on Deque
The following are the operations applied on deque:
● Insert at front
● Delete from end
● Insert at rear
● Delete from rear
Other than insertion and deletion, we can also perform peek operation in deque. Through peek operation, we can get the front and the rear element of the dequeue.
We can perform two more operations on dequeue:
● isFull(): This function returns a true value if the stack is full; otherwise, it returns a false value.
● isEmpty(): This function returns a true value if the stack is empty; otherwise it returns a false value.
Q14) Explain priority queue with example?
A14) A priority queue is an abstract data type that behaves similarly to the normal queue except that each element has some priority, i.e., the element with the highest priority would come first in a priority queue. The priority of the elements in a priority queue will determine the order in which elements are removed from the priority queue.
The priority queue supports only comparable elements, which means that the elements are either arranged in an ascending or descending order.
For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a priority queue with an ordering imposed on the values from least to the greatest. Therefore, the 1 number would be having the highest priority while 22 will be having the lowest priority.
Characteristics of a Priority queue
A priority queue is an extension of a queue that contains the following characteristics:
● Every element in a priority queue has some priority associated with it.
● An element with the higher priority will be deleted before the deletion of the lesser priority.
● If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.
Let's understand the priority queue through an example.
We have a priority queue that contains the following values:
1, 3, 4, 8, 14, 22
All the values are arranged in ascending order. Now, we will observe how the priority queue will look after performing the following operations:
● poll(): This function will remove the highest priority element from the priority queue. In the above priority queue, the '1' element has the highest priority, so it will be removed from the priority queue.
● add(2): This function will insert the '2' element in a priority queue. As 2 is the smallest element among all the numbers so it will obtain the highest priority.
● poll(): It will remove the '2' element from the priority queue as it has the highest priority queue.
● add(5): It will insert 5 elements after 4 as 5 is larger than 4 and lesser than 8, so it will obtain the third highest priority in a priority queue.
Q15) Write the Types of Priority Queue?
A15) There are two types of priority queue:
● Ascending order priority queue: In ascending order priority queue, a lower priority number is given as a higher priority in a priority. For example, we take the numbers from 1 to 5 arranged in an ascending order like 1,2,3,4,5; therefore, the smallest number, i.e., 1 is given as the highest priority in a priority queue.
● Descending order priority queue: In descending order priority queue, a higher priority number is given as a higher priority in a priority. For example, we take the numbers from 1 to 5 arranged in descending order like 5, 4, 3, 2, 1; therefore, the largest number, i.e., 5 is given as the highest priority in a priority queue.
Q16) How representation of priority queue?
A16) Now, we will see how to represent the priority queue through a one-way list.
We will create the priority queue by using the list given below in which INFO list contains the data elements, PRN list contains the priority numbers of each data element available in the INFO list, and LINK basically contains the address of the next node.
Let's create the priority queue step by step.
In the case of priority queue, lower priority number is considered the higher priority, i.e., lower priority number = higher priority.
Step 1: In the list, lower priority number is 1, whose data value is 333, so it will be inserted in the list as shown in the below diagram:
Step 2: After inserting 333, priority number 2 is having a higher priority, and data values associated with this priority are 222 and 111. So, this data will be inserted based on the FIFO principle; therefore 222 will be added first and then 111.
Step 3: After inserting the elements of priority 2, the next higher priority number is 4 and data elements associated with 4 priority numbers are 444, 555, 777. In this case, elements would be inserted based on the FIFO principle; therefore, 444 will be added first, then 555, and then 777.
Step 4: After inserting the elements of priority 4, the next higher priority number is 5, and the value associated with priority 5 is 666, so it will be inserted at the end of the queue.
Implementation of Priority Queue
The priority queue can be implemented in four ways that include arrays, linked list, heap data structure and binary search tree. The heap data structure is the most efficient way of implementing the priority queue, so we will implement the priority queue using a heap data structure.
Q17) What is singly linked list?
A17) In programming, it is the most widely used linked list. When we talk about a linked list, we're talking about a singly linked list. The singly linked list is a data structure that is divided into two parts: the data portion and the address part, which contains the address of the next or successor node. A pointer is another name for the address component of a node.
Assume we have three nodes with addresses of 100, 200, and 300, respectively. The following diagram depicts the representation of three nodes as a linked list:
Fig 11: Singly linked list
In the diagram above, we can see three separate nodes with addresses of 100, 200, and 300, respectively. The first node has the address of the next node, which is 200, the second has the address of the last node, which is 300, and the third has the NULL value in its address portion because it does not point to any node. A head pointer is a pointer that stores the address of the first node.
Because there is just one link in the linked list depicted in the figure, it is referred to as a singly linked list. Just forward traversal is permitted in this list; we can't go backwards because there is only one link in the list.
Representation of the node in a singly linked list
Struct node
{
Int data;
Struct node *next;
}
In the above diagram, we've constructed a user-made structure called a node, which has two members: one is data of integer type, and the other is the node type's pointer (next).
Q18) Write about doubly linked list?
A18) The doubly linked list, as its name implies, has two pointers. The doubly linked list can be described as a three-part linear data structure: the data component, the address part, and the other two address parts. A doubly linked list, in other terms, is a list with three parts in each node: one data portion, a pointer to the previous node, and a pointer to the next node.
Let's pretend we have three nodes with addresses of 100, 200, and 300, respectively. The representation of these nodes in a doubly-linked list is shown below:
Fig 12: Doubly linked list
The node in a doubly-linked list contains two address portions, as shown in the diagram above; one part keeps the address of the next node, while the other half stores the address of the previous node. The address component of the first node in the doubly linked list is NULL, indicating that the prior node's address is NULL.
Representation of the node in a doubly linked list
Struct node
{
Int data;
Struct node *next;
Struct node *prev;
}
In the above representation, we've constructed a user-defined structure called a node, which has three members: one is data of integer type, and the other two are pointers of the node type, i.e. next and prev. The address of the next node is stored in the next pointer variable, whereas the address of the previous node is stored in the prev pointer variable. The type of both the pointers, i.e., next and prev is struct node as both the pointers are storing the address of the node of the struct node type.
Q19) What is Circular linked list?
A19) A singly linked list is a type of circular linked list. The sole difference between a singly linked list and a circular linked list is that the last node in a singly linked list does not point to any other node, therefore its link portion is NULL. The circular linked list, on the other hand, is a list in which the last node connects to the first node, and the address of the first node is stored in the link section of the last node.
There are no nodes at the beginning or finish of the circular linked list. We can travel in either way, backwards or forwards. The following is a diagrammatic illustration of the circular linked list:
Struct node
{
Int data;
Struct node *next;
}
A circular linked list is a collection of elements in which each node is linked to the next and the last node is linked to the first. The circular linked list will be represented similarly to the singly linked list, as demonstrated below:
Fig 13: Circular linked list
Q20) Write the operation on linked list?
A20) Operation on linked list
● In a linked list, the search operation is used to locate a certain entry.
● On a linked list structure, the most common search is sequential search.
● If the element is located, the search procedure is declared successful.
● The search will fail if the element is not found.
// Search a node
Bool searchNode(struct Node** head_ref, int key) {
Struct Node* current = *head_ref;
While (current != NULL) {
If (current->data == key) return true;
Current = current->next;
}
Return false;
}
Update
● This is a type of linked list operation in C/C++ in which the data section of the needed node is replaced with the given value.
● We'll do this by traversing the linked list until we identify a node that corresponds to the node that needs to be modified.
Void updateNode(Node* head, int value, int newValue)
{
// temp is the traversing node
Node* temp = head;
While(temp != NULL)
{
// If the node matches the given node to be updated.
If( temp->data == val)
{
// Updating the data part of the node with the new value.
Temp->data = newVal;
Return;
}
Temp = temp->next;
}
}
Application
● Queues, stacks, and graphs can all be implemented using Linked Lists.
● The forward and backward navigation buttons in the toolbar employ doubly-linked lists.
Unit - 2
Abstract Data Types (ADTs) Stack
Q1) What is the abstract data type?
A1) The abstract data type is a special kind of datatype, whose behavior is defined by a set of values and set of operations. The keyword “Abstract” is used as we can use these data types, we can perform different operations. But how those operations are working is totally hidden from the user. The ADT is made of primitive data types, but operation logics are hidden.
Here we will see the stack ADT. These are a few operations or functions of the Stack ADT.
● isFull(), This is used to check whether stack is full or not
● isEmpty(), This is used to check whether stack is empty or not
● push(x), This is used to push x into the stack
● pop(), This is used to delete one element from top of the stack
● peek(), This is used to get the top most element of the stack
● size(), this function is used to get number of elements present into the stack
Example
#include<iostream>
#include<stack>
Using namespace std;
Main(){
Stack<int> stk;
If(stk.empty()){
Cout << "Stack is empty" << endl;
} else {
Cout << "Stack is not empty" << endl;
}
//insert elements into stack
Stk.push(10);
Stk.push(20);
Stk.push(30);
Stk.push(40);
Stk.push(50);
Cout << "Size of the stack: " << stk.size() << endl;
//pop and display elements
While(!stk.empty()){
Int item = stk.top(); // same as peek operation
Stk.pop();
Cout << item << " ";
}
}
Output
Stack is empty
Size of the stack: 5
50 40 30 20 10
Q2) What do you mean by push and pop?
A2) PUSH operation
The steps involved in the PUSH operation is given below:
● Before inserting an element in a stack, we check whether the stack is full.
● If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.
● When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
● When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, and the element will be placed at the new position of the top.
● The elements will be inserted until we reach the max size of the stack.
Fig 1: Push Operation Example
POP operation
The steps involved in the POP operation is given below:
● Before deleting the element from the stack, we check whether the stack is empty.
● If we try to delete the element from the empty stack, then the underflow condition occurs.
● If the stack is not empty, we first access the element which is pointed by the top
● Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.
Fig 2: Pop Operation example
Q3) How to represent a stack using an array?
A3) The stack is created using the array in array implementation. Arrays are used to accomplish all of the operations on the stack. Let's look at how each operation can be accomplished utilizing an array data structure on the stack.
Adding an element onto the stack (push operation)
A push operation occurs when an element is added to the top of a stack. Two steps are involved in a push operation.
- Increase the value of the variable Top to allow it to refer to the next memory address.
- Add an element to the top of the incremented list. Adding a new element to the top of the stack is referred to as this.
When we try to put an element into a totally loaded stack, the stack overflows. As a result, our main function must always avoid stack overflow.
Algorithm
Begin
If top = n then stack full
Top = top + 1
Stack (top) : = item;
End
Implementation in C language
Void push (int val,int n) //n is size of the stack
{
If (top == n )
Printf("\n Overflow");
Else
{
Top = top +1;
Stack[top] = val;
}
}
Deletion of an element from a stack (Pop operation)
The pop action removes an element from the top of the stack. When an item is removed from the stack, the value of the variable top is increased by one. The stack's topmost element is saved in a separate variable, and then the top is decremented by one. As a result, the operation returns the removed value that was previously saved in another variable.
When we try to delete an element from an already empty stack, we get an underflow condition.
Algorithm
Begin
If top = 0 then stack empty;
Item := stack(top);
Top = top - 1;
End;
Implementation in C language
Int pop ()
{
If(top == -1)
{
Printf("Underflow");
Return 0;
}
Else
{
Return stack[top - - ];
}
}
Visiting each element of the stack (Peek operation)
Returning the element at the top of the stack without removing it is known as a peek operation. If we try to return the top piece from an already empty stack, we may encounter an underflow problem.
Algorithm
PEEK (STACK, TOP)
Begin
If top = -1 then stack empty
Item = stack[top]
Return item
End
Implementation in C language
Int peek()
{
If (top == -1)
{
Printf("Underflow");
Return 0;
}
Else
{
Return stack [top];
}
}
Q4) How to represent stack using linked list?
A4) To implement stack, we can use a linked list instead of an array. The memory is dynamically allocated with a linked list. However, the temporal complexity of all operations, such as push, pop, and peek, is the same in all scenarios.
The nodes in a linked list implementation of a stack are kept in memory in a non-contiguous manner. Each node on the stack has a pointer to its immediate successor node. If there isn't enough room in the memory heap to create a node, the stack is said to have overflown.
Fig 3: Linked list
Adding a node to the stack (Push operation)
The address field of the topmost node in the stack is always null. Let's look at how each action is carried out in the stack's linked list implementation.
The push action is used to add a node to the stack. Pushing an element to a stack in a linked list differs from pushing an element to a stack in an array. The following procedures are required to push an element onto the stack.
- First, make a node and allocate memory to it.
- If the list is empty, the item should be moved to the top as the list's first node. This involves giving the data component of the node a value and giving the address part of the node a null value.
- If the list already has some nodes, we must place the new element at the beginning of the list (to not violate the property of the stack). Assign the address of the starting element to the address field of the new node for this purpose, and make the new node the list's starting node.
C Implementation
Void push ()
{
Int val;
Struct node *ptr =(struct node*)malloc(sizeof(struct node));
If(ptr == NULL)
{
Printf("not able to push the element");
}
Else
{
Printf("Enter the value");
Scanf("%d",&val);
If(head==NULL)
{
Ptr->val = val;
Ptr -> next = NULL;
Head=ptr;
}
Else
{
Ptr->val = val;
Ptr->next = head;
Head=ptr;
}
Printf("Item pushed");
}
}
Deleting a node from the stack (POP operation)
The pop operation is used to remove a node from the top of the stack. The deletion of a node from the stack's linked list implementation differs from the array implementation. To remove an element from the stack, we must first perform the following steps:
- Check for the underflow condition - When we try to pop from an already empty stack, we get an underflow problem. If the list's head pointer points to null, the stack will be empty.
- Adjust the head pointer accordingly - Because the elements in a stack are only popped from one end, the value stored in the head pointer must be removed, and the node must be released. The head node's next node now serves as the head node.
C Implementation
Void pop()
{
Int item;
Struct node *ptr;
If (head == NULL)
{
Printf("Underflow");
}
Else
{
Item = head->val;
Ptr = head;
Head = head->next;
Free(ptr);
Printf("Item popped");
}
}
Q5) Write the application of stack?
A5) The following are the applications of the stack:
● Balancing of symbols: Stack is used for balancing a symbol. For example, we have the following program:
- Int main()
- {
- Cout<<"Hello";
- Coût<<"java point";
- }
As we know, each program has an opening and closing braces; when the opening braces come, we push the braces in a stack, and when the closing braces appear, we pop the opening braces from the stack. Therefore, the net value comes out to be zero. If any symbol is left in the stack, it means that some syntax occurs in a program.
● String reversal: Stack is also used for reversing a string. For example, we want to reverse a "java point" string, so we can achieve this with the help of a stack.
First, we push all the characters of the string in a stack until we reach the null character. After pushing all the characters, we start taking out the character one by one until we reach the bottom of the stack.
● UNDO/REDO: It can also be used for performing UNDO/REDO operations. For example, we have an editor in which we write 'a', then 'b', and then 'c'; therefore, the text written in an editor is abc. So, there are three states, a, ab, and abc, which are stored in a stack. There would be two stacks in which one stack shows UNDO state, and the other shows REDO state.
If we want to perform a UNDO operation, and want to achieve an 'ab' state, then we implement a pop operation.
● Recursion: The recursion means that the function is calling itself again. To maintain the previous states, the compiler creates a system stack in which all the previous records of the function are maintained.
● DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the stack data structure.
● Backtracking: Suppose we have to create a path to solve a maze problem. If we are moving in a particular path, and we realize that we come on the wrong way. In order to come at the beginning of the path to create a new path, we have to use the stack data structure.
● Expression conversion: Stack can also be used for expression conversion. This is one of the most important applications of stack. The list of the expression conversion is given below:
● Infix to prefix
● Infix to postfix
● Prefix to infix
● Prefix to postfix
● Postfix to infix
● Memory management: The stack manages the memory. The memory is assigned in the contiguous memory blocks. The memory is known as stack memory as all the variables are assigned in a function called stack memory. The memory size assigned to the program is known to the compiler. When the function is created, all its variables are assigned in the stack memory. When the function completes its execution, all the variables assigned in the stack are released.
Q6) Define recursion with example?
A6) The process through which a function calls itself is known as recursion. We utilize recursion to break down larger issues into smaller ones. One thing to keep in mind is that the recursive technique can only be used if each sub-problem follows the same patterns.
There are two pieces to a recursive function. The recursive case and the base case. The basic case is utilized to finish the repeating task. If the base case isn't specified, the function will repeat indefinitely.
When we call a function in a computer program, the value of the program counter is saved in the internal stack before we jump into the function area. It pulls out the address and assigns it to the program counter after completing the operation, then resumes the task. It will save the address several times throughout a recursive call and then jump to the next function call statement. If one of the base cases isn't declared, it will repeat over and over, storing the address in the stack. If the stack runs out of space, it will throw an error called "Internal Stack Overflow."
Finding the factorial of a number is an example of a recursive call. The factorial of an integer n = n! is the same as n * (n-1)!, as we can see. , which is same to n * (n - 1) * (n - 2)! So, if factorial is a function, it will be run repeatedly, but the parameter will be reduced by one. It will return 1 if the parameter is 1 or 0. This could be the recursion's starting point.
Example
#include<iostream>
Using namespace std;
Long fact(long n){
If(n <= 1)
Return 1;
Return n * fact(n-1);
}
Main(){
Cout << "Factorial of 6: " << fact(6);
}
Output
Factorial of 6: 720
Q7) How to represent a queue using an array?
A7) Using linear arrays, we can easily describe a queue. In the case of every queue, there are two variables to consider: front and back. In a queue, the front and back variables indicate the location from which insertions and deletions are made. The initial value of front and queue is -1, which indicates that the queue is empty. The next figure shows an array representation of a queue with 5 elements and their respective front and rear values.
Fig 5: Queue
The line of characters that make up the English word "HELLO" is depicted in the diagram above. Because no deletions have been made in the queue to date, the value of front remains -1. When an insertion is performed in the queue, however, the value of rear increases by one. After entering one element into the queue depicted in the above picture, the queue will appear as follows. The value of the rear will increase to 5, while the value of the front will remain unchanged.
Fig 6: Queue after inserting element
The value of front will grow from -1 to 0 if an element is deleted. The queue, on the other hand, will resemble the following.
Fig 7: Queue after deleting element
Algorithm to insert any element in a queue
Compare rear to max - 1 to see if the queue is already full. If this is the case, an overflow error will be returned.
If the item is to be inserted as the first element in the list, set the front and back values to 0 and insert the item at the back end.
Otherwise, keep increasing the value of rear and inserting each element with rear as the index one by one.
Algorithm
Step 1: IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: Set QUEUE[REAR] = NUM
Step 4: EXIT
C function
Void insert (int queue[], int max, int front, int rear, int item)
{
If (rear + 1 == max)
{
Printf("overflow");
}
Else
{
If(front == -1 && rear == -1)
{
Front = 0;
Rear = 0;
}
Else
{
Rear = rear + 1;
}
Queue[rear]=item;
}
}
Algorithm to delete an element from the queue
Write an underflow message and leave if the value of front is -1 or greater than the value of rear.
Otherwise, keep increasing the front's value and returning the item at the front of the queue each time.
Algorithm
● Step 1: IF FRONT = -1 or FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
● Step 2: EXIT
C function
Int delete (int queue[], int max, int front, int rear)
{
Int y;
If (front == -1 || front > rear)
{
Printf("underflow");
}
Else
{
y = queue[front];
If(front == rear)
{
Front = rear = -1;
Else
Front = front + 1;
}
Return y;
}
}
Q8) How to represent a queue using a linked list?
A8) The array method cannot be used for large scale applications when queues are established due to the limitations. The linked list version of queue is one of the alternatives to array implementation.
Each node of a linked queue is made up of two parts: the data part and the link part.
In the memory of the linked queue, there are two pointers: front pointer and rear pointer. The front pointer contains the location of the queue's first element, while the back pointer contains the address of the queue's last member.
The linked depiction of the queue is depicted in the diagram below.
Fig 8: Linked queue
Q9) Write about insertion operation?
A9) By adding an element to the end of the queue, the insert operation appends it. The new element will be the queue's last element.
To begin, use the following line to allocate memory for the new node ptr.
Ptr = (struct node *) malloc (sizeof(struct node));
There are two possible scenarios for adding this new node ptr to the connected queue.
We inject an element into an empty queue in the first scenario. The condition front = NULL gets true in this scenario.
The queue in the second scenario has more than one element. The condition front = NULL is no longer true. We need to change the end pointer rear in this case such that the next pointer of rear points to the new node ptr. Because this is a linked queue, the rear pointer must also point to the newly inserted node ptr. We must additionally set the rear pointer's next pointer to NULL.
Algorithm
● Step 1: Allocate the space for the new node PTR
● Step 2: SET PTR -> DATA = VAL
● Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
● Step 4: END
C function
Void insert(struct node *ptr, int item; )
{
Ptr = (struct node *) malloc (sizeof(struct node));
If(ptr == NULL)
{
Printf("\nOVERFLOW\n");
Return;
}
Else
{
Ptr -> data = item;
If(front == NULL)
{
Front = ptr;
Rear = ptr;
Front -> next = NULL;
Rear -> next = NULL;
}
Else
{
Rear -> next = ptr;
Rear = ptr;
Rear->next = NULL;
}
}
}
Q10) What is deletion operation in queue?
A10) The deletion action removes the initial inserted element from all queue elements. To begin, we must determine whether the list is empty or not. If the list is empty, the condition front == NULL becomes true; in this case, we simply write underflow on the console and quit.
Otherwise, the element pointed by the pointer front will be deleted. Copy the node pointed by the front pointer into the pointer ptr for this purpose. Shift the front pointer to the next node and release the node referenced by node ptr. The following statements are used to do this.
Algorithm
● Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
● Step 2: SET PTR = FRONT
● Step 3: SET FRONT = FRONT -> NEXT
● Step 4: FREE PTR
● Step 5: END
C function
Void delete (struct node *ptr)
{
If(front == NULL)
{
Printf("\nUNDERFLOW\n");
Return;
}
Else
{
Ptr = front;
Front = front -> next;
Free(ptr);
}
}
Q11) Why was the concept of the circular queue introduced?
A11) There was one limitation in the array implementation of Queue. If the rear reaches to the end position of the Queue then there might be the possibility that some vacant spaces are left in the beginning which cannot be utilized. So, to overcome such limitations, the concept of the circular queue was introduced.
Fig 9: Circular queue
As we can see in the above image, the rear is at the last position of the Queue and the front is pointing somewhere rather than the 0th position. In the above array, there are only two elements and the other three positions are empty. The rear is at the last position of the Queue; if we try to insert the element then it will show that there are no empty spaces in the Queue. There is one solution to avoid such wastage of memory space by shifting both the elements at the left and adjust the front and rear end accordingly. It is not a practically good approach because shifting all the elements will consume lots of time. The efficient approach to avoid the wastage of the memory is to use the circular queue data structure.
Q12) What is a Circular Queue?
A12) A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out) principle except that the last position is connected to the first position in a circular queue that forms a circle. It is also known as a Ring Buffer.
Operations on Circular Queue
The following are the operations that can be performed on a circular queue:
● Front: It is used to get the front element from the Queue.
● Rear: It is used to get the rear element from the Queue.
● enQueue(value): This function is used to insert the new value in the Queue. The new element is always inserted from the rear end.
● deQueue(): This function deletes an element from the Queue. The deletion in a Queue always takes place from the front end.
Applications of Circular Queue
The circular Queue can be used in the following scenarios:
● Memory management: The circular queue provides memory management. As we have already seen in the linear queue, the memory is not managed very efficiently. But in case of a circular queue, the memory is managed efficiently by placing the elements in a location which is unused.
● CPU Scheduling: The operating system also uses the circular queue to insert the processes and then execute them.
● Traffic system: In a computer-control traffic system, traffic lights are one of the best examples of the circular queue. Each traffic light gets ON one by one after every interval of time. Like red light gets ON for one minute then yellow light for one minute and then green light. After the green light, the red light gets ON.
Q13) Describe dequeue?
A13) The dequeue stands for Double Ended Queue. In the queue, the insertion takes place from one end while the deletion takes place from another end. The end at which the insertion occurs is known as the rear end whereas the end at which the deletion occurs is known as the front end.
Fig 10: Dequeue
Deque is a linear data structure in which the insertion and deletion operations are performed from both ends. We can say that deque is a generalized version of the queue.
Let's look at some properties of deque
● Deque can be used both as stack and queue as it allows the insertion and deletion operations on both ends.
● In deque, the insertion and deletion operation can be performed from one side. The stack follows the LIFO rule in which both the insertion and deletion can be performed only from one end; therefore, we conclude that deque can be considered as a stack.
● In deque, the insertion can be performed on one end, and the deletion can be done on another end. The queue follows the FIFO rule in which the element is inserted on one end and deleted from another end. Therefore, we conclude that the deque can also be considered as the queue.
There are two types of Queues, Input-restricted queue, and output-restricted queue.
- Input-restricted queue: The input-restricted queue means that some restrictions are applied to the insertion. In input-restricted queue, the insertion is applied to one end while the deletion is applied from both the ends.
2. Output-restricted queue: The output-restricted queue means that some restrictions are applied to the deletion operation. In an output-restricted queue, the deletion can be applied only from one end, whereas the insertion is possible from both ends.
Operations on Deque
The following are the operations applied on deque:
● Insert at front
● Delete from end
● Insert at rear
● Delete from rear
Other than insertion and deletion, we can also perform peek operation in deque. Through peek operation, we can get the front and the rear element of the dequeue.
We can perform two more operations on dequeue:
● isFull(): This function returns a true value if the stack is full; otherwise, it returns a false value.
● isEmpty(): This function returns a true value if the stack is empty; otherwise it returns a false value.
Q14) Explain priority queue with example?
A14) A priority queue is an abstract data type that behaves similarly to the normal queue except that each element has some priority, i.e., the element with the highest priority would come first in a priority queue. The priority of the elements in a priority queue will determine the order in which elements are removed from the priority queue.
The priority queue supports only comparable elements, which means that the elements are either arranged in an ascending or descending order.
For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a priority queue with an ordering imposed on the values from least to the greatest. Therefore, the 1 number would be having the highest priority while 22 will be having the lowest priority.
Characteristics of a Priority queue
A priority queue is an extension of a queue that contains the following characteristics:
● Every element in a priority queue has some priority associated with it.
● An element with the higher priority will be deleted before the deletion of the lesser priority.
● If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.
Let's understand the priority queue through an example.
We have a priority queue that contains the following values:
1, 3, 4, 8, 14, 22
All the values are arranged in ascending order. Now, we will observe how the priority queue will look after performing the following operations:
● poll(): This function will remove the highest priority element from the priority queue. In the above priority queue, the '1' element has the highest priority, so it will be removed from the priority queue.
● add(2): This function will insert the '2' element in a priority queue. As 2 is the smallest element among all the numbers so it will obtain the highest priority.
● poll(): It will remove the '2' element from the priority queue as it has the highest priority queue.
● add(5): It will insert 5 elements after 4 as 5 is larger than 4 and lesser than 8, so it will obtain the third highest priority in a priority queue.
Q15) Write the Types of Priority Queue?
A15) There are two types of priority queue:
● Ascending order priority queue: In ascending order priority queue, a lower priority number is given as a higher priority in a priority. For example, we take the numbers from 1 to 5 arranged in an ascending order like 1,2,3,4,5; therefore, the smallest number, i.e., 1 is given as the highest priority in a priority queue.
● Descending order priority queue: In descending order priority queue, a higher priority number is given as a higher priority in a priority. For example, we take the numbers from 1 to 5 arranged in descending order like 5, 4, 3, 2, 1; therefore, the largest number, i.e., 5 is given as the highest priority in a priority queue.
Q16) How representation of priority queue?
A16) Now, we will see how to represent the priority queue through a one-way list.
We will create the priority queue by using the list given below in which INFO list contains the data elements, PRN list contains the priority numbers of each data element available in the INFO list, and LINK basically contains the address of the next node.
Let's create the priority queue step by step.
In the case of priority queue, lower priority number is considered the higher priority, i.e., lower priority number = higher priority.
Step 1: In the list, lower priority number is 1, whose data value is 333, so it will be inserted in the list as shown in the below diagram:
Step 2: After inserting 333, priority number 2 is having a higher priority, and data values associated with this priority are 222 and 111. So, this data will be inserted based on the FIFO principle; therefore 222 will be added first and then 111.
Step 3: After inserting the elements of priority 2, the next higher priority number is 4 and data elements associated with 4 priority numbers are 444, 555, 777. In this case, elements would be inserted based on the FIFO principle; therefore, 444 will be added first, then 555, and then 777.
Step 4: After inserting the elements of priority 4, the next higher priority number is 5, and the value associated with priority 5 is 666, so it will be inserted at the end of the queue.
Implementation of Priority Queue
The priority queue can be implemented in four ways that include arrays, linked list, heap data structure and binary search tree. The heap data structure is the most efficient way of implementing the priority queue, so we will implement the priority queue using a heap data structure.
Q17) What is singly linked list?
A17) In programming, it is the most widely used linked list. When we talk about a linked list, we're talking about a singly linked list. The singly linked list is a data structure that is divided into two parts: the data portion and the address part, which contains the address of the next or successor node. A pointer is another name for the address component of a node.
Assume we have three nodes with addresses of 100, 200, and 300, respectively. The following diagram depicts the representation of three nodes as a linked list:
Fig 11: Singly linked list
In the diagram above, we can see three separate nodes with addresses of 100, 200, and 300, respectively. The first node has the address of the next node, which is 200, the second has the address of the last node, which is 300, and the third has the NULL value in its address portion because it does not point to any node. A head pointer is a pointer that stores the address of the first node.
Because there is just one link in the linked list depicted in the figure, it is referred to as a singly linked list. Just forward traversal is permitted in this list; we can't go backwards because there is only one link in the list.
Representation of the node in a singly linked list
Struct node
{
Int data;
Struct node *next;
}
In the above diagram, we've constructed a user-made structure called a node, which has two members: one is data of integer type, and the other is the node type's pointer (next).
Q18) Write about doubly linked list?
A18) The doubly linked list, as its name implies, has two pointers. The doubly linked list can be described as a three-part linear data structure: the data component, the address part, and the other two address parts. A doubly linked list, in other terms, is a list with three parts in each node: one data portion, a pointer to the previous node, and a pointer to the next node.
Let's pretend we have three nodes with addresses of 100, 200, and 300, respectively. The representation of these nodes in a doubly-linked list is shown below:
Fig 12: Doubly linked list
The node in a doubly-linked list contains two address portions, as shown in the diagram above; one part keeps the address of the next node, while the other half stores the address of the previous node. The address component of the first node in the doubly linked list is NULL, indicating that the prior node's address is NULL.
Representation of the node in a doubly linked list
Struct node
{
Int data;
Struct node *next;
Struct node *prev;
}
In the above representation, we've constructed a user-defined structure called a node, which has three members: one is data of integer type, and the other two are pointers of the node type, i.e. next and prev. The address of the next node is stored in the next pointer variable, whereas the address of the previous node is stored in the prev pointer variable. The type of both the pointers, i.e., next and prev is struct node as both the pointers are storing the address of the node of the struct node type.
Q19) What is Circular linked list?
A19) A singly linked list is a type of circular linked list. The sole difference between a singly linked list and a circular linked list is that the last node in a singly linked list does not point to any other node, therefore its link portion is NULL. The circular linked list, on the other hand, is a list in which the last node connects to the first node, and the address of the first node is stored in the link section of the last node.
There are no nodes at the beginning or finish of the circular linked list. We can travel in either way, backwards or forwards. The following is a diagrammatic illustration of the circular linked list:
Struct node
{
Int data;
Struct node *next;
}
A circular linked list is a collection of elements in which each node is linked to the next and the last node is linked to the first. The circular linked list will be represented similarly to the singly linked list, as demonstrated below:
Fig 13: Circular linked list
Q20) Write the operation on linked list?
A20) Operation on linked list
● In a linked list, the search operation is used to locate a certain entry.
● On a linked list structure, the most common search is sequential search.
● If the element is located, the search procedure is declared successful.
● The search will fail if the element is not found.
// Search a node
Bool searchNode(struct Node** head_ref, int key) {
Struct Node* current = *head_ref;
While (current != NULL) {
If (current->data == key) return true;
Current = current->next;
}
Return false;
}
Update
● This is a type of linked list operation in C/C++ in which the data section of the needed node is replaced with the given value.
● We'll do this by traversing the linked list until we identify a node that corresponds to the node that needs to be modified.
Void updateNode(Node* head, int value, int newValue)
{
// temp is the traversing node
Node* temp = head;
While(temp != NULL)
{
// If the node matches the given node to be updated.
If( temp->data == val)
{
// Updating the data part of the node with the new value.
Temp->data = newVal;
Return;
}
Temp = temp->next;
}
}
Application
● Queues, stacks, and graphs can all be implemented using Linked Lists.
● The forward and backward navigation buttons in the toolbar employ doubly-linked lists.
