Data Structures(ADTs)

Arrays , Linked Lists ,Queues

 Static data structure
• In Static data structure the size of the
structure is fixed. The content of the data
structure can be modified but without
changing the memory space allocated to it.
• Eg Array
 Static Data Structure
Advantages of Static Data Structures
• Easy to check for overflow
• Memory allocation is fixed and therefore there is no problem with adding
and removing data items.
• Easy to program as there is no need to check for data structure size at any
given time/point
• An array allows random access and is faster to access elements than in other
data structures
Disadvantages of Static Data Structures
• Programmer has to estimate maximum amount of space needed, which may
be difficult
• Can waste a lot of space if some space is left with no data entered into it.
• Adding, removing and modifying elements is not directly possible. If done, it
requires a lot of resources like memory.
 Dynamic Data Structure
• In Dynamic data structure the size of the
structure in not fixed and can be modified
during the operations performed on it.
Dynamic data structures are designed to
facilitate change of data structures in the run
time
• Eg Tree , Linked List
 Dynamic Data Structure
Advantages of Dynamic Data Structures
• Only uses the space that is needed at any time
• Makes efficient use of the memory, no spaces lie idle at any given
point
• Storage no-longer required can be returned to the system for
other uses.
• Does not allow overflow
Disadvantages of Dynamic Data Structures
• Complex and more difficult to program as software needs to keep
track of its size and data item locations at all times
• Can be slow to implement searches
• A linked list only allows serial access
 Abstract Data Type
• Is 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 datatypes,
we can perform different operations. But how those operations
are working that is totally hidden from the user.
• The ADT is made of primitive datatypes, but operation logics
are hidden.
• Stacks and queues are examples of ADTs. They can be
implemented using either arrays or linked lists.
• An ADT simplifies program design by allowing you focus on
the essentials of a data storage structure, without worrying (at
least initially) about its implementation.
 Arrays
• Array is a container which can hold a fix number of
items and these items should be of the same type.
• Most of the data structures make use of arrays to
implement their algorithms.
• Following are the important terms to understand the
concept of Array.
• Element − Each item stored in an array is called an
element.
• Index − Each location of an element in an array has a
numerical index, which is used to identify the element
 Arrays

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

considered.
Index starts with 0.
Array length is 10 which means it can store 10 elements.
Each element can be accessed via its index. For example, we can fetch an
elementat index 0 as 35
 Array Operations
• Traverse − Prints all the array elements one by
one.
• Insertion − Adds an element at the given index.
• Deletion − Deletes an element at the given index.
• Search − Searches an element using the given
index or by the value.
• Update − Updates an element at the given index.
 Insertion
• Insert operation is to insert one or more data
elements into an array.
• Based on the requirement, a new element can
be added at the beginning, end, or any given
index of array
 Insertion
• At the beginning of the array
• When the insertion happens at the beginning, it
causes all the existing data items to shift one step
downward
• Lets assume A is an array with N elements. The
maximum numbers of elements it can store is
defined by MAX.
• We shall first check if an array has any empty space
to store any element and then we proceed with the
insertion process
 Insertion
• begin
IF N = MAX, return
ELSE
N=N+1
For All Elements in A
Move to next adjacent location
A[FIRST] = New_Element
end
 Insertion
#include <stdio.h>
#define MAX 5
void main() {
int array[MAX] = {2, 3, 4, 5};
int N = 4; // number of elements in array
int i = 0; // loop variable
int value = 1; // new data element to be stored in array
// print array before insertion
printf("Printing array before insertion −\n");
for(i = 0; i < N; i++) {
• printf("array[%d] = %d \n", i, array[i]);
• }
• // now shift rest of the elements downwards
• for(i = N; i >= 0; i--) {
• array[i+1] = array[i];
• }
• // add new element at first position
• array[0] = value;
• // increase N to reflect number of elements
• N++;
• // print to confirm
• printf("Printing array after insertion −\n");
• for(i = 0; i < N; i++) {
• printf("array[%d] = %d\n", i, array[i]);
• }
• }
 Insertion at the Given Index
• In this scenario, we are given the exact
location (index) of an array where a new
dataelement (value) needs to be inserted.
• First we shall check if the array is full, if it is
not, then we shall move all data elements
from that location one step downward. This
will makeroom for a new data element.
 Insertion at the Given Index
• Lets assume A is an array with N elements. The maximum
numbers of elements it can store is defined by MAX.
begin
IF N = MAX, return
ELSE
N=N+1
SEEK Location index
For All Elements from A[index] to A[N]
Move to next adjacent location
A[index] = New_Element
end
 Insertion at the Given Index
