Lecture 44: Linked Lists

Introduction

• Host: Love Babbar
• Topic: Linked Lists
• Video sponsored by Coding Ninjas

What is a Linked List?

• A linear data structure formed by a collection of nodes.
  • Node: Combination of data and a pointer to the next node.
  • Example of a node: Contains data (e.g., 3) and a pointer (address) to the next node.
  • Last node points to NULL.

Why Use Linked Lists?

• Dynamic size: Allows increasing/decreasing size at runtime.
• Memory efficiency: No memory wastage unlike arrays.
• Insertion/Deletion: Easier compared to arrays as no shifting of elements is required.

Types of Linked Lists

1. Singly Linked List: Each node points to the next node.
2. Doubly Linked List: Each node points to both next and previous nodes.
3. Circular Linked List: Last node points back to the first node.
4. Circular Doubly Linked List: Combines features of doubly and circular linked lists.

Singly Linked List Implementation

• Node Structure:
  • Contains data (int) and a pointer to the next node.
• Insertion at Head:
  • Create a new node.
  • Update pointers to connect new node to the head.
• Insertion at Tail:
  • Traverse to the last node and attach the new node.
• Insertion at a Position:
  • Traverse to the desired position and update pointers to insert the new node.

Deletion in Singly Linked List

• Delete Node:
  • Handle cases for head, middle, and last nodes.
  • Free memory associated with the deleted node.

Doubly Linked List Implementation

• Node Structure:
  • Contains data, pointer to the next node, and pointer to the previous node.
• Insertion:
  • Similar to singly linked list with additional pointer updates for the previous node.
• Deletion:
  • Similar deletion logic as singly linked list with additional checks for previous pointers.

Circular Linked List Implementation

• Node Structure:
  • Similar to singly linked list, but last node points back to the first node.
• Insertion:
  • Handle empty list and non-empty list differently.
• Traversal:
  • Use a loop to print nodes until the tail is reached again.
• Deletion:
  • Check for different cases: empty list, single node, or multiple nodes.

Summary

• Learned about linked lists, their types, and how to implement them.
• Covered insertion and deletion techniques for both singly and doubly linked lists, as well as circular linked lists.
• Homework: Implement deletion in a doubly linked list and handle edge cases for all types.

Further Learning

• Refer to Code Studio for more resources and practice problems related to linked lists.