DSA Notes

C
DSA
Software Engineering
Software Architecture
Operating System
Big Data
Data Mining and Warehousing
TOC
Ada
CPP
DBMS

All Topics (20)

  • 1. Data Structure
  • 2. Objectives of Data Structure
  • 3. types of data structures
  • 4. Operations on Data Structure
  • 5. Array
  • 6. Types of Arrays
  • 7. Memory Representation of Array
  • 8. Address Calculation in One-Dimensional Array
  • 9. What is a Two-Dimensional Array? (With Simple Explanation & Example)
  • 10. Representation of 2D Array in Memory (Row Major & Column Major Order)
  • 11. Address Calculation in 2D Array (Row Major Order)
  • 12. Basic Operations in Array (Traversal, Insertion, Deletion)
  • 13. Sparse Matrix
  • 14. Why Use Sparse Matrix Instead of Simple Matrix?
  • 15. Advantages & Disadvantages of Array.
  • 16. Linked List
  • 17. Difference Between Array and Linked List.
  • 18. Types of Linked List
  • 19. Operations on Linked List
  • 20. Dynamic Memory Allocation (DMA) vs Array vs Linked List

16. Linked List

A Linked List is a linear data structure in which elements are stored in the form of nodes, and each node is connected to the next node using a pointer (link).

 Unlike arrays, linked list elements are not stored in continuous memory locations.

🔹 Structure of a Node

Each node in a linked list has two parts:

1. Data (Info) Part

  • Stores the actual data/value

2. Link (Pointer) Part

  • Stores the address of the next node

🔹 Node Representation

[ DATA | NEXT ]

🔹 Basic Linked List Structure

START →  [A | • ] → [B | • ] → [C | • ] → [D | NULL]

 Explanation:

  • START (Head) points to first node
  • Each node contains data and address of next node
  • Last node points to NULL

🔹 Start / Head Pointer

  • It is a special pointer called START or HEAD
  • It stores the address of the first node
  • It is the entry point of the linked list

 If START = NULL → Linked List is empty

🔹 Last Node

  • The last node of linked list contains NULL in its link part
  • It shows the end of the list

🔹 Memory Representation Example

START = 100
  Address Data Next
  100   A 200
  200   B 350
  350   C 500
  500   D NULL

 Nodes are stored at different memory locations but connected using pointers.

🔹 Working / Idea of Linked List

  • Data is stored in nodes
  • Each node points to the next node
  • Traversal is done using links
  • Starts from START pointer and ends at NULL

17. Difference Between Array and Linked List.

Basis Array Linked List
1️⃣ Nature Static data structure Dynamic data structure
2️⃣ Size Fixed size (cannot change at runtime) Dynamic size (can grow or shrink at runtime)
3️⃣ Memory Allocation Memory allocated at compile time Memory allocated at runtime
4️⃣ Memory Usage May cause memory wastage No memory wastage (memory used as needed)
5️⃣ Storage Stored in contiguous memory locations Stored in non-contiguous memory locations
6️⃣ Access Time Fast random access using index Slow access (sequential traversal required)
7️⃣ Insertion/Deletion Inefficient (shifting required) Efficient (only pointer changes required)
8️⃣ Searching Faster (direct indexing) Slower (linear traversal)
9️⃣ Structure Simple linear structure Node-based structure (data + pointer)

 Example

Array:

Index: 0 1 2 3
Value: 10 20 30 40

 Stored in continuous memory.

Linked List:

START → [10 | • ] → [20 | • ] → [30 | • ] → [40 | NULL]
 

 Stored in different memory locations and connected using pointers.

18. Types of Linked List

1. Singly Linked List

A Singly Linked List is a type of linked list in which each node contains only one pointer (link) that points to the next node in the sequence.

 Structure of Node

[ DATA | NEXT ]

 Diagram

START → [10 | • ] → [20 | • ] → [30 | • ] → [40 | NULL]

 Working

  • First node is pointed by START (HEAD)
  • Each node points to next node
  • Last node points to NULL

 Disadvantage

  • We cannot move backward
  • Predecessor node cannot be accessed directly

 Key Point

 Simple and easy structure
 Only forward traversal is possible

2. Doubly Linked List

A Doubly Linked List is a type of linked list in which each node has two pointers:

  • One points to the previous node
  • One points to the next node

 Structure of Node

[ PREV | DATA | NEXT ]

 Diagram

NULL ← [10] ⇄ [20] ⇄ [30] ⇄ [40] → NULL

 Working

  • Each node is connected in both directions
  • We can move forward and backward

 Advantage

 Easy backward traversal
 Easy insertion and deletion

 Key Point

 Better than singly linked list for navigation

3. Circular Linked List

A Circular Linked List is a linked list in which the last node points back to the first node, forming a circle.

 Diagram

