There shall be 10 exercises based on C/C++

1. Implementation of stack

stack

2. Implementations of linear and circular queues

linear

circular

3. Solutions of TOH and Fibonacci sequence by Recursion
TOH 

Fibonacci

4. Implementations of linked list: singly and doubly linked list

Linked list

5. Implementation of trees: AVL trees, and balancing
6. Implementation of Merge sort
7. Implementation of search: sequential, Binary and Tree search
8. Implementation of Graphs: Graph Traversals
9. Implementation of hashing
10. Implementation of Heap

Linked List

Circular Linked List is a variation of Linked list in which the first element points to the last element and the last element points to the first element. Both Singly Linked List and Doubly Linked List can be made into a circular linked list.

Singly Linked List as Circular

In singly linked list, the next pointer of the last node points to the first node.

Doubly Linked List as Circular

In doubly linked list, the next pointer of the last node points to the first node and the previous pointer of the first node points to the last node making the circular in both directions.

As per the above illustration, following are the important points to be considered.

• The last link's next points to the first link of the list in both cases of singly as well as doubly linked list.
• The first link's previous points to the last of the list in case of doubly linked list.

Basic Operations

Following are the important operations supported by a circular list.

• insert − Inserts an element at the start of the list.
• delete − Deletes an element from the start of the list.
• display − Displays the list.

Insertion Operation

Following code demonstrates the insertion operation in a circular linked list based on single linked list.

Example

insertFirst(data):
Begin
   create a new node
   node -> data := data
   if the list is empty, then
      head := node
      next of node = head
   else
      temp := head
      while next of temp is not head, do
      temp := next of temp
      done
      next of node := head
      next of temp := node
      head := node
   end if
End

Deletion Operation

Following code demonstrates the deletion operation in a circular linked list based on single linked list.

deleteFirst():
Begin
   if head is null, then
      it is Underflow and return
   else if next of head = head, then
      head := null
      deallocate head
   else
      ptr := head
      while next of ptr is not head, do
         ptr := next of ptr
      next of ptr = next of head
      deallocate head
      head := next of ptr
   end if
End

Display List Operation

Following code demonstrates the display list operation in a circular linked list.

display():
Begin
   if head is null, then
      Nothing to print and return
   else
      ptr := head
      while next of ptr is not head, do
         display data of ptr
         ptr := next of ptr
      display data of ptr
   end if
End

To know about its implementation in C programming language, please click here.

stack implementation in C

We shall see the stack implementation in C programming language here. You can try the program by clicking on the Try-it button. To learn the theory aspect of stacks, click on visit previous page.

Implementation in C

Live Demo

#include <stdio.h>

int MAXSIZE = 8;       
int stack[8];     
int top = -1;            

int isempty() {

   if(top == -1)
      return 1;
   else
      return 0;
}
   
