Doubly Linked List

 Doubly Linked List

struct Node

{

int element;

struct Node *Next;

struct Node *Prev;

};

typedef struct Node *Position, *List;

//typedef PtrToNode Position;

//typedef PtrToNode List;

Position Find(int x, List L)

{

Position P;

P = L->Next;

while(P!=NULL && P->element!=x)

P = P->Next;

return P;

}

void Delete(int x, List L)

{

Position P, Tmpcell;

P=L->Next;

while(P->element!=x)

P=P->Next;

if(P!=NULL)

{

Tmpcell = P;

P->Prev->Next = Tmpcell->Next;

P->Next->Prev = Tmpcell->Prev;

free(Tmpcell);

}

}

void InsertAtBegining(int x, List L)

{

Position Tmpcell;

Tmpcell = (struct Node *)malloc(sizeof(struct Node));

if(Tmpcell == NULL)

printf("Error. Unable to allocate memory\n");

Tmpcell->element = x;

Tmpcell->Next = L->Next;

Tmpcell->Prev = L;

L->Next = Tmpcell;

}

void InsertAtEnd(int x, List L)

{

Position P, Tmpcell;

P = L;

Tmpcell = (struct Node *)malloc(sizeof(struct Node));

if(Tmpcell == NULL)

printf("Error. Unable to allocate memory\n");

while(P->Next!=NULL)

P = P->Next;

Tmpcell->element = x;

Tmpcell->Next = P->Next;

Tmpcell->Prev = P;

P->Next = Tmpcell;

}

void InsertAtPosition(int x, int index, List L)

{

Position P, Tmpcell;

int i=1;

P=L;

Tmpcell = (struct Node *)malloc(sizeof(struct Node));

if(Tmpcell == NULL)

printf("Error. Unable to allocate memory\n");

while(i<index)

{

P = P->Next;

i++;

}

Tmpcell->element = x;

Tmpcell->Next = P->Next;

Tmpcell->Prev = P;

P->Next = Tmpcell;

}

List Create()

{

List L;

L = (struct Node *)malloc(sizeof(struct Node));

if(L==NULL)

printf("Error. Unable to allocate mempry.\n");

else

{

L->element = -1;

L->Next = NULL;

L->Prev = NULL;

}

return L;

}

Linked List Operations

 

// linked list

List Create()

void Insert(int x, List L)

void Delete(int x, List L)

int IsEmpty(List L)

int IsLast(Position P, List L)

Position Find(int x, List L)

Position FindPrevious(int x, List L)

void Display(List L)

void DeleteList(List L)

 

// linked list

 

#include<stdio.h>

#include<conio.h>

 

struct Node

{

          int element;

          struct Node *Next;

};

 

typedef struct Node *Position, *List;

//typedef PtrToNode Position;

//typedef PtrToNode List;

 

 

int IsEmpty(List L)

{

          return (L->Next == NULL);

}

 

int IsLast(Position P, List L)

{

          return (P->Next == NULL);

}

 

Position Find(int x, List L)

{

          Position P;

          P = L->Next;

 

          while(P!=NULL && P->element!=x)

                   P = P->Next;

 

          return P;

}

 

Position FindPrevious(int x, List L)

{

          Position P;

          P = L;

          while(P->Next!=NULL && P->Next->element!=x)

                   P = P->Next;

 

          return P;

}

 

void Delete(int x, List L)

{

          Position P, Tmpcell;

          P = FindPrevious(x, L);

 

          if(!IsLast(P,L))

          {

                   Tmpcell = P->Next;

                   P->Next = Tmpcell->Next;

                   free(Tmpcell);

          }

}

 

 

void Insert(int x, List L)

{

          Position Tmpcell;

 

          Tmpcell = (struct Node *)malloc(sizeof(struct Node));

 

          if(Tmpcell == NULL)

                   printf("Error. Unable to allocate memory\n");

 

          Tmpcell->element = x;

          Tmpcell->Next = L->Next;

          L->Next = Tmpcell;

}

 

void DeleteList(List L)

{

          Position P, Tmp;

          P = L->Next;

          L->Next = NULL;

 

          while(P!=NULL)

          {

                   Tmp = P->Next;

                   free(P);

                   P = Tmp;

          }

}

 

 

 

List Create()

{

 

          List L;

          L = (struct Node *)malloc(sizeof(struct Node));

 

          if(L==NULL)

                   printf("Error. Unable to allocate mempry.\n");

 

          else

          {

                   L->element = -1;

                   L->Next = NULL;

          }

          return L;

}

 

void Display(List L)

{

          L = L->Next;

          if(L==NULL)

                   printf("Empty List.\n");

          else

          {

                   printf("Elements in List : ");

                   while(L!=NULL)

                   {

                             printf("%d ",L->element);

                             L = L->Next;

                   }

          }

}

Priority Queue Implementation

  

Implementation of Priority Queue

 

struct HeapStruct

{

int Capacity;

int Size;

int *Elements;

};

