Course Outline

Overview of Data Structure

UNIT I -

 LINEAR DATA STRUCTURES -

Abstract Data Types (ADTs)- Time and space complexities – List ADT – Array-
Based Implementation – Linked List Implementation – Doubly-Linked Lists –
Circular Linked Lists – Stack ADT: Implementation of Stacks – Queue ADT:
Applications of ADT
What is Data Structure?
 Data Structures are used to store and manage data in an
efficient and organized way for faster and easier access and
modification of Data.
 Some of the basic data structures are Arrays, LinkedList,
Stacks, Queues, etc.
 Applications of Data Structure
• Storing data. Data structures are used for efficient data persistence, such as specifying the
collection of attributes and corresponding structures used to store records in a database
management system.
• Managing resources and services. Core operating system (OS) resources and services are
enabled through the use of data structures such as linked lists for memory allocation, file
directory management and file structure trees, as well as process scheduling queues
• Data exchange. Data structures define the organization of information shared between
applications, such as TCP/IP packets
• Ordering and sorting. Data structures such as binary search trees -- also known as an
ordered or sorted binary tree -- provide efficient methods of sorting objects, such as character
strings used as tags. With data structures such as priority queues, programmers can manage
items organized according to a specific priority.
• Indexing. Even more sophisticated data structures such as B-trees are used to index
objects, such as those stored in a database
• Searching. Indexes created using binary search trees, B-trees or hash tables speed the
ability to find a specific sought-after item.
• Scalability. Big data applications use data structures for allocating and managing data
storage across distributed storage locations, ensuring scalability and performance. Certain
big data programming environments -- such as Apache Spark -- provide data structures that
mirror the underlying structure of database records to simplify querying.
 Data Structure

Basic Data Structure

Basic Data Structures

Linear Data Structures Non-Linear Data Structures

Arrays Linked Lists Stacks Queues Trees Graphs Hash Tables

 Data Structure

Types of Data Structure

Linear: In Linear data structure, values are
arrange in linear fashion.
Array: Fixed-size
Linked-list: Variable-size
Stack: Add to top and remove from top
Queue: Add to back and remove from front
 Data Structure

array

Linked list

queue
tree stack
 Data Structure

Types of Data Structure

Non-Linear: The data values in this structure are
not arranged in order.

 Hash tables: Unordered lists which use a ‘hash function’

to insert and search

 Tree: Data is organized in branches.

 Graph: A more general branching structure, with less

strict connection conditions than for a tree
 Data Structure

Type of Data Structures

Homogenous: In this type of data structures,
values of the same types of data are stored.
Array

Non-Homogenous: In this type of data structures,

data values of different types are grouped and
stored.
Structures
Classes
 Data Structure

Some real-world examples include:

• Linked lists are best if a program is managing a collection of items that don't need to be
ordered, constant time is required for adding or removing an item from the collection and
increased search time is OK.

• Stacks are best if the program is managing a collection that needs to support a LIFO order.

• Queues should be used if the program is managing a collection that needs to support a FIFO
order.

• Binary trees are good for managing a collection of items with a parent-child relationship, such
as a family tree.

• Binary search trees are appropriate for managing a sorted collection where the goal is to
optimize the time it takes to find specific items in the collection.

• Graphs work best if the application will analyze connectivity and relationships among a
collection of individuals in a social media network.
 Data Structure

Selection of Data Structure

The choice of particular data model
depends on 3 consideration:

1. Supported operations. What functions and operations does the program need?

2. Computational complexity. What level of computational performance is tolerable?

For speed, a data structure whose operations execute in time linear to the number
of items managed -- using Big O Notation: O(n) -- will be faster than a data structure
whose operations execute in time proportional to the square of the number of items
managed -- O(n^2).

3. Programming elegance. Are the organization of the data structure and its
functional interface easy to use?
 ADT
Abstract Data Type and Data Structure
 Abstract Data Types (ADTs) stores data and allow various
operations on the data to access and change it.
 A mathematical model, together with various operations defined
on the model
 An ADT is a collection of data and associated operations for
manipulating that data

 Data Structures
• Physical implementation of an
ADT.

 Data structures used in

implementations are provided in
a language (primitive or built-in)
or are built from the language
constructs (user-defined).

 Each operation associated with

the ADT is implemented by one
or more subroutines in the
implementation
 ADT
Abstract Data type (ADT)
ADT is a type (or class) for objects whose behavior is defined
by a set of values and a set of operations.

The definition of ADT only mentions what operations are to be

performed but not how these operations will be implemented.

It does not specify how data will be organized in memory and
what algorithms will be used for implementing the operations.

It is called “abstract” because it gives an implementation-

independent view.

The process of providing only the essentials and hiding the

details is known as abstraction.
 ADT
Features of ADT:
Abstract data types (ADTs) are a way of encapsulating data and operations on that
data into a single unit. Some of the key features of ADTs include:

 Abstraction: The user does not need to know the implementation of the data
structure only essentials are provided.
 Better Conceptualization: ADT gives us a better conceptualization of the real
world.
 Robust: The program is robust and has the ability to catch errors.
 Encapsulation: ADTs hide the internal details of the data and provide a public
interface for users to interact with the data. This allows for easier maintenance
and modification of the data structure.
 Data Abstraction: ADTs provide a level of abstraction from the implementation
details of the data. Users only need to know the operations that can be performed
on the data, not how those operations are implemented.
 Data Structure Independence: ADTs can be implemented using different data
structures, such as arrays or linked lists, without affecting the functionality of the
ADT.
 Information Hiding: ADTs can protect the integrity of the data by allowing
access only to authorized users and operations. This helps prevent errors and
misuse of the data.
 Modularity: ADTs can be combined with other ADTs to form larger, more
complex data structures. This allows for greater flexibility and modularity in
programming.
 ADT
Abstract Data Type
ADTs support abstraction (hides the details), encapsulation,
and information hiding.

Abstraction is the structuring of a problem into well-defined

entities by defining their data and operations.

The principle of hiding the used data structure and to only

provide a well-defined interface is known as encapsulation.

Three ADTs -
List ADT
Stack ADT
Queue ADT
 ADT
List ADT .1
 Lists are linear data structures that hold data in a non-continuous structure.
The list is made up of data storage containers known as "nodes." These nodes
are linked to one another, which means that each node contains the address of
another block. All of the nodes are thus connected to one another via these
links.

The List ADT Functions is given below:

 get() – Return an element from the list at any given position.
 insert() – Insert an element at any position of the list.
 remove() – Remove the first occurrence of any element from a non-empty list.
 removeAt() – Remove the element at a specified location from a non-empty list.
 replace() – Replace an element at any position by another element.
 size() – Return the number of elements in the list.
 isEmpty() – Return true if the list is empty, otherwise return false.
 isFull() – Return true if the list is full, otherwise return false.
 ADT
