✅ Linked List: Definition

---

✅ 1. Introduction

A Linked List is an important topic in Data Structures.
It is used to store a collection of elements in a linear order, but unlike arrays, it does not store elements in continuous memory.

---

✅ 2. Definition of Linked List

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

✅ Each node contains two parts:

1. Data Part → stores the actual value/information
2. Link (Pointer) Part → stores the address of the next node

📌 Diagram:

[Data | Next] → [Data | Next] → [Data | Next] → NULL

Where:

• NULL shows the end of the linked list.

---

✅ 3. Node Structure of Linked List

A node can be represented as:

✅ Node Format:

+---------+----------+
|  DATA   |  NEXT    |
+---------+----------+

✅ Example in C:

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

---

✅ 4. Characteristics / Features of Linked List

✅ Main features are:

✅ 1. Dynamic Size

Linked list size can increase or decrease during runtime.

📌 No fixed size like arrays.

---

✅ 2. Non-Contiguous Memory Allocation

Nodes are stored at different memory locations, not continuously.

---

✅ 3. Linked Using Pointers

Nodes are connected using pointer address links.

---

✅ 4. Sequential Access

Elements are accessed sequentially, not directly like array indexing.

✅ Example:
To access 4th node, we must start from the first node and move step by step.

---

✅ 5. Working of Linked List

A linked list always has a starting pointer called HEAD.

✅ HEAD stores the address of the first node.

📌 Example:

HEAD → [10|•] → [20|•] → [30|NULL]

Here:

• HEAD points to node containing 10
• Node 10 points to node 20
• Node 20 points to node 30
• Node 30 points to NULL (end)

---

✅ 6. Types of Linked Lists (Brief)

Linked list is mainly of 3 types:

✅ 1. Singly Linked List

Each node points to the next node only.

10 → 20 → 30 → NULL

✅ 2. Doubly Linked List

Each node has two pointers:

• Previous
• Next

NULL ← 10 ↔ 20 ↔ 30 → NULL

✅ 3. Circular Linked List

Last node points back to the first node.

10 → 20 → 30
↑         ↓
←←←←←←←←←←

---

✅ 7. Advantages of Linked List

✅ Major advantages:

1. Dynamic memory allocation (size grows/shrinks)
2. Efficient insertion and deletion (no shifting like arrays)
3. No memory wastage (uses memory as needed)
4. Better than arrays when number of elements is unknown

---

✅ 8. Disadvantages of Linked List

❌ Limitations:

1. More memory required (extra pointer field)
2. No direct/random access like arrays
3. Traversing takes more time
4. More complex compared to arrays

---

✅ 9. Applications of Linked List

✅ Used in many areas such as:

• Stack and Queue implementation
• Dynamic memory management
• Browser history (forward/back)
• Music playlist (next/previous song)
• Polynomial representation
• Graph adjacency list

---

✅ Conclusion

A linked list is a dynamic linear data structure where elements are stored as nodes connected by pointers. It is very useful when frequent insertion and deletion operations are required, and memory allocation needs to be flexible.

---