Unit 5: Linked List  (DSA)– Exam Revision Notes

1. Introduction to Linked List

• Linked List = A linear data structure where elements (nodes) are linked using pointers instead of contiguous memory.
  
• Each node contains:
  
  1. Data – Actual value stored.
     
  2. Pointer/Next – Address of next node.
     
• Advantage: Dynamic memory allocation, easy insertion/deletion.
  

2. Linked List as an Abstract Data Type (ADT)

• ADT defines logical operations without specifying implementation.
  
• Basic Operations:
  
  1. Insert(node, position) – Add node at specific position.
     
  2. Delete(position) – Remove node from a given position.
     
  3. Traverse() – Access nodes sequentially.
     
  4. Search(element) – Find a node containing the element.
     
  5. Update(position, element) – Modify node’s data.
     

3. Types of Linked Lists

1. Singly Linked List
   
   • Each node points to the next node.
     
   • Traversal is one-way only.
     
2. Doubly Linked List
   
   • Each node has next and previous pointers.
     
   • Supports two-way traversal.
     
   • Easier insertion/deletion at both ends.
     
3. Circular Linked List
   
   • Last node points back to the first node.
     
   • Can be singly or doubly linked.
     

4. Operations on Linked List

1. Insertion
   
   • At beginning: New node becomes head.
     
   • At end: New node added after last node.
     
   • After/before a node: Use pointer to adjust links.
     
2. Deletion
   
   • At beginning: Head moves to next node.
     
   • At end: Second last node’s next pointer = NULL.
     
   • Specific node: Adjust previous node’s pointer.
     
3. Traversal
   
   • Start from head → follow next pointers → reach NULL.
     

5. Linked Stacks and Queues

• Stack using Linked List: Top = head node, push/pop at head.
  
• Queue using Linked List: Front = head, Rear = tail, enqueue at tail, dequeue at head.
  

6. Advantages of Linked Lists

• Dynamic size – Grows/shrinks at runtime.
  
• Efficient insertion/deletion – No shifting like arrays.
  
• Flexible memory usage – No wasted space.
  
• Supports complex structures – Graphs, adjacency lists, etc.
  

7. Applications

1. Implement stacks and queues dynamically.
   
2. Dynamic memory allocation in OS (free lists).
   
3. Represent polynomial expressions, sparse matrices.
   
4. Undo/redo operations in software applications.
   

Key Takeaways – Unit 5

• Linked list = dynamic linear structure using pointers.
  
• Types: Singly, Doubly, Circular – each has unique traversal and insertion/deletion capabilities.
  
• Supports efficient memory usage and dynamic operations.
• Forms the basis for dynamic stacks, queues, and complex data structures.