typedef struct HeapStruct *PriorityQueue;

 

PriorityQueue Initialize(int MaxElements)

{

PriorityQueue H;

if( MaxElements < MIN_PQ_SIZE )

printf(“Error – Priority queue size is too small");

 

H = malloc ( sizeof (struct HeapStruct) );

if( H == NULL )

printf(“Memory Allocation Error.");

 

H->Elements = malloc( (MaxElements+1) * sizeof(int) );

if( H-> Elements == NULL )

printf(“Memory Allocation Error”);

 

H->Capacity = MaxElements;

H->Size = 0;

H->Elements[0] = MIN_DATA;

 

return H;

}

 

 

void Insert( int x, PriorityQueue H)

{

int i;

if( IsFull( H ) )

{

printf(“Error – Priority queue is full");

return;

}

for(i = ++H->size; H->Elements[i/2] > x; i /= 2 )

H->Elements[i] = H->Elements[i/2];

H->Elements[i] = x;

}

 

 

int DeleteMin( PriorityQueue H)

{

int i, Child;

int MinElement, LastElement;

 

if( IsEmpty( H ) )

{

printf(“Error – Priority queue is empty");

return H->Elements[0];

}

 

MinElement = H->Elements[1];

LastElement = H->Elements[H->size--];

 

for( i=1; i*2 <= H->size; i=Child )

{

/* find smaller child */

Child = i*2;

if( ( Child != H->size ) &&

( H->Elements[Child+1] < H->Elements[Child] ) )

Child++;

 

/* percolate one level */

if( LastElement > H->Elements[Child] )

H->Elements[i] = H->Elements[Child];

else

break;

}

H->Elements[i] = LastElement;

return MinElement;

}

 

Basic Heap Operations

 Basic Heap Operations

 

Insert an element into the heap

1.   Create a hole in the next available location (i.e. in the next available position of the array representation)

§  This step maintains the complete binary tree property, ensuring the tree remains balanced (each level filled from left to right).

2.   Bubble Up (Heapify Up):

§  Check if the new element violates the heap property. In a min-heap, the element should be smaller than or equal to its parent.

§  If the element is smaller than its parent, swap it with the parent.

§  Continue to swap with parents until either:

o  The element is larger than its parent, or

o  The element reaches the root of the heap (where it has no parent).

 

Example – to insert 1 into the heap

 

        2

       / \

      4   5

     / \

    7   6

 

     2

    / \

   4   5

  / \   \

 7   6   1

 

     2

    / \

   4   1

  / \   \

 7   6   5

 

     1

    / \

   4   2

  / \   \

 7   6   5

 

 

 

 

 

DeleteMin

Deleting the Root Element in a Min-Heap

1. Remove the Root Element – (Root element is the smallest element in a min-heap)

• To maintain the complete binary tree structure, replace the root with the last element in the heap (the rightmost element in the last level).
• The heap's size is now reduced by one.

2. Heapify Down (Bubble Down):
• Check if the new element violates the heap property. In a min-heap, the element at root should be smaller than or equal to its child.
• If the element is larger than its child, swap it with the smaller child.
• Continue to swap with children until either:
• The element is smaller than its children, or
• The element reaches the leaf of the heap (where it has no children).
• This restores the min-heap property, ensuring every parent node is smaller than its children.

 

Example – to delete minimum element in the heap

 

        2

       / \

      4   5

     / \   \

    7   6   8

 

     8

    / \

   4   5

  / \

 7   6

 

     4

    / \

   8   5

  / \

 7   6

 

     4

    / \

   6   5

  / \

 7   8

Priority Queue

 

Priority Queue

 

 

A priority queue is a data structure similar to a regular queue, but with an additional feature: each element is associated with a priority level. In a standard queue, elements are added at the end and removed from the front in a first-in, first-out (FIFO) order. However, in a priority queue, elements are dequeued not strictly in the order they were enqueued but based on their priority.

 

Implementations of a Priority Queue

Priority queues can be implemented using various data structures:

1. Binary Heap (Min-Heap or Max-Heap): The most common implementation uses a heap, especially a binary heap. In a min-heap, the element with the smallest priority (or highest priority, depending on the application) is at the top, and in a max-heap, the element with the largest priority is at the top.
2. Binary Search Tree (BST): Priority queues can also be implemented using a balanced binary search tree (e.g., Red-Black Tree or AVL Tree), allowing for efficient insertions, deletions, and lookups based on priority.
3. Unordered List or Linked List: Elements can be stored in an unordered list where insertion is O(1), but finding the highest-priority element would take O(n).
4. Ordered List or Linked List: The list is kept sorted by priority. Finding the highest-priority element is O(1), but insertion takes O(n) to find the correct position in the sorted order.

 

Operations in a Priority Queue

§  Insert (Enqueue): Adds an element with a priority to the queue.

• Remove (Dequeue): Removes and returns the element with the highest priority.
• Peek: Returns the element with the highest priority without removing it.

 

Binary Heap

Heap has two properties

1.   Structure property

2.   Heap order property

 

Structure property

A heap is a binary tree that is completely filled, with possible exception of the bottom level which is filled from left to right. Such a tree is known as a complete binary tree.

Complete binary tree of height h has between 2^h and (2^h+1 – 1) nodes. Time complexity for any operation is O(log N). Since complete binary tree is regular it can be represented in an array.

For any element in array position i, the left child is in position 2i and right child is in the cell after the left child at position (2i+1). The parent is in position i/2

 

Heap order property

1.   A min-heap requires that each parent node is less than or equal to its children. This ensures that the minimum element is always at the root.

2.   A max-heap requires that each parent node is greater than or equal to its children, making the maximum element reside at the root.

 

Time Complexity

• Insert – (O(log n)) – Inserting an element involves placing it at the end of the array and then "bubbling up" or "heapifying up" the element by swapping it with its parent until the heap property is restored.
• Remove – (O(log n)) – Removing the highest-priority element (root) involves replacing it with the last element in the array, then "bubbling down" or "heapifying down" by repeatedly swapping with the smaller (or larger) child until the heap property is maintained.
• Peek – (O(1)) – Accessing the root (highest-priority element) without removing it is a constant-time operation.

 

 

 

Queue List Implementation

 Linked List implementation of Queue

typedef struct Node *PtrToNode;

typedef PtrToNode Queue, Front, Rear;

 

int IsEmpty(Queue Q);

Queue CreateQueue();

void DisposeQueue(Queue Q);

void MakeEmpty(Queue Q);

void Enqueue(int X, Queue Q);

void Dequeue(Queue Q);

 

struct Node

{

         int Element;

         struct Node * Next;

};

 

// Check for empty Queue

int IsEmpty(Queue Q)

{

         return (Q == NULL);

}

 

// Create empty queue

Queue CreateQueue()

{

         return NULL;

}

 

 

// Insert element at Rear

void Enqueue(int X, Queue Q)

{

         PtrToNode Tmpcell;

         Tmpcell = malloc(sizeof(struct Node));

         Tmpcell->Element = X;

Tmpcell->Next = NULL;

         if(Q == NULL)

         {

                 Front = Rear = Tmpcell;

return;

}

Rear->Next = Tmpcell;

Rear = Tmpcell;

}

 

// Delete element from Front

void Dequeue(Queue Q)

{

         PtrToNode Tmpcell;

         if(IsEmpty(Q))    

                 printf(“Error – Empty queue. Cant delete.”);

         else

{

                 Tmpcell = Front;

                 Front = Front->Next;

                 free(Tmpcell);

}      

}

Queue Array Implementation

The Queue ADT

 

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. The first element added to the queue is the first one to be removed. Insertions are limited to one end (Rear end) and deletions occur at the other end (Front end).

Key Operations on a Queue:

1. Enqueue: Adds an element to the rear of the queue.
2. Dequeue: Removes an element from the front of the queue.

Queue model

 

Array implementation of Queue

struct QueueRecord;

typedef struct QueueRecord *Queue;

 

int IsEmpty(Queue Q);

int IsFull(Queue Q);

Queue CreateQueue(int maxElements);

void DisposeQueue(Queue Q);

void MakeEmpty(Queue Q);

void Enqueue(int X, Queue Q);

void Dequeue(Queue Q);

 

# define maxElements 100

struct QueueRecord

{

         int Capacity;

         int Front;

         int Rear;

int size;

int * Array;

}

 

Note – Circular array implementation – when Front or Rear gets to the end of the array it is wrapped to the start of the array.

 

// Check for empty queue

int IsEmpty(Queue Q)

{

         return (Q->Size == 0);

}

 

// Check for full queue

int IsFull(Queue Q)

{

         return (Q->Size == Q->Capacity);

}

 

// Delete all elements in queue

void MakeEmpty(Queue Q)

{

         Q->Size = 0;

Q->Front = 1;

Q->Rear = 0;

}

 

// Create Queue

Queue CreateQueue(int maxElements)

{

         Queue Q;

         Q = malloc(sizeof(struct QueueRecord));

         Q->Array = malloc(sizeof(int) * maxElements);

         Q->Size = 0;

Q->Front = 1;

Q->Rear = 0;

         Q->Capacity = maxElements;

}

 

static int succ(int value, Queue Q)

{

if(++value == Q->Capacity)

         value = 0;

return value;

}

 

// Insert element at Rear

void Enqueue(int X, Queue Q)

{

         if(IsFull(Q))       

                 printf(“Error – Full queue. Cant insert.”);

         else

{

                 Q->Size++;

                 Q->Rear = succ(Q->Rear, Q);

                 Q->Array[Q->Rear] = X;

         }

}

 

// Delete element from Front

void Dequeue(Queue Q)

{

         if(IsEmpty(Q))    

                 printf(“Error – Empty queue. Cant delete.”);

         else

{

                 Q->Size––;

                 Q->Front++;

}      

}