#include <stdio.h>
#define MAX 5
void main() {
int array[MAX] = {1, 2, 4, 5};
int N = 4; // number of elements in array
int i = 0; // loop variable
int index = 2; // index location to insert new value
int value = 3; // new data element to be inserted
// print array before insertion
printf("Printing array before insertion −\n");
 Insertion at the Given Index
for(i = 0; i < N; i++) {
printf("array[%d] = %d \n", i, array[i]);
}
// now shift rest of the elements downwards
for(i = N; i >= index; i--) {
array[i+1] = array[i];
}
// add new element at first position
array[index] = value;
// increase N to reflect number of elements
N++;
// print to confirm
printf("Printing array after insertion −\n");
for(i = 0; i < N; i++) {
printf("array[%d] = %d\n", i, array[i]);
}
}
 Deletion Operation
• Deletion refers to removing an existing element from the
array and re-organizing all elements of an array.
• Following is the algorithm to delete an element available at
the Kth position of LA.
• 1. Start
• 2. Set J=K
• 3. Repeat steps 4 and 5 while J < N
• 4. Set LA[J-1] = LA[J]
• 5. Set J = J+1
• 6. Set N = N-1
• 7. Stop
 Search Operation
.
• You can perform a search for an array element based on its value or its
index
• Consider LA is a linear array with N elements and K is a positive integer
such that K<=N.
• Following is the algorithm to find an element with a value of ITEM using
sequential search.
• Start
• 2. Set J=0
• 3. Repeat steps 4 and 5 while J < N
• 4. IF LA[J] is equal ITEM THEN GOTO STEP 6
• 5. Set J = J +1
• 6. PRINT J, ITEM
• 7. Stop
 Search Using C
#include <stdio.h>
main() {
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
while( j < n){
if( LA[j] == item ){
break;
}
j = j + 1;
}
printf("Found element %d at position %d\n", item, j+1);
}
 Update Operation
• Update operation refers to updating an existing
element from the array at a given index.
• Algorithm
• Consider LA is a linear array with N elements and K is a
positive integer such that K<=N.
• Following is the algorithm to update an element
available at the Kth position of LA.
1. Start
2. Set LA[K-1] = ITEM
3. Stop
 Update Using C
#include <stdio.h>
main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5, item = 10;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
LA[k-1] = item;
printf("The array elements after updation :\n");
Linked List
 What is a Linked List
• A linked list, in its simplest form, is a collection of nodes that together
form a linear ordering.
• each node stores a pointer, called next, to the next node of the list. In
addition, each node stores its associated element
• The next pointer inside a node is a link or pointer to the next node of
the list.
• Moving from one node to another by following a next reference is
known as link hopping or pointer hopping.
• The first and last nodes of a linked list are called the head and tail of
the list, respectively.
• Thus, we can link-hop through the list,starting at the head and ending
at the tail.
• We can identify the tail as the node havinga null next reference
Linked List Representation
 Linked List Representation
• Linked List contains a link element called first.
• Each link carries a data field(s) and a link field
called next.
• Each link is linked with its next link using its
next link.
• Last link carries a link as null to mark the end
of the list.
 Why Linked List
• They are not very adaptable.
• For instance, we have to fix the size n of an array in
advance, which makes resizing an array difficult.
Unlike an array, a singly linked list does not have a
predetermined fixed size. It can be resized by
adding or removing nodes.
• (This drawback is remedied in STL vectors.)
Insertions and deletions are difficult, because
elements need to be shifted around to make space
for insertion or to fill empty positions after deletion.
 Types of Linked Lists
• Simple Linked List − Item navigation is forward
only.
• Doubly Linked List − Items can be navigated
forward and backward.
• Circular Linked List − Last item contains link of
the first element as next and the first element
has a link to the last element as previous
 Linked List Operations
• Insertion − Adds an element at the beginning of
the list.
• Deletion − Deletes an element at the beginning
of the list.
• Display − Displays the complete list.
• Search − Searches an element using the given
key.
• Delete − Deletes an element using the given
key.
 Insertion Operation
• Adding a new node in linked list is a more than
one step activity.
• First, create a node using the same structure
and find the location where it has to be
inserted
 Deletion Operation
• First, locate the target node to be removed, by
using searching algorithms.
• The left (previous) node of the target node
now should point to the next node of the
target node −
 Updating
• Updating a data item at a specified node
• Search the target node starting at the head
until the specified target none is reached
 Application Of Linked List
