Abstract Data Type (ADT)

Definition
Abstract Data Type (ADT) is a data structure defined by a set of values and operations.

• It specifies *what* operations are performed, but *not how* they are implemented.
• Provides an *implementation-independent* view, making it abstract.

Key Concept

• ADT focuses on *abstraction*, hiding the internal implementation.

• Users interact with data types without knowing how they work internally (e.g., `int`,
`float`).

Features of ADT
1. Abstraction: Users see what an ADT can do, but not how it's implemented.
2. Encapsulation: Internal details are hidden, and a public interface is provided for interaction.

3. Modularity: ADTs can be combined to form complex data structures.

4. Information Hiding: Only authorized operations can modify the data.
5. Data Structure Independence: ADTs can be implemented using different data structures (e.g.,
arrays, linked lists).

Common ADTs
1. List ADT
Description
A list stores elements in a sequence with a structure for count and pointers.

Operations

• `get(pos)` – Retrieve an element at a specific position.

• `insert(pos, element)` – Insert an element at any position.
• `remove(element)` – Remove the first occurrence of an element.
• `removeAt(pos)` – Remove an element at a specific position.
• `replace(pos, element)` – Replace an element at a given position.
• `size()` – Return the number of elements in the list.
• `isEmpty()` – Return true if the list is empty.
• `isFull()` – Return true if the list is full.
• Example
• A list of integers `[1, 2, 3, 4]` where operations like `get(2)` return `3`, and `insert(2, 5)`
makes the list `[1, 2, 5, 3, 4]`.
•

2. Stack ADT

Description
 • Stack follows a Last-In-First-Out (LIFO) principle.
• Only the top element is accessible.
Operations

• `push(element)` – Add an element to the top.

• `pop()` – Remove and return the top element.
• `peek()` – Return the top element without removing it.
• `size()` – Return the number of elements.
• `isEmpty()` – Return true if the stack is empty.
• `isFull()` – Return true if the stack is full.
• Example
• A stack `[2, 4, 6]` where `push(8)` results in `[2, 4, 6, 8]`, and `pop()` returns `8` while
leaving `[2, 4, 6]`.

3. Queue ADT
Description

• Queue follows a First-In-First-Out (FIFO) principle.

Operations

• `enqueue(element)` – Add an element to the end.

• `dequeue()` – Remove and return the first element.
• `peek()` – Return the first element without removing it.
• `size()` – Return the number of elements.
• `isEmpty()` – Return true if the queue is empty.
• `isFull()` – Return true if the queue is full.
• Example
• A queue `[1, 3, 5]` where `enqueue(7)` results in `[1, 3, 5, 7]`, and `dequeue()` removes
`1` to get `[3, 5, 7]`.

Advantages of ADTs

1. Encapsulation: Simplifies management and modification of data structures.

2. Abstraction: Users focus on *what* data structures do, not *how* they work.
3. Data Structure Independence: ADTs can be implemented in multiple ways (e.g., array or
linked list).
4. Information Hiding: Protects the integrity of data by controlling access.
5. Modularity: Enables the combination of multiple ADTs for more complex structures.

Disadvantages of ADTs
1. Overhead: Extra memory and processing can affect performance.
2. Complexity: Large or complex data structures may be difficult to implement.
3. Learning Curve: Requires understanding of ADT concepts and implementations.
4. Limited Flexibility: Some ADTs may not be suitable for certain data types.
5. Cost: Development effort and resources may increase due to complexity
Array: Definition & Need

• Definition: An array is a linear data structure that stores a collection of elements of the
same data type. It allows multiple elements to be stored together in contiguous memory
locations.
• Need: Arrays are useful when there’s a need to store multiple elements and offer efficient
O(1) random access due to direct memory addressing. This makes operations like lookups
extremely fast.

Key Concepts

1. Element: Each item in the array.

2. Index: Numeric position of each element, starting from 0.
3. Memory Address: The starting address in memory, while the index is a reference point to
locate elements.

Array Representation

• An array is visualized as a collection of buckets, where each bucket holds one element.
• Example:
Array: [10, 20, 30, 40]
Indices: 0 1 2 3
• Access is done using the index, such as array[2] to get the third element (30).

Basic Operations in Arrays

1. Traverse: Print all elements one by one.

2. Insertion: Add an element at a specific index.
3. Deletion: Remove an element from a specific index.
4. Search: Find an element using its index or value.
5. Update: Modify an element at a specific index.
6. Display: Print the entire array.

Example Code in Java

1. Array Declaration & Initialization