2. Stacks
 A stack is a linear data structure that only allows data to be accessed from the
top. It simply has two operations: push (to insert data to the top of the stack) and
pop (to remove data from the stack). (used to remove data from the stack top)
 The program allocates memory for the data and address is passed to the stack
ADT.
 The head node and the data nodes are encapsulated in the ADT. The calling
function can only see the pointer to the stack.
 The stack head structure also contains a pointer to top and count of number of
entries currently in stack.
 push() – Insert an element at one end of the stack called to.
 pop() – Remove and return the element at the top of the stack, if it is not empty.
 peek() – Return the element at the top of the stack without removing it, if the
stack is not empty.
 size() – Return the number of elements in the stack.
 isEmpty() – Return true if the stack is empty, otherwise return false.
 isFull() – Return true if the stack is full, otherwise return false.
 ADT
3. Queues
 A queue is a linear data structure that allows data to be accessed from
both ends. There are two main operations in the queue: push (this
operation inserts data to the back of the queue) and pop (this operation
is used to remove data from the front of the queue).

 The program’s responsibility is to allocate memory for storing the data.

 enqueue() – Insert an element at the end of the queue.
 dequeue() – Remove and return the first element of the queue, if the
queue is not empty.
 peek() – Return the element of the queue without removing it, if the
queue is not empty.
 size() – Return the number of elements in the queue.
 isEmpty() – Return true if the queue is empty, otherwise return false.
 isFull() – Return true if the queue is full, otherwise return false.
Applications of ADT – ADT

[Link] ADT - servicing in the order of arrival ( FIFO)

- Customer servicing for any type application for example waiting for
Printer service
- Operating Systems where processes need memory to be allocated in
the order of arrival
- Round Robin scheduler where jobs are scheduled again in the order
of arrival in a round robin manner

2. Stack ADT – LIFO

- Web browser : keeping track of Page-visited history
- Undoing the sequence of operations in a text editor
- used for systematic Memory Management.

3. List ADT –
- Image viewer / Web browser / Music player – Next and Previous are
linked, so can be accessed by the “next” and “previous” buttons.
- Mailing lists: Linked lists have their benefit in email applications as
well. Since it is challenging to anticipate numerous lists, maybe a mailer
U BMS Institute of Technology and Mgmt
creates a linked list of email addresses before sending a message.
 TC & SC

Fundamental steps in solving problems

Statement of the problem

Development of mathematical model
Design of the algorithm
Correctness of the algorithm
Analysis of algorithm for its time and
space complexity
Implementation
Program testing and debugging
Documentation
U BMS Institute of Technology and Mgmt
TC & SC
 TC & SC
Time and Space complexities -
What is Time Complexity?
- Time complexity measures how many operations an algorithm completes
in relation to the size of the input.
- Big O notation (O()) is the notation that is most frequently used to
indicate temporal complexity. It offers an upper bound on how quickly an
algorithm's execution time will increase.

Best, Worst, and Average Case Complexity:

In analyzing algorithms, we consider three types of time complexity:

Best-case complexity (O(best)): This represents the minimum time

required for an algorithm to complete when given the optimal input. It
denotes an algorithm operating at its peak efficiency under ideal
circumstances.
Worst-case complexity (O(worst)): This denotes the maximum time an
algorithm will take to finish for any given input. It represents the scenario
where the algorithm encounters the most unfavorable input.
Average-case complexity (O(average)): This estimates the typical
running time of an algorithm when averaged over all possible inputs. It
provides a more realistic evaluation of an algorithm's performance.
 TC & SC
Time and Space complexities -
What is Time Complexity?
- Total time taken by algorithm to complete its execution

Divided into 2 –

[Link] time complexity

[Link] time complexity

Constant time complexity – If a program requires fixed amount of time

for all inputs

Eg - Int sum (int a, int b)

{ return a+b; }

Linear time complexity – If input values are increased, then the time
complexity changes
TC & SC
 TC & SC
Time

