1.

Introduction to Data Structures

A Data Structure is a way of organizing and storing data so that operations like searching,
insertion, deletion, and updating can be performed efficiently.

Types of Data Structures

1. Primitive

o int, char, float, double, etc.

2. Non-Primitive

o Linear: Arrays, Linked Lists, Stacks, Queues

o Non-Linear: Trees, Graphs

2. Linked Lists

A Linked List is a dynamic data structure where elements are stored in nodes, and each
node contains:

 Data

 Pointer to next node

Unlike arrays:

 Memory is allocated dynamically

 Size can grow or shrink

 Insertion/deletion is easier

2.1 Singly Linked List

Structure of Node

struct node {

int data;

struct node *next;

};

Operations

1. Insertion

o At beginning
 o At end

o After a given node

2. Deletion

o From beginning

o From end

o Particular node

3. Traversal

o Visit all nodes from head to end

Advantages

 Dynamic size

 Easy insertion/deletion

Disadvantages

 No backward traversal

 Extra memory for pointer

2.2 Doubly Linked List

Each node contains:

 Data

 Pointer to next node

 Pointer to previous node

Structure

struct dnode {

int data;

struct dnode *prev;

struct dnode *next;

};

Advantages

 Traversal possible in both directions

Disadvantages

 More memory

 Complex implementation

2.3 Circular Linked List

A Circular Linked List is one in which:

 Last node points back to the first node.

Types

1. Singly Circular Linked List

2. Doubly Circular Linked List

Uses

 Round-robin scheduling

 Repeated processes

2.4 Basic Algorithms (General)

A. Traversal (Singly LL)

ptr = head

while(ptr != NULL)

visit(ptr->data)

ptr = ptr->next

B. Insert at Beginning

new->next = head

head = new

C. Delete at End

ptr = head

while(ptr->next != last)

ptr = ptr->next
ptr->next = NULL

3. Stacks

A Stack is a linear data structure based on LIFO (Last In First Out).

Examples:

 Function calls

 Undo operations

 Expression evaluation

3.1 Stack Implementation Using Linked List

Node Structure

struct node {

int data;

struct node *next;

};

struct node *top = NULL;

Operations

A. push(x)

1. Create new node

2. Set new->next = top

3. top = new

B. pop()

1. If top == NULL → underflow

2. temp = top

3. top = top->next

4. free(temp)

C. peek()

 Return top->data
Advantages of LL Implementation

 No overflow (until memory full)

 Dynamic size

4. Queues

A Queue follows FIFO (First In First Out).

Examples:

 Printer queue

 Customer service systems

 Scheduling processes

4.1 Queue Implementation Using Linked List

Node Structure

struct node {

int data;

struct node *next;

};

struct node *front = NULL;

struct node *rear = NULL;

Operations

A. enqueue(x)

1. Create new node

2. If queue empty

o front = rear = new

3. Else

o rear->next = new

o rear = new
B. dequeue()

1. If front == NULL → underflow

2. temp = front

3. front = front->next

4. If front == NULL → rear = NULL

5. free(temp)

C. peek()

 Return front->data