int [] array = {10, 20, 30, 40}; // Declaring and initializing an array

2. Insertion Operation

• Add an element at a specific index.

 int [] array = new int [5]; // Array of size 5
array [0] = 10; // Inserting at index 0

array [1] = 20; // Inserting at index 1

3. Deletion Operation

• Shift elements left to fill the gap created by deletion.

int[] array = {10, 20, 30, 40};
for (int i = 1; i < array.length - 1; i++) {
array[i] = array[i + 1]; // Shift elements after index 1
}

4. Search Operation

• Search for an element by value.

int[] array = {10, 20, 30, 40};
int searchValue = 30;
for (int i = 0; i < array.length; i++) {
if (array[i] == searchValue) {
System.out.println("Found at index: " + i);
}
}

5. Update Operation

• Update an element at a given index.

java
Copy code
int[] array = {10, 20, 30, 40};
array[2] = 50; // Updating the element at index 2

6. Display Operation

6. Print all elements in the array.

java
Copy code
int[] array = {10, 20, 30, 40};
for (int i = 0; i < array.length; i++) {
System.out.println("Element at index " + i + ": " + array[i]);
}

Advantages of Arrays

• Fast access: O(1) time complexity for accessing elements using an index.
• Contiguous memory: Ensures efficient storage and quick traversal.
Linked List

Definition

A linked list is a linear data structure composed of nodes connected via pointers. Each node has:

1. Data: Stores the actual value.

2. Pointer: Points to the next node in the sequence.

Key Features

• Dynamic Memory: Memory is allocated or deallocated at runtime.

• Non-contiguous Storage: Nodes are scattered across memory, connected by pointers.
• Applications: Used in stacks, queues, graphs, and hash maps.

Structure of a Linked List

• Head Node: Points to the first node of the list.

• Tail Node: The last node, which points to null to signify the end.
• Nodes: Consist of data and a pointer to the next node.

Linked Lists vs Arrays

Arrays Linked Lists

Fixed size at creation Dynamic size
Stored in contiguous Nodes stored in non-contiguous
memory memory
Homogeneous data Can store different data types

Types of Linked Lists

1. Singly Linked List

a. Each node contains data and a pointer to the next node.
b. Traversal occurs in one direction.
2. Doubly Linked List
a. Each node contains data, a pointer to the previous node, and a pointer to the next
node.
b. Allows bidirectional traversal.
3. Circular Linked List
a. The last node points back to the first node, creating a circular structure.
b. Can be singly or doubly linked.

Basic Operations

1. Insertion
 Add a node to the list.
a. At Beginning: Insert a new node at the start.
b. At End: Insert a new node at the end.
c. At a Given Position: Insert a node after a specified node.

2. Deletion
Remove a node from the list.
a. At Beginning: Remove the head node.
b. At End: Remove the last node.
c. At a Given Position: Delete a node by key or position.

3. Traversal
Walk through all nodes sequentially to access their values.

4. Search
Locate a node by its value using a key.

5. Reversal
Reverse the order of nodes in the list.

Detailed Code Examples

Insertion Operations

1. Insertion at Beginning

static void insertAtBegin(int data) {

node newNode = new node(data);
newNode.next = head;
head = newNode;
}

2. Insertion at End

static void insertAtEnd(int data) {

node newNode = new node(data);
if (head == null) {
head = newNode;
return;
}
node temp = head;
while (temp.next != null) temp = temp.next;
temp.next = newNode;
}

3. Insertion at a Given Position

static void insertAfterNode(node prevNode, int data) {
if (prevNode == null) return;
node newNode = new node(data);
newNode.next = prevNode.next;
prevNode.next = newNode;
}

Deletion Operations

1. Deletion at Beginning

static void deleteAtBegin() {

if (head != null) head = head.next;
}

2. Deletion at End

static void deleteAtEnd() {

if (head == null || head.next == null) {
head = null;
return;
}
node temp = head;
while (temp.next.next != null) temp = temp.next;
temp.next = null;
}

3. Deletion at a Given Position

static void deleteByKey(int key) {

node temp = head, prev = null;
if (temp != null && temp.data == key) {
head = temp.next;
return;
}
while (temp != null && temp.data != key) {
prev = temp;
temp = temp.next;
}
if (temp == null) return;
prev.next = temp.next;
}

Reversal Operation

Reverse the Linked List

static node reverseList(node head) {
node prev = null, curr = head, next;
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}

Search Operation

Search for an Element

static boolean search(int key) {

node temp = head;
while (temp != null) {
if (temp.data == key) return true;
temp = temp.next;
}
return false;
}