complexities -
Arrays: Linked Lists:
• Access: O(1)
•Access: O(n)
• Search: O(n) •Search: O(n)
• Insertion (at the end): O(1) •Insertion (at the beginning): O(1)
• Insertion (at the beginning or middle): O(n) •Insertion (at the end, with a tail pointer): O(
• Deletion (from the end): O(1) •Insertion (at the end, without a tail poin
O(n)
• Deletion (from the beginning or middle): O(n) •Insertion (in the middle): O(n)
Stacks: Queues: •Deletion (from the beginning): O(1)
•Push: O(1) •Enqueue: O(1) •Deletion (from the end, with a tail pointer):
•Pop: O(1) •Dequeue: O(1) •Deletion (from the end, without a tail poin
•Peek: O(1) •Peek: O(1) O(n)
•Deletion (from the middle): O(n)

Hash Tables: Doubly Linked List:

•Search: O(1) - on average, assuming a good hash
function and minimal collisions •Accessing an element by index: O(n)
•Insertion: O(1) - on average, assuming a good hash •Searching for an element: O(n)
function and minimal collisions •Insertion (at the beginning): O(1)
•Deletion: O(1) - on average, assuming a good hash •Insertion (at the end, with a tail pointer): O
function and minimal collisions •Insertion (at the end, without a tail po
Binary Search Trees (BSTs): O(n)
•Search: O(log n) - on average for balanced BST, •Insertion (in the middle): O(n)
O(n) worst case for unbalanced BST •Deletion (from the beginning): O(1)
•Insertion: O(log n) - on average for balanced BST, •Deletion (from the end, with a tail pointer):
O(n) worst case for unbalanced BST •Deletion (from the end, without a tail po
•Deletion: O(log n) - on average for balanced BST, O(n)
O(n) worst case for unbalanced BST •Deletion (from the middle): O(n)
 TC & SC
Space complexity -
What is Space Complexity?

- Amount of memory space required by algorithm during course of

execution

- Instruction space – Executable program

- data space – to store all constants and variables value
- environment space – (sometimes a function calls itself (recursively) or
another function, storing or pushing the data of the previous function onto
the stack until further execution is required, at which point the inner
function is called. This space is used to store the address of the partially
executed functions (a partially executed function is one that calls another
function without fully executing itself).

[Link] Space complexity – Fixed amount of space

Eg - Int square (int a)
{ return a*a ; }
-Here algorithm requires fixed amount of space to input values. So space
complexity is constant
-[Link]
 TC & SC

2. Linear Space complexity – Memory utilization while evaluation of an algorithm

Array Array
Array
Array Based Implementation - ADT Array ADT
Array ADT
 Array ADT
Operations performed on Array –

1. Create the array – Create the list with ‘n’ number of elements. If ‘n’ exceeds the
arrays max size , then elements cannot be inserted into the list. These array elements
are stored in consecutive order

void create ()
{
int a[10];
int i , n;
Printf (“%d enter the number of elements”, n); // n=5
scanf (“%d”, &n);
printf (“ enter the elements”); // 10,20,30,40,50
for (i=0, i<n,i++) // gets only till 5 elements from user
scanf(“%d”,&a[i]) // reads elements and can be inserted in array
}

n=5 10 20 30 40 50
a[10] 0 1 2 3 4 5 6 7 8 9

([Link]
q=list+adt+array+based+implementation&sca_esv=599157406&tbm=vid&source=lnms&sa=X&ved=2ahUKEwjq99Gr5-
SDAxUH4TgGHRNtAxoQ_AUoAnoECAIQBA&biw=1707&bih=772&dpr=1.13#fpstate=ive&vld=cid:0899a111,vid:mlCaRfDgKQ4,st:0)
 Array ADT
2. Print / display the elements in an array – Display all the elements stored in the list
void display ()
{
int i ;
for (i=0, i<n,i++) // gets till 5 elements from array
Printf(“%d”,a[i]) ; // prints elements in array
}
n=5 10 20 30 40 50
a[10] a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

3. Insertion– Insert operation is used to insert elements at a particular position in the existing
list. This involves the shifting of elements one position towards right

[Link] elements to right by 1 index for

all elements until you get the required
position
2. Write the element in the gap
3. update the size to increment it by 1 as 1
position is moved extra
 Array ADT
void insert ()
{
int i , data, pos,n;
Printf (“\n enter the data to be inserted: \t”); // data =4
scanf (“%d”, &data);
printf (“ \n enter the position at which element to be inserted:\t”); // 3rd pos or a[2] pos
scanf (“%d”, &pos);
if (pos==n) // n is the number of elements which is total 5
printf (“ array overflow”) ;
else
for (i=n-1, i>=pos, i--) //nth is the last position in array.
a[i+1] = a[i]; // shift right by 1 Index means, store 5 th
element in 6th pos, and so on..
}
a[i]=data; // write the data into that gap
n=n+1; // update the size to increment number of elements by 1 as 1 position is moved extra
display();
}
i.e ; for i=5, i>=3
5>=3
a[5+1] = a[5]…. Continue loop till i=3.
Once u get ith (3 ) position, write the data=4 in that gap i.e a[2] = 4 gets inserted with n=6 elements
rd
4. Deletion – Process to remove an element from array at any position Array ADT
- This requires, all elements from the deleted position to be moved to left and
decrement the size of elements

void delete ()
{
int i ,pos,n;
printf (“ \n enter the position at which element to be deleted:\t”);
scanf (“%d”, &pos);
printf (“ \n the data deleted is: \t %d”, a[pos]) ;
for (i=pos, i<n-1, i++) //i++ because, pos will be incremented
{
a[i] = a[i+1]; // shift left by 1 Index i.e move i+1 th data to ‘i’ th position
}
n=n-1; // update the size to decrement number of elements by 1 as 1 position is moved extra
display();
}
step : 1: data 4 in pos 3 to be deleted –
for I = 3; 3<6-1; then a[3]=a[3+1] i.e 4th position will
be assigned to 3rd position.(shift left)

step: 2 i++ = 3++ = 4.

for i=4, 4<6-1; then a[4]=a[4+1]..
step: 3 i++ = 4++ = 5
For i= 5, 5<6-1 = Not valid. No [Link] size of n=5
Array ADT
Array ADT
Time Complexity of these operations in List ADT Arrays - Array ADT
Linked List Implementation - Linked List ADT
Linked List — Abstract Data Type

- Collection of Nodes, the nodes can be accessed in a sequential way.

- Each elements in the list is called Node. Node contains 2 field, Data field
(actual data) and next field ( address of next node)
- Nodes are connected to the next node and/or with the previous one, this
gives the linked effect. When the Nodes are connected with only the next
pointer the list is called Singly Linked List and when it’s connected by the
next and previous the list is called Doubly Linked List.
- The Nodes stored in a Linked List can be anything from primitives types
such as integers to more complex types like instances of classes.
Operations –

[Link] – Inserts a new node in the list.

[Link] – Deletes any node from the list.
[Link] – Finds the position( address ) of any node in
the list.
[Link] - Finds the position( address ) of the
previous node in the list.
[Link]- Finds the position( address ) of the next
node in the list.
[Link]-display the date in the list
[Link]-find whether a element is present in the
list or not
Linked List Implementation - Linked List ADT

Advantages of Linked list:

[Link] and deletion of elements can be done efficiently

[Link] uses dynamic memory allocation
[Link] utilization is efficient compared to arrays.

Disadvantages of linked list:

[Link] list does not support random access
[Link] is required to store next field
[Link] takes time compared to arrays

Types of Linked List

1. Singly Linked List or One Way List
2. Doubly Linked List or Two-Way Linked List
3. Circular Linked List
Single Linked List – Linked List

• A linked list is a linear data

structure, in which the elements are not
stored at contiguous memory locations.
• For every data item in a linked list, there is
an associated pointer that would give the
memory location of the next data item in the
linked list.
• A list can be defined as an ordered collection.

• A node contains two fields i.e. data stored at that particular address and the
pointer which contains the address of the next node in the memory.
• The last node of the list contains pointer to the null.
Linked List Representation
Node =–Data + Pointer to the next node

Dynamic Data Structure –

A linked list can change during execution ( Dynamic Data Structure)

•Successive elements are connected by pointers.

•Last element points to NULL.
•It can grow or shrink in size during execution of a program.
•It can be made just as long as required.
•It does not waste memory space.
Basic operations of Linked List
 Creation - Creates a linked list
 Insertion - Adds an element to the list.
 Deletion - Deletes an element to the list.
 Display - Displays the complete list.
 Search - Searches an element using the given key.

 Concept –
Self Referential Structure – Structure which contains pointer to
a structure of the same type
Algorithm (Inserting a node at the beginning of a linked list)
1. Declare head pointer and make it as NULL.

2. Create a new node with the given data.

 And make the new node => next as NULL.
 (Because the new node is going to be the last node.)

3. If the head node is NULL (Empty Linked List), make the

new node as the head.

4. If the head node is not NULL , (Linked list already has

some elements), find the last node.
 make the last node => next as the new node.
 [Link]
a. Creation of Node
(Using Struct – as different datatypes are used
together)

//Struct node * link (/ next) – Because * link or *next represents pointer

of the node
3 .Make the new node points to the head node –

void addFirst(struct node **head, int val)

{
//create a new node
struct node *newNode = malloc(sizeof(struct node));
newNode->data = val;

newNode->next = *head;

}
4. Make the new node as the head node
 Insertion of a Node at the Beginning of the
List
 There are two steps to insert the data at the beginning:
1. Update the next pointer of the new node to the head node.
2. Update head pointer to the new node.
 Example: Let’s insert a new node with data 10 at the beginning of the
given list.
 Step 1: Updating the next of the new node to head node
b. Inserting node at the end of the list

Algorithm
[Link] head pointer and make it as NULL.
[Link] a new node with the given data. And make the new node =>
next as NULL.
(Because the new node is going to be the last node.)
[Link] the head node is NULL (Empty Linked List), make the new
node as the head.
[Link] the head node is not null, (Linked list already has some elements),
find the last node.
Make the last node => next as the new node.
URL: [Link]
To insert the new node at the end of the list we have to take the
following steps:

[Link] the list to the last node.

[Link] the next pointer of the last node to the new node.
Example: Inserting a new node with data 88 at the end of the list.

Step 1: Traversing the list, and reach at the last node

Step 2: Update the next of the temp to the new node

1. Declare head pointer and make it as NULL.
struct node
{
int data;
struct node *next;
};

struct node *head =

NULL;
 2. Create a new node

void addLast(struct node **head, int val)

{
//create a new node
struct node *newNode = malloc(sizeof(struct node));
newNode->data = val;
newNode->next = NULL;
}

20
3. If the head node is NULL, make the new node as
head
void addLast(struct node **head, int val)
{
//create a new node
struct node *newNode = malloc(sizeof(struct
node)); newNode->data = val;
newNode->next = NULL;
//if head is NULL, it is an empty list
if(*head == NULL)
*head = newNode;
}
4. Find the last node and
set last node => new node
while(node->next != NULL)
{
node = node->next;
}
Sample Linked List
Implementation
Example //declaring nodes
#include<stdio.h> struct node *head,*middle,*last;
#include<stdlib.h> int //allocating memory for each node
main() head = malloc(sizeof(struct
{ node)); middle =
//node structure malloc(sizeof(struct node)); last =
struct node malloc(sizeof(struct node));
{ //assigning values to each node
int regno; head->regno = 10;
char name[20]; head->name=” DSU”; middle-
struct node *next; >regno = 20; head->name
}; =”DSE”; last->regno =
; 30; head->name=”DSI”
Dr. Kousalya ssor, Department of CSE, Dayananda Sagar
G,Profe University, Harohalli, Karnataka. 23
//connecting each nodes. head->middle->last head-
>next = middle;
middle->next = last;
last->next = NULL;
//temp is a reference for head pointer. struct node *temp =
head;
//till the node becomes null, printing each nodes data
while(temp != NULL)
{
printf("\n Regno: %d Name: %s => ",temp->regno,temp->na me
);
temp = temp->next;
}
printf("NULL");
return 0;
}
 Insertion of a New Node at the Given Position

Insertion of the new node at the middle of the list needs the following
steps:

[Link] to the list till given position using temp pointer and move
another pointer prev to its just previous node.
[Link] the next pointer of the previous node to the new node.
[Link] the next pointer of the new node to the temp node.

Example: Inserting a new node with data 34 at position 3 in the given list.
Step 2: Update the next of the prev to the new node

Step 3: Update the next of the new node to temp node

c. Deletion of a Node from the Beginning of the List
To delete the node from the beginning of the list we have to take the following steps:

[Link] the head node to any other temporary pointer.

[Link] head to its next node.
[Link] the memory of the temporary pointer.

Example: Deleting the node from the beginning in the given list.

Step 1: Store the head node to the temp and move head to its next node
// Function to delete the first node in the linked list

struct Node* deleteFromBeginning(struct Node* head)

{
if (head == NULL)
{
printf("List is empty\n");
return NULL;
}

struct Node* temp = head;

head = head->next;
free(temp);
return head;
}
Deletion of a Node from the End of the Node
This operation takes the following steps to delete the node:

[Link] to the end of the node using the temp pointer and use another pointer prev which
pointer previous node of the temp pointer.
[Link] the next pointer field of the prev to NULL.
[Link] the memory of the temp pointer.

Example: Deleting the last node of the given list.

Step 1: Traverse the list at the one node before the last node
// Function to delete the last node in the linked list
struct Node* deleteFromEnd(struct Node* head)
{
if (head == NULL) {
printf("List is empty\n");
return NULL;
}

if (head->next == NULL)
{
free(head);
return NULL;
}
struct Node* current = head;
while (current->next!= NULL)
{
current = current->next;
}
free(current->next);
current->next = NULL;
return head;
}
Deletion of a Node from the Given Position

[Link] the list to the given position node using the temp pointer and
use another previous pointer prev which points to the previous node of
the temp pointer.
[Link] the next pointer of the prev to the next of the temp pointer.
[Link] the memory of the temp pointer.

Example: Deleting the node at position 3 in the given list.

d. Display
// Function to display all the elements in the
linked list
void displayList(struct Node* head) {
struct Node* current = head;
while (current != NULL)
{
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
e. Search - To find a node with the given key, we need to traverse the list
from start to end and match the data with the key. If the data is found in the list
then return 1 otherwise return 0.

// Function to search for an element in the linked list

and return its position
int searchElement(struct Node* head, int key)
{
int position = 1;
struct Node* current = head;
while (current != NULL)
{
if (current->data == key)
{
return position;
}
current = current->next;
position++;
}
return -1; // Element not found
}
f. Update a Node Data

Updation is the process to change the value of a node.

To update the node data we have to follow the given steps:

[Link] the list from start to the given position.

[Link] the value of that node.

g. Traversing the Singly Linked List

Traversing the singly linked list requires the following steps:

[Link] any temporary node type of pointer temp and point

it to the head pointer.
[Link] iterating using temp until it does not reach the NULL
value.
[Link] the data of that node which is pointing by the temp
node.
 Circular Linked List
The circular linked list is a linked list where
all nodes are connected to form a circle.
In a circular linked list, the first node and
the last node are connected to each other
which forms a circle.
There is no NULL at the end.

START

1 2 3 4 5 6 7

Circular list is a list in which the link field of the last node is made to
point to the start/first node of the list.
1.A circular linked list is a linked list in which the head element's previous pointer
points to the tail element and the tail element's next pointer points to the head
element.
2.A circularly linked list node looks exactly the same as a linear singly linked list.

 In a circular linked list, each node has a data element and a

pointer/reference to the next node in the sequence.

 The last node in the list points back to the first node, and the
traversal of the list can continue indefinitely in a loop.
a. Insertion - at the Beginning
[Link] the address of the current first node in the newNode (i.e.
pointing the newNode to the current first node)
2. point the last node to newNode (i.e making newNode as head)
Insert at the beginning
Insertion at beginning in linked list the steps are followed :-

[Link] the linked list.

[Link] we have to take an extra pointer which points to the end

node of the circular linked list.

3. Then we have a pointer that is pointing to the end node,

then end node-> next will point to the first node.

[Link] last follow the algorithm for insertion at beginning in circular

linked list given below
Insertion at the end
[Link] the address of the head node to next of newNode
(making newNode the last node)
[Link] the current last node to newNode make newNode
as the last node
Insertion at end in linked list the steps are followed :-

[Link] a new node.

[Link] the new node next to circular list.
[Link] the list is empty then return new node.
[Link] the new node next to the front of the
list.
[Link] tail next to the new node.
[Link] the end node of the circular linked list.
void insertLast (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;

// if its the first node being entered

if (*head == NULL)
{
*head = newNode;
(*head)->next = *head; // if LL already as >=1 node
return; struct Node *curr = *head;
}
// traverse till last node in LL

while (curr->next != *head)

{
curr = curr->next;
}
// assign LL's current last node's next as this new node

curr->next = newNode;
// assign this new node's next as current head of LL

newNode->next = *head;
}
Insertion in between two nodes

Let's insert newNode after the first node. travel to the node given (let this node
be p)
point the next of newNode to the node next to p store the address of newNode
at next of p
Insertion in between the nodes in linked list the steps are followed :-

[Link] a new node and set the data.

[Link] to pos-1 position in the circular linked list.
3. Now link the next pointer of new node with the node
pointed by the next pointer of current(pos-1) node.
4. After that join the next pointer of current node with the
newly created node which means that the next pointer of
current node will point to new node.
[Link] print the linked list.
void insertPosition (int data, int pos, struct Node **head)
//function to insert element at specific position
{
struct Node *newnode, *curNode;
int i;
if (*head == NULL)
{
printf ("List is empty");
}
if (pos == 1) else
{ {
insertStart (head, data); newnode = (struct Node *) malloc (sizeof (struct Node));
return; newnode->data = data;
} curNode = *head;

while (--pos > 1)

{
curNode = curNode->next;
}
newnode->next = curNode->next;
curNode->next = newnode;
}
}
b. Deletion –
// Delete a node with given value
struct Node* deleteNode(struct Node* head, int value) {
if (head == NULL) {
printf("List is empty.\n");
return NULL;
}

struct Node* current = head;

struct Node* prev = NULL;

do {
if (current->data == value) {
if (prev != NULL) {
prev->next = current->next;
free(current);
return head;
} else {
struct Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = head->next;
free(head);
return temp->next;
}
}
prev = current;
current = current->next;
} while (current != head);

printf("Value not found in the list.\n");

return head;
}
Deleting a Node at a Given Point

[Link] if the position is first, then apply the algorithm for deleting the first
node from a circular linked list (mentioned above).
[Link] two temporary variables and store the head address in one of
them.
[Link] the list till the previous node to the node to be deleted and
assign the position's next node address in a temporary node variable.
[Link] the previous node pointer to point to the current's next node.
[Link] the temporary variable which still points to the position node.
Deleting the First Node –

1. If the list has only one node, then delete the head node by using the free() function
directly.
2. Create two temporary variables and store the head address in them.
3. Traverse the list to the last node and assign the head's next node address to the
last node.
4. Update the head pointer to point to the next node.
5. free the temporary variable which still points to the first node.
Deleting the Last Node

[Link] the list has only one node, then delete the head node by
using the free() function directly.
[Link] two temporary variables and store the head address in
one of them.
[Link] the list till the second last node and assign the last
node address in a temporary node variable.
[Link] the second last node pointer to point to the head node.
[Link] the temporary variable which still points to the last node.
void insertNodeAtEnd(struct node** head, int data){ // traversing the list till the last node
struct node* temp, *current; while(current->next != *head){
// creating the new node
current = current->next;
temp = createNode(); }
temp->data = data;
temp->next = NULL; // assigning head node pointer to the last node to make the list
circular
// if the list is empty
if(*head == NULL){
current->next = (*head)->next;
*head = temp;
temp->next = *head; // assigning the address of the next node in the head node.
return; *head = (*head)->next;
}

// if the list already has more than 1 node

// removing the first node from the memory
current = *head; free(temp);
return;
while(current->next != *head){ }
current = current->next;
}

current->next = temp;
temp->next = *head;
return;
}

// code to delete the first node from the list

void deleteFirstNode(struct node** head){
struct node* temp = *head;
struct node* current = *head;

if(*head == NULL){
printf("List empty.");
return;
}else if((*head)->next == *head){ // if there is only one node in the list
*head = NULL;
free(temp);
return;
}
c. Display

// Display the circular linked list

void display(struct Node* head) {
if (head == NULL) {
printf("List is empty.\n");
return;
}

struct Node* current = head;

printf("Circular Linked List: ");

do {
printf("%d ", current->data);
current = current->next;
}
while (current != head);

printf("\n");
}
Double Linked List –

Check the notes for this Topic and

use only applicable slides for
Operations.
 Doubly Linked List
Linked List

A linked list is a linear data structure in which data is stored in a non- contiguous memory location.
Every node contains data and the address of the other node.

Doubly Linked List

A doubly linked list is a type of linked list in which each node consists of 3 components:

*prev - address of the previous node data - data item

*next - address of next node

//node structure struct Node {

int data;
struct Node* next; struct Node* prev;
};
#include <stdio.h> #include <stdlib.h>

//node structure struct Node {

int data;
struct Node* next; struct Node* prev;
};
int main() {

//create the head node with name MyList struct Node* MyList = NULL;

//Add first node.

struct Node* first;
//allocate second node in the heap
first = (struct Node*)malloc(sizeof(struct Node)); first->data = 10001;
first->next = NULL; first->prev = NULL;
//linking with head node MyList = first;
//Add second node.
struct Node* second;
//allocate second node in the heap
second = (struct Node*)malloc(sizeof(struct Node)); second->data = 20001;
second->next = NULL;
//linking with first node second->prev = first; first->next = second;

//Add third node.

struct Node* third;
//allocate third node in the heap
third = (struct Node*)malloc(sizeof(struct Node)); third->data = 30001;
third->next = NULL;
//linking with second node third->prev = second; second->next = third;

return 0;
}
Traversal
void PrintList(struct Node* head_ref) {

//1. create a temp node pointing to head struct Node* temp = head_ref;
//2. if the temp node is not null continue
// displaying the content and move to the
// next node till the temp becomes null

if(head_ref != NULL) { printf("The list contains: "); while (temp != NULL) { printf("%i ",temp-
>data); temp = temp->next;
}
printf("\n");
} else {

//3. If the temp node is null at the start,

// the list is empty

printf("The list is empty.\n");

}
}
#include <stdio.h> #include <stdlib.h>
//node structure struct Node {
int data;
struct Node* next; struct Node* prev;
};
//Add new element at the end of the list
void push_back(struct Node** head_ref, int newElement) { struct Node *newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = newElement;
newNode->next = NULL; newNode->prev = NULL; if(*head_ref == NULL) {
*head_ref = newNode;
} else {
temp = *head_ref; while(temp->next != NULL) { temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}

//display the content of the list

void PrintList(struct Node* head_ref) { struct Node* temp = head_ref; if(head_ref != NULL) {
printf("The list contains: ");
while (temp != NULL) { printf("%i ",temp->data); temp = temp->next;
}
printf("\n");
} else {
printf("The list is empty.\n");
}
}
int main() {
struct Node* MyList = NULL;

//Add three elements at the end of the list. push_back(&MyList, 110);

push_back(&MyList, 210);
push_back(&MyList, 310);

//traverse to display the content of the list. PrintList(MyList);

return 0;
}
Doubly Linked List - Insert a new node at the beginning
[Link] at the Beginning

Let's add a node with value 6 at the beginning of the doubly linked list we made above.
[Link] a new node
allocate memory for newNode
assign the data to newNode.
2. Set prev and next pointers of new node

point next of newNode to the first node of the doubly linked list point prev to

null
[Link] new node as head node

 Point prev of the first node to newNode (now the previous head is the second node)
 Point head to newNode

// insert node at the front

void insertFront(struct Node** head, int data) {

// allocate memory for newNode

struct Node* newNode = new Node;

// assign data to newNode
newNode->data = data;

// point next of newNode to the first node of the doubly linked list newNode->next =
(*head);
// point prev to NULL newNode->prev = NULL;

// point previous of the first node (now first node is the second
Node – Assigning newcode as head now) to newNode
if ((*head) != NULL)
(*head)->prev = newNode;

// head points to newNode (*head) = newNode;

}
#include <stdio.h> #include <stdlib.h>

//node structure struct Node {

int data;
struct Node* next; struct Node* prev;
};

//Add new element at the start of the list

void push_front(struct Node** head_ref, int newElement) { struct Node *newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = newElement;
newNode->next = NULL; newNode->prev = NULL; if(*head_ref == NULL) {
*head_ref = newNode;
} else {
(*head_ref)->prev = newNode; newNode->next = *head_ref;
*head_ref = newNode;
}
}

//display the content of the list

void PrintList(struct Node* head_ref) { struct Node* temp = head_ref; if(head_ref !=
NULL) {
printf("The doubly linked list contains: "); while (temp != NULL) {
printf("%i ",temp->data);
temp = temp->next;
}
printf("\n");
} else {
printf("The list is empty.\n");
}
}
int main() {
struct Node* MyList = NULL;

//Add three elements at the start of the list. push_front(&MyList,

10);
push_front(&MyList, 20);
push_front(&MyList, 30); PrintList(MyList);

return 0;
}
Output

The doubly linked list contains: 30 20 10

Doubly Linked List - Insert a new node at the end

#include <stdio.h> #include <stdlib.h>

//node structure struct Node {

int data;
struct Node* next;
struct Node* prev;
};

//Add new element at the end of the list

void push_back(struct Node** head_ref, int newElement) { struct Node *newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = newElement;
newNode->next = NULL;
newNode->prev = NULL; if(*head_ref == NULL) {
*head_ref = newNode;
} else {
temp = *head_ref; while(temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode; newNode->prev = temp;
}
}

//display the content of the list

void PrintList(struct Node* head_ref) {
struct Node* temp = head_ref; if(head_ref != NULL) { printf("The list contains: "); while (temp != NULL) {
printf("%i ",temp->data); temp = temp->next;
}
printf("\n");
} else {
printf("The list is empty.\n");
}
}
int main() {
struct Node* MyList = NULL;

//Add three elements at the end of the list. push_back(&MyList, 10);

push_back(&MyList, 20);
push_back(&MyList, 30); PrintList(MyList);

return 0;
}
 Doubly Linked List - Insert a new node at the given position

#include <stdio.h> #include <stdlib.h>

//node structure struct Node {

int data;
struct Node* next; struct Node* prev;
};

//Add new element at the end of the list

void push_back(struct Node** head_ref, int newElement) { struct Node *newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = newElement;
newNode->next = NULL;
newNode->prev = NULL; if(*head_ref == NULL) {
*head_ref = newNode;
} else {
temp = *head_ref; while(temp->next != NULL) { temp = temp->next;
}
temp->next = newNode; newNode->prev = temp;
}
}

//Inserts a new element at the given position

void push_at(struct Node** head_ref, int newElement, int position) { struct Node
*newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = newElement;
newNode->next = NULL;
newNode->prev = NULL; if(position < 1) {
printf("\nposition should be >= 1.");
} else if (position == 1) {
newNode->next = *head_ref; (*head_ref)->prev = newNode;
*head_ref = newNode;
} else {
temp = *head_ref;
for(int i = 1; i < position-1; i++) { if(temp != NULL) {
temp = temp->next;
}
}
if(temp != NULL) {
newNode->next = temp->next; newNode->prev = temp;
temp->next = newNode; if(newNode->next != NULL)
newNode->next->prev = newNode;
} else {
printf("\nThe previous node is null.");
}
}
}
//display the content of the list
void PrintList(struct Node* head_ref) { struct Node* temp = head_ref; if(head_ref != NULL) {
printf("The list contains: "); while (temp != NULL) {
printf("%i ",temp->data); temp = temp->next;
}
printf("\n");
} else {
printf("The list is empty.\n");
}
}
int main() {
struct Node* MyList = NULL;

//Add three elements in the list. push_back(&MyList, 10);

push_back(&MyList, 20);
push_back(&MyList, 30); PrintList(MyList);
//Insert an element at position 2 push_at(&MyList, 100, 2); PrintList(MyList);

//Insert an element at position 1 push_at(&MyList, 200, 1); PrintList(MyList);

return 0;
}
Doubly Linked List - Delete the first node

#include <stdio.h> #include <stdlib.h>

//node structure struct Node {

int data;
struct Node* next; struct Node* prev;
};

//Add new element at the end of the list

void push_back(struct Node** head_ref, int newElement) { struct Node *newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = newElement;
newNode->next = NULL; newNode->prev = NULL;
if(*head_ref == NULL) {
*head_ref = newNode;
} else {
temp = *head_ref;
while(temp->next != NULL) { temp = temp->next;
}
temp->next = newNode; newNode->prev = temp;
}
}

//Delete first node of the list

void pop_front(struct Node** head_ref) { if(*head_ref != NULL) {
struct Node *temp = *head_ref;
*head_ref = (*head_ref)->next; temp = NULL;
if(*head_ref != NULL) (*head_ref)->prev = NULL;
}
}

//display the content of the list

void PrintList(struct Node* head_ref) { struct Node* temp = head_ref; if(head_ref !=
NULL) {
printf("The list contains: "); while (temp != NULL) { printf("%i ",temp->data);
temp = temp->next;
}
printf("\n");
} else {
printf("The list is empty.\n");
}
}
int main() {
struct Node* MyList = NULL;

//Add four elements in the list. push_back(&MyList, 10);

push_back(&MyList, 20);
push_back(&MyList, 30);
push_back(&MyList, 40); PrintList(MyList);

//Delete the first node pop_front(&MyList); PrintList(MyList);

return 0;
}
 Doubly Linked List - Delete the last node
#include <stdio.h> #include <stdlib.h>

//node structure struct Node {

int data;
struct Node* next; struct Node* prev;
};

