Project 2: Linked List Toolkit

Build a linked list library (singly, doubly, circular) and use it to power an undo/redo system.

Quick Reference

Attribute Value
Difficulty Intermediate
Time Estimate 1 week
Language C (Alternatives: Rust, Go, Python)
Prerequisites Project 1, pointers, malloc/free
Key Topics Node ownership, pointer manipulation, O(1) insert/delete

1. Learning Objectives

By completing this project, you will:

  1. Implement singly, doubly, and circular linked lists.
  2. Handle edge cases like empty lists and single-node lists.
  3. Compare traversal cost vs insertion cost against arrays.
  4. Build an undo/redo stack using linked list nodes.

2. Theoretical Foundation

2.1 Core Concepts

  • Node-based storage: Each element owns a node containing data and pointer(s).
  • Indirection: Traversal is pointer chasing; locality is poor but insertion is cheap.
  • Head/tail invariants: Correctness depends on consistent head/tail updates.
  • Doubly-linked trade-offs: Extra pointers buy bidirectional traversal and O(1) deletes.

2.2 Why This Matters

Linked lists are the simplest non-contiguous structure. Understanding them makes every tree, graph, and hash bucket implementation more intuitive.

2.3 Historical Context / Background

Linked lists appeared in early systems programming as a natural solution for variable-size collections before dynamic arrays were common in high-level languages.

2.4 Common Misconceptions

  • “Linked lists are always faster”: Random access is O(n) and cache misses are expensive.
  • “Doubly-linked is always better”: Extra memory and pointer updates can slow operations.

3. Project Specification

3.1 What You Will Build

  • A linked list library with standard operations.
  • A CLI tool to visualize list operations.
  • An undo/redo system for text edits backed by a doubly-linked list.

3.2 Functional Requirements

  1. Implement push_front, push_back, insert_after, remove.
  2. Support singly and doubly linked lists.
  3. Provide a circular list variant for round-robin traversal.
  4. Implement undo/redo with two lists or a doubly-linked list cursor.

3.3 Non-Functional Requirements

  • Performance: O(1) insert/delete when node is known.
  • Reliability: No memory leaks (use free).
  • Usability: CLI output shows pointer addresses and list shape.

3.4 Example Usage / Output

$ ./linkedlist_demo
Insert 10 at head: [10] -> NULL
Insert 20 at tail: [10] -> [20] -> NULL
Delete 10: [20] -> NULL
Undo/redo:
Text: "Hello" -> undo -> "" -> redo -> "Hello"

3.5 Real World Outcome

You can run the demo and watch nodes appear with their addresses. The undo/redo tool shows the active cursor between a “past” list and a “future” list. Each edit is a node; undo moves the cursor backward, redo forward.

4. Solution Architecture

4.1 High-Level Design

┌──────────────┐     ┌──────────────────┐     ┌──────────────────┐
│ List Library │────▶│ CLI Visualizer   │────▶│ Undo/Redo Engine │
└──────────────┘     └──────────────────┘     └──────────────────┘

4.2 Key Components

Component Responsibility Key Decisions
Node types Store data + pointers Single vs double pointers
List API Insert/delete/traverse Consistent invariants
Undo/redo Track edit history Cursor vs two stacks

4.3 Data Structures

typedef struct Node {
    char* text;
    struct Node* next;
    struct Node* prev;
} Node;

typedef struct {
    Node* head;
    Node* tail;
    size_t size;
} DoublyLinkedList;

4.4 Algorithm Overview

Key Algorithm: Insert After Node

  1. Save target->next.
  2. Link new node between target and next.
  3. Update tail if needed.

Complexity Analysis:

  • Time: O(1) for insert/delete with node; O(n) for search
  • Space: O(n) nodes

5. Implementation Guide

5.1 Development Environment Setup