Advantages

1. Dynamic Size: Adjusts during runtime, unlike arrays.

2. Efficient Insertions/Deletions: No need for shifting elements.
3. Flexibility: Can store data of different types.

Disadvantages

1. Memory Overhead: Requires extra space for pointers.

2. Sequential Access: Slower traversal compared to arrays.
3. Complex Implementation: Difficult to debug and maintain.

Doubly Linked List

Definition

A Doubly Linked List is a variation of a linked list where each node contains pointers to both its
next and previous nodes, enabling traversal in both forward and backward directions.

Key Terms

Link: A node in the list containing data and pointers.

1. Next: Pointer to the next node.
2. Prev: Pointer to the previous node.
3. Head: Points to the first node of the list.
 4. Tail: Points to the last node of the list.

Features

• Supports bidirectional traversal.

• The last node points to null to signify the end of the list.

Representation

In a Doubly Linked List:

• Each node contains data, a pointer to the next node, and a pointer to the previous node.
• The head points to the first node, and the tail points to the last node.

Basic Operations

1. Insertion
a. At Beginning: Adds a node at the start.
b. At End: Adds a node at the end.
c. After a Node: Inserts a node after a specified node.
2. Deletion
a. At Beginning: Removes the first node.
b. At End: Removes the last node.
c. By Key: Deletes a node containing a specific key.
3. Traversal
a. Forward: Traverses from the head to the tail.
b. Backward: Traverses from the tail to the head.

Code Examples

1. Insertion Operations

Insertion at Beginning

static void insertFirst(int key, int data) {

Node newNode = new Node(key, data);
if (isEmpty()) {
tail = newNode;
} else {
head.prev = newNode;
}
newNode.next = head;
head = newNode;
}
Insertion at End
static void insertLast(int key, int data) {
Node newNode = new Node(key, data);
if (isEmpty()) {
head = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
}
tail = newNode;
}

Insertion After a Node

static boolean insertAfter(int key, int newKey, int data) {

Node current = head;
while (current != null && current.key != key) {
current = current.next;
}
if (current == null) return false;
Node newNode = new Node(newKey, data);
newNode.next = current.next;
if (current.next != null) {
current.next.prev = newNode;
} else {
tail = newNode;
}
newNode.prev = current;
current.next = newNode;
return true;
}

2. Deletion Operations

Deletion at Beginning

static Node deleteFirst() {

if (isEmpty()) return null;
Node temp = head;
if (head.next == null) {
tail = null;
} else {
head.next.prev = null;
}
head = head.next;
return temp;
}

Deletion at End

static Node deleteLast() {

if (isEmpty()) return null;
Node temp = tail;
if (tail.prev == null) {
head = null;
} else {
tail.prev.next = null;
}
tail = tail.prev;
return temp;
}

Deletion by Key

static Node delete(int key) {

Node current = head;
while (current != null && current.key != key) {
current = current.next;
}
if (current == null) return null;
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
} else {
tail = current.prev;
}
return current;}

3. Traversal Operations

Forward Traversal

static void displayForward() {

Node temp = head;
while (temp != null) {
System.out.print("(" + temp.key + "," + temp.data + ") ");
temp = temp.next;
}
System.out.println();
}

Backward Traversal

static void displayBackward() {

Node temp = tail;
while (temp != null) {
System.out.print("(" + temp.key + "," + temp.data + ") ");
temp = temp.prev;
}
System.out.println();
}

Advantages

1. Bidirectional Traversal: Allows moving in both directions.

2. Efficient Insertions/Deletions: Can be done at both ends easily.
3. Flexible Memory Usage: Does not require contiguous memory allocation.

Disadvantages

1. Increased Memory Overhead: Requires extra space for prev pointers.

2. Complex Implementation: More complex than singly linked lists.

Circular Linked List

A Circular Linked List is a variation of a linked list in which the last node points back to the
first node, creating a circular structure. It can be implemented as either a Singly Circular
Linked List or a Doubly Circular Linked List.

Singly Circular Linked List

In a Singly Circular Linked List, the next pointer of the last node points to the first node,
creating a circular reference.

Doubly Circular Linked List

In a Doubly Circular Linked List, the next pointer of the last node points to the first node, and
the previous pointer of the first node points back to the last node, forming a circular reference in
both directions.

Basic Operations in Circular Linked List

1. Insert: Adds an element at the start of the list.

 2. Delete: Removes an element from the start of the list.
3. Display: Displays all elements in the list.

Circular Linked List - Insertion Operation

