Abstract Data Types
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.
1. List ADT
The List ADT (Abstract Data Type) is a sequential collection of elements that supports a set of
operations without specifying the internal implementation. It provides an ordered way to
store, access, and modify data.
Operations:
The List ADT need to store the required data in the sequence and should have the following
operations:
1.1 The GET operation
get(): Return an element from the list at any given position.
The program below is a C program to get a number in C.
#include <stdio.h>
int main() {
int arr[5] = {10, 20, 30, 40, 50};
int pos = 3; // Invalid position, outside the array
printf("Element at position %d is %d\n", pos, arr[pos]);
return 0;
}
1.2 Insert operation in lists
-insert(): Insert an element at any position in the list.
#include <stdio.h>
int main() {
int arr[6] = {10, 20, 30, 40, 50}; // We leave space for 1 new element
int i;
// Insert value 25 at position 2
for (i = 5; i > 2; i--) {
arr[i] = arr[i - 1];
}
arr[2] = 25;
// Print the new list
printf("The New list after inserting 25 is:\n");
for (i = 0; i < 6; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Lin Code Explanation
e
1 #include <stdio.h> Includes the standard input/output library for functions
like printf().
2 int main() { Entry point of the C program (main function starts here).
3 int arr[6] = {10, 20, 30, 40, 50}; Declares an array arr with 6 spaces and initializes the first
5 elements.
4 int i; Declares a loop variable i for iteration.
5 // Insert value 25 at position 2 A comment explaining the purpose of the next code block.
6 for (i = 5; i > 2; i--) { Starts a loop from index 5 to 3 to shift elements right to
make space at index 2.
7 arr[i] = arr[i - 1]; Shifts the element one place to the right to create space.
8 } Ends the for loop.
9 arr[2] = 25; Inserts the value 25 at index 2 of the array.
10 printf("The New list after inserting Prints a message before displaying the updated list.
25 is:\n");
11 for (i = 0; i < 6; i++) { Starts a loop to print all 6 elements of the array.
12 printf("%d ", arr[i]); Prints each element followed by a space.
13 } Ends the loop for printing.
14 return 0; Returns 0, indicating successful program execution.
15 } Closes the main function.
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 with another element.
1.3 SIZE OF THE LIST
-size (): Return the number of elements in the list.
C Program to show the list
#include <stdio.h>
int main() {
int arr[5] = {10, 20, 30, 40, 50}; // List with 5 elements
int size = 5; // Number of elements in the list
printf("The size of the list is: %d\n", size);
return 0;
}
isEmpty(): Return true if the list is empty; otherwise, return false.
isFull(): Return true if the list is full, otherwise, return false. Only applicable in fixed-size
implementations (e.g., array-based lists).
2. Stack ADT
The Stack ADT is a linear data structure that follows the LIFO (Last In, First Out) principle. It
allows elements to be added and removed only from one end, called the top of the stack.
Operations:
In Stack ADT, the order of insertion and deletion should be according to the FILO or LIFO
Principle. Elements are inserted and removed from the same end, called the top of the stack. It
should also support the following operations:
push(): Insert an element at one end of the stack called the top.
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. Only relevant for fixed-
capacity stacks (e.g., array-based).
3. Queue ADT
The Queue ADT is a linear data structure that follows the FIFO (First In, First Out) principle.
It allows elements to be inserted at one end (rear) and removed from the other end (front).
Operations:
The Queue ADT follows a design similar to the Stack ADT, but the order of insertion and
deletion changes to FIFO. Elements are inserted at one end (called the rear) and removed from
the other end (called the front). It should support the following operations:
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.
Advantages and Disadvantages of ADT
Abstract data types (ADTs) have several advantages and disadvantages that should be
considered when deciding to use them in software development. Here are some of the main
advantages and disadvantages of using ADTs:
Advantage:
The advantages are listed below:
Encapsulation: ADTs provide a way to encapsulate data and operations into a single unit,
making it easier to manage and modify the data structure.
Abstraction: ADTs allow users to work with data structures without having to know the
implementation details, which can simplify programming and reduce errors.
Data Structure Independence: ADTs can be implemented using different data structures,
which can make it easier to adapt to changing needs and requirements.
Information Hiding: ADTs can protect the integrity of data by controlling access and
preventing unauthorized modifications.
Modularity: ADTs can be combined with other ADTs to form more complex data
structures, which can increase flexibility and modularity in programming.
Disadvantages:
The disadvantages are listed below:
Overhead: Implementing ADTs can add overhead in terms of memory and processing,
which can affect performance.
Complexity: ADTs can be complex to implement, especially for large and complex data
structures.
Learning Curve: Using ADTs requires knowledge of their implementation and usage,
which can take time and effort to learn.
Limited Flexibility: Some ADTs may be limited in their functionality or may not be
suitable for all types of data structures.
Cost: Implementing ADTs may require additional resources and investment, which can
increase the cost of development.