clang -Wall -Wextra -g -o linkedlist_demo src/*.c

5.2 Project Structure

project-root/
├── src/
│   ├── list.c
│   ├── list.h
│   ├── undo.c
│   └── main.c
├── tests/
│   └── test_list.c
└── Makefile

5.3 The Core Question You’re Answering

“How can I manage a growing collection when memory is not contiguous and I still need fast insert/delete?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Pointer ownership
    • Who allocates and who frees nodes?
  2. Null pointers
    • How to detect list ends safely
  3. Double linking invariants
    • node->next->prev == node must always hold

5.5 Questions to Guide Your Design

  1. How will you represent empty vs single-node lists?
  2. Should your API expose raw nodes or hide them?
  3. How will you visualize forward and backward links?

5.6 Thinking Exercise

Draw a list of three nodes and simulate deleting the middle node. Update all pointers by hand and verify invariants.

5.7 The Interview Questions They’ll Ask

  1. “Why is deletion O(1) with a doubly-linked list?”
  2. “What are the memory trade-offs vs arrays?”
  3. “How would you detect a cycle?”

5.8 Hints in Layers

Hint 1: Centralize node creation Write a helper that allocates and initializes nodes.

Hint 2: Update tail carefully If deleting tail, move tail to tail->prev.

Hint 3: Add a list validator Count nodes and verify prev pointers to catch bugs.

5.9 Books That Will Help

Topic Book Chapter
Linked lists Introduction to Algorithms (CLRS) Ch. 10.2
Pointers C Programming: A Modern Approach Ch. 11

5.10 Implementation Phases

Phase 1: Foundation (2 days)

Goals:

  • Implement singly-linked list
  • Basic traversal output

Tasks:

  1. Create node and list structs.
  2. Add push/pop operations.

Checkpoint: List prints correctly after each operation.

Phase 2: Core Functionality (3 days)

Goals:

  • Add doubly and circular lists
  • Add remove by node

Tasks:

  1. Implement prev pointers and update logic.
  2. Add circular traversal option.

Checkpoint: Forward/backward traversal matches expected order.

Phase 3: Polish & Edge Cases (2 days)

Goals:

  • Build undo/redo demo
  • Validate memory cleanup

Tasks:

  1. Build edit history using list nodes.
  2. Add list_destroy with full free.

Checkpoint: Undo/redo works and valgrind is clean.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Undo/redo model Two stacks, cursor Cursor in DLL Mirrors editor behavior
Memory for text Copy string, pointer Copy string Avoid dangling references

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Verify operations insert, remove, size
Integration Tests Undo/redo flow multiple edits
Edge Case Tests Empty list remove from empty

6.2 Critical Test Cases

  1. Remove head/tail in 1-node list.
  2. Insert after tail.
  3. Undo after new edit clears redo list.

6.3 Test Data

Edits: "Hello", " ", "World", "!"

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Forgetting to update prev Backward traversal crash Update both links
Losing head/tail List becomes detached Handle empty list cases
Memory leaks valgrind reports leaks Free nodes on remove

7.2 Debugging Strategies

  • Print node addresses with data to track links.
  • Validate list size by counting nodes.

7.3 Performance Traps

  • Frequent searches make linked lists slower than arrays for random access.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add find and remove_by_value.
  • Add list reverse operation.

8.2 Intermediate Extensions

  • Implement a free list for node reuse.
  • Add iterator-style traversal API.

8.3 Advanced Extensions

  • Implement a lock-free list (single producer/consumer).
  • Add cycle detection (Floyd’s algorithm).

9. Real-World Connections

9.1 Industry Applications

  • Media players: playlist navigation.
  • Text editors: undo/redo history.
  • Redis: uses linked lists for quick list operations.
  • Linux kernel: extensive use of intrusive lists.

9.3 Interview Relevance

  • Deleting nodes with only pointer access is a common interview question.

10. Resources

10.1 Essential Reading

  • Introduction to Algorithms (CLRS) - Ch. 10.2
  • C Programming: A Modern Approach - Ch. 11

10.2 Video Resources

  • “Linked Lists in C” - university data structures lectures

10.3 Tools & Documentation

  • Valgrind: https://valgrind.org/

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain list invariants.
  • I can compare linked lists vs dynamic arrays.
  • I can detect and fix pointer bugs.

11.2 Implementation

  • All operations work on empty and single-node lists.
  • Undo/redo behaves correctly.
  • No memory leaks.

11.3 Growth

  • I can describe when linked lists are the right choice.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Singly and doubly linked lists implemented.
  • CLI shows operations and addresses.

Full Completion:

  • Undo/redo demo plus tests.

Excellence (Going Above & Beyond):

  • Circular list and cycle detection implemented.

This guide was generated from DATA_STRUCTURES_FROM_FIRST_PRINCIPLES.md. For the complete learning path, see the parent directory README.