Insertion is done at the start of the circular linked list. The steps for inserting at the start are as
follows:

1. Check if the list is empty.

2. If empty, set the new node as both the head and point its next pointer to itself.
3. If not empty, point the next of the new node to the current head and then set the new node
as the head.

Example: Java Code for Insertion

import java.util.*;
class Node {
int data;
int key;
Node next;
}
public class CircularLinkedList {
static Node head = null;
static boolean isEmpty() {
return head == null;
}
// Insert at the start of the list
static void insertFirst(int key, int data) {
Node newNode = new Node();
newNode.key = key;
newNode.data = data;
if (isEmpty()) {
head = newNode;
head.next = head;
} else {
newNode.next = head;
head = newNode;
}
}
// Display the list
static void printList() {
Node ptr = head;
if (head != null) {
do {
System.out.print("(" + ptr.key + "," + ptr.data + ") ");
ptr = ptr.next;
} while (ptr != head);
 }
System.out.println();
}

public static void main(String[] args) {

insertFirst(1, 10);
insertFirst(2, 20);
insertFirst(3, 30);
System.out.print("Circular Linked List: ");
printList();
}
}

Output:

Circular Linked List:

(3,30) (2,20) (1,10)

Circular Linked List - Deletion Operation

The deletion operation removes a node from the list, which can be done at the beginning, middle,
or end. For deletion:

1. If the list has only one node, set the head to null.
2. If the node to be deleted is at the start, set the head to the next node.
3. If the node is at the end, set the second-to-last node's next pointer to the head.
4. For a middle node, remove the node by linking its previous node to its next node.

Example: Java Code for Deletion

public class CircularLinkedList {

static Node head = null;

// Delete first item

static Node deleteFirst() {
if (head != null) {
Node tempLink = head;
if (head.next == head) {
head = null;
} else {
head = head.next;
}
return tempLink;
}
return null;
}

public static void main(String[] args) {

 insertFirst(1, 10);
insertFirst(2, 20);
insertFirst(3, 30);
System.out.print("Original Circular Linked List: ");
printList();

deleteFirst();
System.out.print("List after deleting the first item: ");
printList();
}
}

Output:

Original Circular Linked List:

(3,30) (2,20) (1,10)
List after deleting the first item:
(2,20) (1,10)

Circular Linked List - Display Operation

To display the list, we traverse the list starting from the head and continue until we return to the
head node, printing each element during the traversal.

Example: Java Code for Display

public class CircularLinkedList {

static Node head = null;

// Display the list

static void printList() {
Node ptr = head;
if (head != null) {
do {
System.out.print("(" + ptr.key + "," + ptr.data + ") ");
ptr = ptr.next;
} while (ptr != head);
}
System.out.println();
}

public static void main(String[] args) {

insertFirst(1, 10);
insertFirst(2, 20);
insertFirst(3, 30);
 System.out.print("Circular Linked List: ");
printList();
}
}

Output:

Circular Linked List:

(3,30) (2,20) (1,10)

Circular Linked List - Complete Implementation

A complete implementation would support insertion, deletion, and display functions along with
other operations such as length calculation.

Example: Java Code for Complete Circular Linked List

public class CircularLinkedList {

private Node head;

boolean isEmpty() {
return head == null;
}

// Insert at the first location

void insertFirst(int key, int data) {
Node newNode = new Node(key, data);
if (isEmpty()) {
head = newNode;
head.next = head;
} else {
newNode.next = head;
head = newNode;
}
}

// Delete first item

Node deleteFirst() {
if (head != null) {
Node tempLink = head;
if (head.next == head) {
head = null;
} else {
head = head.next;
}
 return tempLink;
}
return null;
}

// Display the list

void printList() {
Node ptr = head;
if (head != null) {
do {
System.out.print("(" + ptr.key + "," + ptr.data + ") ");
ptr = ptr.next;
} while (ptr != head);
}
System.out.println();
}

public static void main(String[] args) {

CircularLinkedList linkedList = new CircularLinkedList();
linkedList.insertFirst(1, 10);
linkedList.insertFirst(2, 20);
linkedList.insertFirst(3, 30);
linkedList.printList();

while (!linkedList.isEmpty()) {
Node temp = linkedList.deleteFirst();
System.out.println("Deleted value: (" + temp.key + "," + temp.data
+ ")");
}
linkedList.printList();
}
}

Output:

Circular Linked List:

(3,30) (2,20) (1,10)
Deleted value: (3,30)
Deleted value: (2,20)
Deleted value: (1,10)
Circular Linked List: