Advance-Data-Structure

Advance data structure from MCA

🧩 Overview

This project demonstrates the implementation of advanced data structure concepts and searching/sorting algorithms in a step-by-step manner.
It includes practical applications such as expression conversion and evaluation, stack and linked list operations, and infix convertions.

---

📂 Contents

1️⃣ Searching Algorithms

A. Linear Search

• Simple search algorithm that traverses the list sequentially to find a target value.
• Time Complexity: O(n)

B. Binary Search

• Efficient searching technique for sorted lists using a divide-and-conquer approach.
• Time Complexity: O(log n)

---

2️⃣ Sorting Algorithms

A. Bubble Sort

• Repeatedly swaps adjacent elements if they are in the wrong order.
• Time Complexity: O(n²)

B. Selection Sort

• Repeatedly selects the smallest element and places it in the correct position.
• Time Complexity: O(n²)

C. Insertion Sort

• Builds the sorted array one element at a time by inserting elements into their correct position.
• Time Complexity: O(n²)

---

3️⃣ Expression Conversion and Evaluation

A. Infix to Postfix Conversion

• Converts an infix expression (e.g., A + B * C) to postfix (e.g., A B C * +) using a stack.

B. Postfix Evaluation

• Evaluates postfix expressions using a stack-based approach.

C. Infix to Prefix Conversion

• Converts an infix expression (e.g., A + B * C) to prefix (e.g., + A * B C) using a stack.

D. Prefix Evaluation

• Evaluates prefix expressions using a stack.

---

4️⃣ Stack Implementation

A. Stack using Linked List

• Implements stack operations (Push, Pop, Peek, Display) using a singly linked list.
• Demonstrates dynamic memory allocation and pointer manipulation.

---

5️⃣ Parentheses Balancer

• Checks whether parentheses in an expression are balanced or missing.
• Uses stack operations to ensure every opening bracket has a corresponding closing one.

Example:

✅ Balanced → (A+B)*(C+D)
❌ Unbalanced → (A+B*(C+D)

---

6️⃣ Linked List Implementations

A. Singly Linked List

• Operations: Insert, Delete, Display, Traverse
• Features: Sequential traversal in one direction.

B. Doubly Linked List (Two-Way Linked List)

• Operations: Insert, Delete, Display, Traverse
• Features: Each node has pointers to both previous and next nodes.

C. Header Linked List

1. Grounded Header Linked List – The last node points to NULL.
2. Two-Way (Doubly) Header Linked List – Both head and tail pointers maintained using a special header node.

D. Doubly Ended Linked List

• Maintains front and rear pointers for efficient insertion/deletion at both ends.

---

🧠 Concepts Covered

• Searching & Sorting
• Stack operations
• Expression Conversion (Infix ↔ Postfix ↔ Prefix)
• Linked List Variations
• Parentheses Balancing

---

📑 File Structure

📁 Advanced-Data-Structures
│
├── Searching/
│   ├── linear_search.java
│   └── binary_search.java
│
├── Sorting/
│   ├── bubble_sort.java
│   ├── selection_sort.java
│   └── insertion_sort.java
│
├── Stack/
│   ├── infix_to_postfix.java
│   ├── postfix_evaluation.java
│   ├── infix_to_prefix.java
│   ├── prefix_evaluation.java
│   ├── stack_linkedlist.java
│   └── parenthese_balancer.java
│
├── Linked_Lists/
│   ├── singly_linked_list.java
│   ├── doubly_linked_list.java
│   ├── header_linked_list.java
│   └── doubly_ended_linked_list.java
│
└── README.md

---

👨‍💻 Author

Name: Sayed Mohd. Kaif
Course: Advanced Data Structures
Institution: GNIMS / Mumbai University

Instructor: Sandhya Kapil Thakkar

---