int isfull() {

   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

int peek() {
   return stack[top];
}

int pop() {
   int data;
 
   if(!isempty()) {
      data = stack[top];
      top = top - 1;   
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

int push(int data) {

   if(!isfull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

int main() {
   // push items on to the stack 
   push(3);
   push(5);
   push(9);
   push(1);
   push(12);
   push(15);

   printf("Element at top of the stack: %d\n" ,peek());
   printf("Elements: \n");

   // print stack data 
   while(!isempty()) {
      int data = pop();
      printf("%d\n",data);
   }

   printf("Stack full: %s\n" , isfull()?"true":"false");
   printf("Stack empty: %s\n" , isempty()?"true":"false");
   
   return 0;
}

If we compile and run the above program, it will produce the following result −

Output

Element at top of the stack: 15
Elements:
15
12
1 
9 
5 
3 
Stack full: false
Stack empty: true

Linear Data Structures

https://www.geeksforgeeks.org/overview-of-data-structures-set-1-linear-data-structures/

A data structure is a particular way of organizing data in a computer so that it can be used effectively. The idea is to reduce the space and time complexities of different tasks. Below is an overview of some popular linear data structures.

1. Array
2. Linked List
3. Stack
4. Queue

Array
Array is a data structure used to store homogeneous elements at contiguous locations. Size of an array must be provided before storing data.

Let size of array be n.
Accessing Time: O(1) [This is possible because elements
                      are stored at contiguous locations]   
Search Time:   O(n) for Sequential Search: 
               O(log n) for Binary Search [If Array is sorted]
Insertion Time: O(n) [The worst case occurs when insertion 
                     happens at the Beginning of an array and 
                     requires shifting all of the elements]
Deletion Time: O(n) [The worst case occurs when deletion 
                     happens at the Beginning of an array and 
                     requires shifting all of the elements]

Example : For example, let us say, we want to store marks of all students in a class, we can use an array to store them. This helps in reducing the use of number of variables as we don’t need to create a separate variable for marks of every subject. All marks can be accessed by simply traversing the array.

Linked List
A linked list is a linear data structure (like arrays) where each element is a separate object. Each element (that is node) of a list is comprising of two items – the data and a reference to the next node.

Types of Linked List :
1. Singly Linked List : In this type of linked list, every node stores address or reference of next node in list and the last node has next address or reference as NULL. For example 1->2->3->4->NULL

2. Doubly Linked List : In this type of Linked list, there are two references associated with each node, One of the reference points to the next node and one to the previous node. Advantage of this data structure is that we can traverse in both the directions and for deletion we don’t need to have explicit access to previous node. Eg. NULL<-1<->2<->3->NULL

3. Circular Linked List : Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list. Advantage of this data structure is that any node can be made as starting node. This is useful in implementation of circular queue in linked list. Eg. 1->2->3->1 [The next pointer of last node is pointing to the first]

Accessing time of an element : O(n)
Search time of an element : O(n)
Insertion of an Element : O(1) [If we are at the position 
                                where we have to insert 
                                an element] 
Deletion of an Element : O(1) [If we know address of node
                               previous the node to be 
                               deleted] 

Example : Consider the previous example where we made an array of marks of student. Now if a new subject is added in the course, its marks also to be added in the array of marks. But the size of the array was fixed and it is already full so it can not add any new element. If we make an array of a size lot more than the number of subjects it is possible that most of the array will remain empty. We reduce the space wastage Linked List is formed which adds a node only when a new element is introduced. Insertions and deletions also become easier with linked list.
One big drawback of linked list is, random access is not allowed. With arrays, we can access i’th element in O(1) time. In linked list, it takes Θ(i) time.

Stack
A stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the last element that was added. In stack both the operations of push and pop takes place at the same end that is top of the stack. It can be implemented by using both array and linked list.

Insertion : O(1)
Deletion :  O(1)
Access Time : O(n) [Worst Case]
Insertion and Deletion are allowed on one end. 

Example : Stacks are used for maintaining function calls (the last called function must finish execution first), we can always remove recursion with the help of stacks. Stacks are also used in cases where we have to reverse a word, check for balanced parenthesis and in editors where the word you typed the last is the first to be removed when you use undo operation. Similarly, to implement back functionality in web browsers.

Queue
A queue or FIFO (first in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: enqueue, the process of adding an element to the collection.(The element is added from the rear side) and dequeue, the process of removing the first element that was added. (The element is removed from the front side). It can be implemented by using both array and linked list.

Insertion : O(1)
Deletion  : O(1)
Access Time : O(n) [Worst Case]

Example : Queue as the name says is the data structure built according to the queues of bus stop or train where the person who is standing in the front of the queue(standing for the longest time) is the first one to get the ticket. So any situation where resources are shared among multiple users and served on first come first server basis. Examples include CPU scheduling, Disk Scheduling. Another application of queue is when data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.

Circular Queue The advantage of this data structure is that it reduces wastage of space in case of array implementation, As the insertion of the (n+1)’th element is done at the 0’th index if it is empty.

Circular Queue

Circular Queue | Set 2 (Circular Linked List Implementation)

Prerequisite – Circular Singly Linked List

We have discussed basics and how to implement circular queue using array in set 1.
Circular Queue | Set 1 (Introduction and Array Implementation)

In this post another method of circular queue implementation is discussed, using Circular Singly Linked List.

Operations on Circular Queue:

• Front:Get the front item from queue.
• Rear: Get the last item from queue.
• enQueue(value) This function is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at Rear position.
  Steps:
  1. Create a new node dynamically and insert value into it.
  2. Check if front==NULL, if it is true then front = rear = (newly created node)
  3. If it is false then rear=(newly created node) and rear node always contains the address of the front node.
• deQueue() This function is used to delete an element from the circular queue. In a queue, the element is always deleted from front position.
  Steps:
  1. Check whether queue is empty or not means front == NULL.
  2. If it is empty then display Queue is empty. If queue is not empty then step 3
  3. Check if (front==rear) if it is true then set front = rear = NULL else move the front forward in queue, update address of front in rear node and return the element.


Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Below is the implementation of above approach:
• C++
• Java
• Python3
• C#













//C++ program for insertion and // deletion in Circular Queue #include <bits/stdc++.h> using namespace std;    // Structure of a Node struct Node {     int data;     struct Node* link; };    struct Queue {     struct Node *front, *rear; };    // Function to create Circular queue void enQueue(Queue *q, int value) {     struct Node *temp = new Node;     temp->data = value;     if (q->front == NULL)         q->front = temp;     else         q->rear->link = temp;        q->rear = temp;     q->rear->link = q->front; }    // Function to delete element from Circular Queue int deQueue(Queue *q) {     if (q->front == NULL)     {         printf ("Queue is empty");         return INT_MIN;     }        // If this is the last node to be deleted     int value; // Value to be dequeued     if (q->front == q->rear)     {         value = q->front->data;         free(q->front);         q->front = NULL;         q->rear = NULL;     }     else  // There are more than one nodes     {         struct Node *temp = q->front;         value = temp->data;         q->front = q->front->link;         q->rear->link= q->front;         free(temp);     }        return value ; }    // Function displaying the elements of Circular Queue void displayQueue(struct Queue *q) {     struct Node *temp = q->front;     printf("\nElements in Circular Queue are: ");     while (temp->link != q->front)     {         printf("%d ", temp->data);         temp = temp->link;     }     printf("%d", temp->data); }    /* Driver of the program */ int main() {     // Create a queue and initialize front and rear     Queue *q = new Queue;     q->front = q->rear = NULL;        // Inserting elements in Circular Queue     enQueue(q, 14);     enQueue(q, 22);     enQueue(q, 6);        // Display elements present in Circular Queue     displayQueue(q);        // Deleting elements from Circular Queue     printf("\nDeleted value = %d", deQueue(q));     printf("\nDeleted value = %d", deQueue(q));        // Remaining elements in Circular Queue     displayQueue(q);        enQueue(q, 9);     enQueue(q, 20);     displayQueue(q);        return 0; }


Output:

Elements in Circular Queue are: 14 22 6
Deleted value = 14
Deleted value = 22
Elements in Circular Queue are: 6
Elements in Circular Queue are: 6 9 20