[go: up one dir, main page]
Scribd
Upload
10 views4 pages

Data_Structures_All_Units_Java_Notes_jntuk

The document provides an overview of data structures, covering Abstract Data Types (ADTs) such as lists, stacks, and queues, along with their implementations in Java. It discusses searching and sorting algorithms, including linear and binary search, as well as various sorting techniques and hashing methods. Additionally, it explores binary trees, AVL trees, B-trees, red-black trees, splay trees, and priority queues, with Java code examples for practical understanding.

Uploaded by

memesmachamemes143
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views4 pages

Data_Structures_All_Units_Java_Notes_jntuk

The document provides an overview of data structures, covering Abstract Data Types (ADTs) such as lists, stacks, and queues, along with their implementations in Java. It discusses searching and sorting algorithms, including linear and binary search, as well as various sorting techniques and hashing methods. Additionally, it explores binary trees, AVL trees, B-trees, red-black trees, splay trees, and priority queues, with Java code examples for practical understanding.

Uploaded by

memesmachamemes143
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

DATA STRUCTURES - Notes for All Units

UNIT-I: Introduction to Data Structures

Abstract Data Types (ADTs) define data models and the allowed operations without specifying the

implementation.

- List ADT: Can be implemented using arrays or linked lists.

- Stack ADT: Follows LIFO principle.

- Queue ADT: Follows FIFO principle.

- Implementations in Java are dynamic using classes and objects.

Java Example (Stack using array):

class Stack {
int top = -1;
int[] stack = new int[100];

void push(int x) {
if (top < 99) stack[++top] = x;
}

int pop() {
if (top >= 0) return stack[top--];
return -1;
}

int peek() {
return top >= 0 ? stack[top] : -1;
}
}

UNIT-II: Searching, Sorting, and Hashing

Searching:

- Linear Search: Simple iteration.

- Binary Search: Efficient for sorted arrays.


DATA STRUCTURES - Notes for All Units

Sorting:

- Includes Bubble, Insertion, Selection, Merge, Quick, Heap Sort.

Hashing:

- Hash Functions map keys to indices.

- Collision resolution with separate chaining using LinkedLists.

Java Example (Binary Search):

int binarySearch(int[] arr, int x) {


int l = 0, r = arr.length - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] < x) l = mid + 1;
else r = mid - 1;
}
return -1;
}

UNIT-III: Binary Trees

Binary Trees:

- Each node has a maximum of two children.

- Binary Search Trees allow fast searching, insertion, and deletion.

Expression Trees represent mathematical expressions.

Java uses classes and recursion to implement trees.

Java Example (Insert in BST):

class Node {
DATA STRUCTURES - Notes for All Units

int data;
Node left, right;

Node(int value) {
data = value;
left = right = null;
}
}

Node insert(Node root, int key) {


if (root == null) return new Node(key);
if (key < root.data) root.left = insert(root.left, key);
else root.right = insert(root.right, key);
return root;
}

UNIT-IV: AVL and B-Trees

AVL Trees:

- Self-balancing binary search tree.

- Maintains balance using rotations.

B-Trees:

- Multi-way search trees.

- Useful in databases and filesystems.

- Java uses classes with dynamic node children.

Concept: If balance > 1 or < -1, use rotations (LL, RR, LR, RL)

Java (conceptual class structure shown):

class AVLNode {
int key, height;
AVLNode left, right;

AVLNode(int d) {
DATA STRUCTURES - Notes for All Units

key = d;
height = 1;
}
}

UNIT-V: Red-Black, Splay Trees, Priority Queues

Red-Black Trees:

- Balanced BST with coloring rules.

- Guarantees logarithmic time for operations.

Splay Trees:

- Recently accessed elements moved to root.

Priority Queue:

- Elements ordered by priority.

- Java uses PriorityQueue class (min-heap by default).

Java Example (PriorityQueue):

import java.util.*;

class Example {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(20);
pq.add(5);

while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
}

You might also like