• Used to implement Stacks and Queues
• Used to implement Graphs
• Used to implement Hash Tables
 Linked List using C
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node
{
int data;
int key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
//display the list
void printList()
{
struct node *ptr = head;
printf("\n[ ");
//start from the beginning
while(ptr != NULL)
{
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
//insert link at the first location
void insertFirst(int key, int data)
{
//create a link
 Linked List using C
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
//point it to old first node
link->next = head;
//point first to new first node
head = link;
}
//delete first item
struct node* deleteFirst()
{
//save reference to first link
struct node *tempLink = head;
//mark next to first link as first
head = head->next;
//return the deleted link
return tempLink;
}
//is list empty
bool isEmpty()
{
return head == NULL;
}
int length()
{
int length = 0;
struct node *current;
 Linked List using C
for(current = head; current != NULL; current = current->next)
{
length++;
}
return length;
}
//find a link with given key
struct node* find(int key){
//start from the first link
struct node* current = head;
//if list is empty
if(head == NULL)
{
return NULL;
}
//navigate through list
while(current->key != key){
//if it is last node
if(current->next == NULL){
return NULL;
}else {
//go to next link
current = current->next;
}
}
//if data found, return the current Link
return current;
}
Queue

ADT
 Queue
• Formally, the queue abstract data type defines a container
that keeps elements in sequence, where element access
and deletion are restricted to the first elementin the
sequence, which is called the front of the queue,
• element insertion is restricted to the end of the sequence,
which is called the rear of the queue. This restriction
enforces the rule that items are inserted and deleted in a
queue according to the first-in first-out (FIFO) principle
• Unlike stacks, a queue is open at both its ends. One end is
always used to insert data (enqueue) and the other is
used to remove data (dequeue)
 Queue
• A queue can also be implemented using
Arrays, Linked-lists, Pointers and Structures.
 Queue Operations
• enqueue() − add (store) an item to the queue.
• dequeue() − remove (access) an item from the queue.
• peek() − Gets the element at the front of the queue
without removing it.
• isfull() − Checks if the queue is full.
• isempty() − Checks if the queue is empty
• In queue, we always dequeue (or access) data, pointed
by front pointer and while enqueing (or storing) data in
the queue we take help of rear pointer
 peek()
This function helps to see the data at the front of the queue.

The algorithm of peek() function is as follows −

begin procedure peek

return queue[front]
end procedure

Implementation of peek() function in C programming language −

int peek() {
return queue[front];
}
 isFull
• using single dimension array to implement queue,
check for the rear pointer to reach at MAXSIZE to
determine that the queue is full
begin procedure isfull
if rear equals to MAXSIZE
return true
Else
return false
endif
end procedure
 isFull in C
• bool isfull() {
if(rear == MAXSIZE - 1)
return true;
else
return false;
}
 isEmpty
begin procedure isempty
if front is less than MIN OR front is greater than
rear
return true
else
return false
endif
end procedure
 isEmpty
bool isempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}
 Enqueue
• Queues maintain two data pointers, front and rear. Therefore, its
operations are comparatively difficult to implement than that of
stacks.
• The following steps should be taken to enqueue (insert) data into
a queue −
• Step 1 − Check if the queue is full.
• Step 2 − If the queue is full, produce overflow error and exit.
• Step 3 − If the queue is not full, increment rear pointer to point
the next empty space.
• Step 4 − Add data element to the queue location, where the rear
is pointing.
• Step 5 − Return success
 Enqueue in C
int enqueue(int data)
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
return 1;
end procedure
 Dequeue
• Accessing data from the queue is a process of two tasks − access
the data where front is pointing and remove the data after
access.
• The following steps are taken to perform dequeue operation −
• Step 1 − Check if the queue is empty.
• Step 2 − If the queue is empty, produce underflow error and
exit.
• Step 3 − If the queue is not empty, access the data where front
is pointing.
• Step 4 − Increment front pointer to point to the next available
data element.
• Step 5 − Return success
 Dequeue in C
int dequeue() {
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}
 Application of Queues
Task Scheduling
• Operating Systems: Queues are used in
process scheduling, where processes waiting
for CPU time are managed in a queue. The
process at the front of the queue is executed
first.
• Job Scheduling: In environments like print
servers, tasks are queued up, and the first job
in the queue is printed first.
 Application of Queues
• Network Routers: Queues are used to manage packets
waiting to be transmitted across a network. Packets
arriving at a router are placed in a queue before being
sent to their destination.
• Web Servers: Queues are used in web servers to manage
incoming requests. When the server is busy, incoming
requests are queued until they can be processed.
• Distributed Systems: In load balancing scenarios, queues
are used to manage tasks or requests distributed across
multiple servers, ensuring that each server processes
requests in a balanced manner.