//Add new element at the end of the list

void push_back(struct Node** head_ref, int newElement) { struct Node
*newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data =
newElement;
newNode->next = NULL; newNode->prev = NULL; if(*head_ref == NULL)
{
*head_ref = newNode;
} else {
temp = *head_ref; while(temp->next != NULL) { temp = temp->next;
}
temp->next = newNode; newNode->prev = temp;
}
}

//Delete last node of the list

void pop_back(struct Node** head_ref) { if(*head_ref != NULL) {
if((*head_ref)->next == NULL) {
} else {
struct Node* temp = *head_ref; while(temp->next->next != NULL)
temp = temp->next;
struct Node* lastNode = temp->next; temp->next = NULL;
free(lastNode);
}
}
}

//display the content of the list

void PrintList(struct Node* head_ref) { struct Node* temp = head_ref; if(head_ref != NULL) {
printf("The list contains: "); while (temp != NULL) { printf("%i ",temp->data); temp = temp->next;
}
printf("\n");
} else {
printf("The list is empty.\n");
}
}
int main() {
struct Node* MyList = NULL;

//Add four elements in the list. push_back(&MyList, 10);

push_back(&MyList, 20);
push_back(&MyList, 30);
push_back(&MyList, 40); PrintList(MyList);
//Delete the last node pop_back(&MyList); PrintList(MyList);

return 0;
}
 Doubly Linked List - Delete a node at the given position

