Data Structures #1 — Linked List

A linked list is a sequence of nodes where each node points to the next. Unlike arrays, insertion and deletion at the head are O(1). This article implements singly and doubly linked lists with all standard operations.

1. Singly Linked List — Node + Basic Structure

2. Reverse a Linked List — Classic Interview Question

3. Detect Cycle — Floyd's Tortoise and Hare

4. Doubly Linked List

Each node has prev and next pointers:

Key Takeaways

• Singly linked: O(1) prepend/append, O(n) search/delete. Minimal memory (one pointer per node).
• Doubly linked: O(1) both ends, O(n) search. Extra prev pointer per node.
• Reverse: iterate with prev/current/next pointers — O(n) time, O(1) space.
• Cycle detection: Floyd's algorithm — slow moves 1 step, fast moves 2. If they meet, cycle exists.
• Linked lists shine when you need frequent insertion/deletion at the head (queues, stacks). Arrays are better for random access.

Next: Data Structures #2 — Hash Table — build a hash table with bucket array and collision chaining.