START → [10 | • ] → [20 | • ] → [30 | • ]
↑__________________________↓
 

 Working

  • No NULL at the end
  • Last node connects back to START
  • Forms a circular structure

 Advantage

 Can be traversed continuously
 Useful in CPU scheduling, games, etc.

4. Circular Doubly Linked List

It is a combination of Doubly + Circular Linked List.

 Each node has:

  • Previous pointer
  • Next pointer

 Last node connects to first node and vice versa

 Structure of Node

[ PREV | DATA | NEXT ]
 

 Diagram

↖────────────────────────↘
NULL ⇄ [10] ⇄ [20] ⇄ [30] ⇄ [40]
↙────────────────────────↗

 Working

  • Forward and backward movement possible
  • Forms a circular loop
  • No NULL in middle connections

19. Operations on Linked List

1. Creation of Linked List

Creation is the process of forming a linked list by creating nodes and linking them together.

 Explanation

  • First node is created and stored in memory
  • START (head) pointer stores address of first node
  • Each new node is linked to previous node

 If no node exists:

START = NULL
 

2. Insertion in Linked List

Insertion is the process of adding a new node into an existing linked list.

 Types of Insertion

A new node can be inserted at:

(a) At Beginning

  • New node becomes the first node
  • START pointer updated

(b) At End

  • New node is added after last node
  • Last node points to new node

(c) At Specific Position

  • Node is inserted between two existing nodes
  • Links are adjusted accordingly

 Diagram 

Before: START → [10] → [20] → [30]

After inserting 15 at beginning:
START → [15] → [10] → [20] → [30]
 

3. Deletion in Linked List

Deletion is the process of removing a node from an existing linked list.

 Types of Deletion

A node can be deleted from:

(a) Beginning

  • First node is removed
  • START moves to next node

(b) End

  • Last node is removed
  • Second last node points to NULL

(c) Specific Position

  • Node is removed from middle
  • Links are adjusted to maintain structure

 Diagram (Deletion Example)

Before: START → [10] → [20] → [30]

After deleting 20:
START → [10] → [30]
 

4. Traversal in Linked List

Traversal means visiting each node of the linked list one by one.

 Process

  1. Start from START
  2. Visit current node
  3. Move to next node using link
  4. Repeat until NULL is reached

 Diagram

START → [10] → [20] → [30] → NULL

 Key Points 

  • Creation → forming linked list
  • Insertion → adding new node
  • Deletion → removing node
  • Traversal → visiting all nodes
  • All operations are dynamic in nature

20. Dynamic Memory Allocation (DMA) vs Array vs Linked List

1. Memory Allocation Types

 (A) Static Memory Allocation (Array)

In static memory allocation, memory is allocated at compile time.

 Example (Array)

int A[5];

 Memory calculation (example):
If integer = 4 bytes
So memory = 5 × 4 = 20 bytes

 Drawback of Array

  • Fixed size (cannot change at runtime)
  • Memory wastage if full space is not used
  • Overflow problem if more elements are needed

 Example of Wastage

int A[10]
Used = 5 elements
Wasted = remaining 5 elements memory

 (B) Linked List (Dynamic Nature)

 Linked List uses Dynamic Memory Allocation (DMA)
 Memory is allocated at runtime

 Advantage

  • No memory wastage
  • Memory used only when required
  • Flexible size

 Memory in Linked List Node

Each node contains:

[ DATA | NEXT ]

 Each node is created dynamically.

 Example Memory Allocation

Node 1 →  100 address 
Node 2 →  200 address 
Node 3 →  300 address 
Node 4 →  400 address

Memory is NOT continuous.

 2. Dynamic Memory Allocation (DMA)

Dynamic Memory Allocation refers to the process of allocating and freeing memory at runtime using standard library functions.

 Time Concepts

 Compile Time

  • Source code is converted into executable code

 Runtime

  • Program is actually executing

 DMA works at runtime

3. DMA Functions in C

DMA is handled using <stdlib.h>

 (1) malloc()

 Allocates single block of memory

ptr = (int*) malloc(5 * sizeof(int));

 Does NOT initialize memory

 (2) calloc()

 Allocates multiple blocks of memory

ptr = (int*) calloc(5, sizeof(int));

✔ Initializes memory with 0

 (3) realloc()

 Changes size of previously allocated memory

ptr = realloc(ptr, newSize);

 Used to increase or decrease memory

 (4) free()

 Deallocates memory

free(ptr);

Releases unused memory

 4. Dynamic Memory in Linked List (Node Creation)

 Structure of Node

struct node {
int data;
struct node *next;
};

 Memory Allocation Example

struct node *newNode;

newNode = (struct node*) malloc(sizeof(struct node));

 Here:

  • Memory is created at runtime
  • newNode stores address of allocated memory

 5. Key Difference (Important Exam Point)

Feature Array Linked List
Memory type Static Dynamic
Allocation Compile time Runtime
Size Fixed Flexible
Memory usage May waste memory No wastage
Structure Continuous memory Non-continuous memory

 

Page 4 of 4