#include <stdio.h> #include <stdlib.h>

//node structure struct Node {

int data;
struct Node* next; struct Node* prev;
};

//Add new element at the end of the list

void push_back(struct Node** head_ref, int newElement) { struct Node *newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = newElement;
newNode->next = NULL; newNode->prev = NULL; if(*head_ref == NULL) {
*head_ref = newNode;
} else {
temp = *head_ref; while(temp->next != NULL) { temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}

//Delete an element at the given position

void pop_at(struct Node** head_ref, int position) { if(position < 1) {
printf("\nposition should be >= 1.");
} else if (position == 1 && *head_ref != NULL) { struct Node* nodeToDelete = *head_ref;
*head_ref = (*head_ref)->next;
free(nodeToDelete); if(*head_ref != NULL) (*head_ref)->prev = NULL;
} else {
struct Node *temp; temp = *head_ref;
for(int i = 1; i < position-1; i++) { if(temp != NULL) {
temp = temp->next;
}
}
if(temp != NULL && temp->next != NULL) { struct Node* nodeToDelete = temp->next; temp->next = temp-
>next->next;
if(temp->next->next != NULL)
temp->next->next->prev = temp->next; free(nodeToDelete);
} else {
printf("\nThe node is already null.");
}
}
}
//display the content of the list
void PrintList(struct Node* head_ref) { struct Node* temp = head_ref;
if(head_ref != NULL) { printf("The list contains: "); while (temp != NULL) { printf("%i
",temp->data); temp = temp->next;
}
printf("\n");
} else {
printf("The list is empty.\n");
}
}

// test the code int main() {

struct Node* MyList = NULL;

//Add three elements at the end of the list. push_back(&MyList, 10);

push_back(&MyList, 20);
push_back(&MyList, 30); PrintList(MyList);

//Delete an element at position 2 pop_at(&MyList, 2); PrintList(MyList);

//Delete an element at position 1 pop_at(&MyList, 1); PrintList(MyList);

return 0; }
Doubly Linked List - Count nodes

int countNodes(struct Node* head_ref) {

//1. create a temp node pointing to head struct Node* temp = head_ref;

//2. create a variable to count nodes int i = 0;

//3. if the temp node is not null increase

// i by 1 and move to the next node, repeat
// the process till the temp becomes null while (temp != NULL) {
i++;
temp = temp->next;
}

//4. return the count return i;

}
#include <stdio.h> #include <stdlib.h>

//node structure struct Node {

int data;
struct Node* next; struct Node* prev;
};

