DS UNIT II – Linked Lists

1. Define Linked List

A Linked List is a collection of nodes where each node contains data and a pointer to the next node.

---

2. What are the types of linked lists?

• Singly Linked List
• Doubly Linked List
• Circular Linked List

---

3. List advantages of linked list over arrays

• Dynamic size (no fixed size)
• Efficient insertion and deletion
• No memory wastage

---

4. Define Doubly Linked List

A Doubly Linked List is a linked list where each node contains data, previous pointer, and next pointer.

---

5. What is a Circular Linked List?

A Circular Linked List is a linked list in which the last node points back to the first node instead of NULL.

---

6. What is a Self-Referential Structure?

A self-referential structure is a structure that contains a pointer to itself.

---

7. Write the structure of a node in linked list

struct Node 
{
    int data;

    struct Node *next;
};

---

8. Define Dynamic Memory Allocation in Linked List

It is the process of allocating memory for nodes at runtime using functions like malloc().

---

9. What is Traversal?

Traversal is the process of visiting each node in a linked list one by one.

---

10. Define Time Complexity of Insertion in Linked List

• At beginning → O(1)
• At end or middle → O(n)

Q1. Explain Singly Linked List with Operations

Singly Linked List is a collection of nodes containing data and next pointer.

STRUCTURE

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

TRAVERSAL

Start from HEAD
Visit node
Move to next until NULL

INSERTION

At Beginning
new->next = head
head = new

At End
Traverse to last
last->next = new

At Middle
new->next = temp->next
temp->next = new

DELETION

From Beginning
head = head->next

From End
second_last->next = NULL

From Middle
prev->next = curr->next

---

Q2. Explain Doubly Linked List

Each node contains prev, data, next

NULL ← [A] ↔ [B] ↔ [C] → NULL

Insertion at Beginning
new->next = head
head->prev = new
head = new

Deletion from Middle
temp->prev->next = temp->next
temp->next->prev = temp->prev

Supports forward and backward traversal

---

Q3. Explain Circular Linked List

Last node points to first node

HEAD → [10] → [20] → [30] ↑__________________________

Applications

• CPU scheduling
• Games
• Traffic systems

---

Q4. Compare Linked List vs Array

Feature	Linked List	Array
Memory	Dynamic	Fixed
Access	Sequential	Random
Insertion	Easy	Difficult
Deletion	Easy	Difficult
Speed	Slow	Fast

---

Q5. Algorithms for Insertion & Deletion

Insertion at Beginning
new->next = head
head = new

Deletion from End
second_last->next = NULL

---

Q6. Performance Analysis

Operation	Time
Traversal	O(n)
Insertion	O(1)
Deletion	O(n)
Search	O(n)

Linked List → Fast insertion, Slow searching