//Add new element at the end of the list

void push_back(struct Node** head_ref, int newElement) { struct Node *newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = newElement;
newNode->next = NULL; newNode->prev = NULL; if(*head_ref == NULL) {
*head_ref = newNode;
} else {
temp = *head_ref; while(temp->next != NULL) { temp = temp->next;
}
temp->next = newNode; newNode->prev = temp;
}
}

//count nodes in the list

int countNodes(struct Node* head_ref) { struct Node* temp = head_ref;
int i = 0;
while (temp != NULL) { i++;
temp = temp->next;
}
return i;
}

//display the content of the list

void PrintList(struct Node* head_ref) {
struct Node* temp = head_ref; if(head_ref != NULL) { printf("The list contains: "); while (temp !=
NULL) {
printf("%i ",temp->data); temp = temp->next;
}
printf("\n");
} else {
printf("The list is empty.\n");
}
}

int main() {
struct Node* MyList = NULL;

//Add four elements in the list.

push_back(&MyList, 10);
push_back(&MyList, 20);
push_back(&MyList, 30);
push_back(&MyList, 40);
//number of nodes in the list
printf("No. of nodes: %i",countNodes(MyList)); return 0;
}
Stacks
 Stack is a linear data structure that follows a particular order in which the operations
are performed.
 The order may be LIFO `(Last In First Out) or FILO (First In Last Out).
 LIFO implies that the element that is inserted last, comes out first and FILO implies
that the element that is inserted first, comes out last.

Regularly used -

•Page-visited history in a Web browser

•Undo sequence in a text editor
•Saving local variables when one function
calls another, and this one calls another

121
Stack
 To implement the stack, it is required to maintain the pointer to the top of
the stack, which is the last element to be inserted because we can access
the elements only on the top of the stack.

122
Basic Operations on Stack
In order to make manipulations in a stack, there are certain
operations provided to us.
push() to insert an element into the stack
pop() to remove an element from the stack
top() Returns the top element of the stack.
isEmpty() returns true if stack is empty else false.
size() returns the size of stack.

123
a. push() –

[Link] a node first and allocate memory to it.

[Link] the list is empty then the item is to be pushed as the start
node of the list. This includes assigning value to the data part
of the node and assign null to the address part of the node.
[Link] there are some nodes in the list already, then we have to
add the new element in the beginning of the list (to not
violate the property of the stack). For this purpose, assign
the address of the starting element to the address field of the
new node and make the new node, the starting node of the
list.

Time Complexity : o(1)

 Stack – ADT – Implementation using
Linked
Node list
Structure:
// Structure to create a node with data and the next pointer

struct Node {
int data;
struct Node *next;
};
Node* top = NULL;

a. push() elements - Elements can only be pushed at the top of the

stack.

Steps to push an element into a Stack:

1. Create a new node using dynamic memory allocation and assign

value to the node.

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

newNode->data = 10;
2. Check if stack is
empty or not, i.e, (top // Push() operation on a stack
== NULL)
If it is empty, then set void push(int data) {
the next pointer of the if (top == NULL)
node to NULL. {
top =(struct node *)malloc(1*sizeof(struct node));
newNode->next = top->ptr = NULL;
NULL; top->info = data;
}
3. If it is not empty, the else
newly created node {
should be linked to the temp =(struct node *)malloc(1*sizeof(struct node));
current top element of temp->ptr = top;
the stack, i.e., temp->info = data;
top = temp;
newNode->next = top; }
count++;
4. Make sure that the printf("Node is Inserted\n\n");
top of the stack should }
always be pointing to
the newly created node.
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");

}
}
Pop() operation - Elements are popped from the
top of the stack. There should be at least one element
in the stack to perform the pop() operation.

Steps to pop an element from a Stack: int pop() {

top1 = top;
1. Check if stack is empty or not, i.e, (TOP == NULL).
If it is empty, then print Stack Underflow. if (top1 == NULL)
{
2. If it is not empty, then create a temporary node and printf("\nStack Underflow\n");
set it to top. Now, create another variable and copy the return -1;
data of top element to this variable. Means - Adjust
}
the head pointer accordingly: In stack, the
elements are popped only from one end, else
therefore, the value stored in the head pointer top1 = top1->ptr;
must be deleted and the node must be freed. int popped = top->info;
The next node of the head node now becomes free(top);
the head node. top = top1;
count--;
Time Complexity : o(n) return popped;
}
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");

(Note – Head means TOP and temp = ptr here in comparison with previous code)
 Display the nodes (Traversing)

void display()
1. Copy the head pointer into {
a temporary pointer. int i;
struct node *ptr;
2. Move the temporary pointer ptr=head;
through all the nodes of the if(ptr == NULL)
list and print the value field {
attached to every node. printf("Stack is empty\n");
}
Time Complexity : o(n) else
{
printf("Printing Stack elements \n");

while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}
}
}
Queue
 A Queue is defined as a linear data structure that is open at both ends and
the operations are performed in First In First Out (FIFO) order.

 We define a queue to be a list in which all additions to the list are made at
one end, and all deletions from the list are made at the other end.

 The element which is first pushed into the order, the operation is first
performed on that.

132
Characteristics of Queue

Queue can handle multiple data.

We can access both ends.

They are fast and flexible.

If front and rear both are NULL, it indicates that the queue is
empty.

Insertion Deletion

133
Applications of Queues
Direct applications
Waiting lines
Access to shared resources (e.g., printer)

Indirect applications
Auxiliary data structure for algorithms
Component of other data structures

134
 Queue Representation
 Like stacks, Queues can also be represented in an array: In this representation,
the Queue is implemented using the array. Variables used in this case are
Queue: the name of the array storing queue elements.
Front: the index where the first element is stored represents the queue.
Rear: the index where the last element is stored represents the queue.

135
Basic Operations on Queue
 Some of the basic operations for Queue in Data Structure are:

enqueue() – Insertion of elements to the queue.

dequeue() – Removal of elements from the queue.
peek() or front()- Acquires the data element available at the front node of the queue
without deleting it.
rear() – This operation returns the element at the rear end without removing it.
isFull() – Validates if the queue is full.
isEmpty() – Checks if the queue is empty.
size(): This operation returns the size of the queue i.e. the total number of elements it
contains.

136
Enqueue
 Inserts an element at the end of the queue i.e. at the rear
end.
 The following steps should be taken to enqueue (insert)
data into a queue:

Check if the queue is full.

If the queue is full, return overflow error and exit.

If the queue is not full, increment the rear pointer to
point to the next empty space.

Add the data element to the queue location, where the
rear is pointing.

return success.

137
Insert operation / Enqueue
The insert operation append the queue by adding an element to the
end of the queue. The new element will be the last element of the
queue.
Firstly, allocate the memory for the new node ptr -
Ptr = (struct node *) malloc (sizeof(struct node));

There can be the two scenario of inserting this new node ptr into the
linked queue.

[Link] the first scenario, we insert element into an empty queue. In

this case, the condition front = NULL becomes true.
Now, the new element will be added as the only element of the queue
and the next pointer ptr
of front
-> dataand rear pointer both, will point to NULL.
= item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
2. In the second case, the queue contains more than one element.
The condition front = NULL becomes false.
In this scenario, we need to update the end pointer rear so that
the next pointer of rear will point to the new node ptr.
Since, this is a linked queue, hence we also need to make the rear
pointer point to the newly added node ptr. We also need to make
the next pointer of rear point to NULL.

rear -> next = ptr;

rear = ptr;
rear->next = NULL;
 /* Enqueing the queue */

void enq(int data)

{
/* Create an empty queue */
if (rear == NULL)
void create()
{
{
rear = (struct node
front = rear = NULL;
*)malloc(1*sizeof(struct node));
}
rear->ptr = NULL;
rear->info = data;
/* Returns queue size */
front = rear;
void queuesize()
}
{
else
printf("\n Queue size : %d", count);
{
}
temp=(struct node
*)malloc(1*sizeof(struct node));
rear->ptr = temp;
temp->info = data;
temp->ptr = NULL;

rear = temp;
}
count++;
}
Dequeue
 This operation removes and returns an element that is
at the front end of the queue.
 The following steps are taken to perform the dequeue
operation:

Check if the queue is empty.

If the queue is empty, return the underflow error and
exit.

If the queue is not empty, access the data where the
front is pointing.

Increment the front pointer to point to the next
available data element.

The Return success.

141
void delete (struct node *ptr)
{
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
Applications of ADT –

. Used in Stack / Queue related Applications