Project 4: Linked List Library

Implement singly and/or doubly linked lists with safe insertion, deletion, and traversal.

Quick Reference

Attribute Value
Difficulty Intermediate
Time Estimate 1 week
Language C
Prerequisites Project 3, pointer ownership
Key Topics Pointers, ownership, invariants

1. Learning Objectives

By completing this project, you will:

  1. Implement linked list insertion and deletion safely.
  2. Maintain invariants for head/tail nodes.
  3. Build iterator-style traversal APIs.
  4. Manage memory for nodes without leaks.

2. Theoretical Foundation

2.1 Core Concepts

  • Nodes and pointers: Each node points to the next (and optionally previous).
  • Ownership: The list owns the nodes; payload ownership is a design choice.
  • Invariants: Head/tail pointers must be consistent after every operation.

2.2 Why This Matters

Linked lists appear in kernels, allocators, and embedded systems. They teach pointer manipulation with non-contiguous memory.

2.3 Historical Context / Background

Before dynamic arrays were cheap, linked lists were a common data structure for flexible insertion and deletion.

2.4 Common Misconceptions

  • “Linked lists are always faster”: They are often slower due to cache misses.
  • “Deletion is easy”: It is easy only if you track previous nodes correctly.

3. Project Specification

3.1 What You Will Build

A list library that supports:

  • list_init, list_free
  • list_push_front, list_push_back
  • list_pop_front, list_pop_back
  • list_insert_after, list_remove
  • list_foreach

3.2 Functional Requirements

  1. Support empty and single-node lists.
  2. Handle insert/remove at head and tail.
  3. Allow storing generic payloads via void *.
  4. Provide a cleanup callback for payloads.

3.3 Non-Functional Requirements

  • Reliability: No leaks, no dangling pointers.
  • Usability: Simple and well-documented API.
  • Performance: O(1) insertion/removal at ends.

3.4 Example Usage / Output

List list;
list_init(&list, free);
list_push_back(&list, strdup("a"));
list_push_back(&list, strdup("b"));
list_remove(&list, node_for_b);
list_free(&list);

3.5 Real World Outcome

You can use the list for queues, stacks, and free lists. You understand how to manipulate node pointers safely and predictably.

4. Solution Architecture

4.1 High-Level Design

List { head, tail, size } -> Node { data, next, prev }

4.2 Key Components

Component Responsibility Key Decisions
List struct Track head/tail/size Include size for convenience
Node struct Store payload and links Optional prev pointer
API functions Insert/remove/traverse Consistent error returns

4.3 Data Structures

typedef struct Node {
    void *data;
    struct Node *next;
    struct Node *prev;
} Node;

typedef struct {
    Node *head;
    Node *tail;
    size_t size;
    void (*free_fn)(void *);
} List;

4.4 Algorithm Overview

Key Algorithm: Remove node

  1. Rewire previous and next pointers.
  2. Update head/tail if needed.
  3. Free node and optionally payload.

Complexity Analysis:

  • Insert/remove at ends: O(1)
  • Search by value: O(n)

5. Implementation Guide

5.1 Development Environment Setup

cc -Wall -Wextra -O2 -g -o test_list test_list.c list.c

5.2 Project Structure

list/
├── src/
│   ├── list.c
│   └── list.h
├── tests/
│   └── test_list.c
└── README.md

5.3 The Core Question You’re Answering

“How do I safely link and unlink nodes without corrupting the chain?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Pointer rewiring
    • What happens when you remove the head?
    • How do you update tail when removing last node?
  2. Ownership
    • Who frees payloads?
    • How do you avoid double free?
  3. Traversal patterns
    • How do you iterate without losing the next pointer during deletion?

5.5 Questions to Guide Your Design

Before implementing, think through these:

  1. Will you implement singly or doubly linked lists?
  2. Should list_remove take a node pointer or value?
  3. Will list_foreach allow mutation?

5.6 Thinking Exercise

Trace a Removal

Draw a three-node list and remove the middle node. Which pointers must change?

5.7 The Interview Questions They’ll Ask

Prepare to answer these:

  1. “What are the pros and cons of linked lists vs arrays?”
  2. “How do you remove a node in a singly linked list?”
  3. “What invariants must a list maintain?”

5.8 Hints in Layers

Hint 1: Start with push/pop at front Only manage head pointer first.

Hint 2: Add tail support Maintain tail updates on insert/remove.

Hint 3: Add removal by node Pass a node pointer to simplify deletion.

5.9 Books That Will Help

Topic Book Chapter
Linked lists “Algorithms in C” Lists chapter
Pointer safety “C Interfaces and Implementations” Containers

5.10 Implementation Phases

Phase 1: Foundation (2-3 days)

Goals:

  • Basic node and list structs

Tasks:

  1. Implement list_init and list_push_front.

Checkpoint: Insert and traverse works.

Phase 2: Core Functionality (2-3 days)

Goals:

  • Full insertion/removal

Tasks:

  1. Add push/pop at back.
  2. Add removal of arbitrary node.

Checkpoint: Remove head, tail, middle correctly.

Phase 3: Polish & Edge Cases (1-2 days)

Goals:

  • Cleanup and iteration helpers

Tasks:

  1. Add list_foreach.
  2. Add list_free with payload cleanup.

Checkpoint: No memory leaks in tests.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
List type Singly vs doubly Doubly Easier deletion
API remove Node vs value Node Clear ownership

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Insert/remove Head/tail updates
Edge Cases Empty list Pop empty
Memory Tests Leaks/dangling Valgrind

6.2 Critical Test Cases

  1. Remove head: New head updates.
  2. Remove tail: Tail updates.
  3. Remove only node: List becomes empty.

6.3 Test Data

"a", "b", "c"

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Forgetting to update tail Corrupt list Update on last node removal
Losing next pointer Crash on iteration Store next before deleting
Double free of payloads Crash Use free callback carefully

7.2 Debugging Strategies

  • Print list after each operation.
  • Use valgrind to check for leaks.

7.3 Performance Traps

Linked lists are cache-inefficient. Use only when insertion/deletion patterns justify them.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add list_find by predicate.
  • Add list_size helper.

8.2 Intermediate Extensions

  • Implement iterator struct.
  • Add list_reverse.

8.3 Advanced Extensions

  • Add intrusive list variant.
  • Add lock-free list (research-heavy).

9. Real-World Connections

9.1 Industry Applications

  • Allocators: Free lists are linked lists.
  • Kernels: Task queues and scheduling.
  • Linux kernel list.h: Intrusive list implementation.

9.3 Interview Relevance

Linked list manipulation is a classic interview topic.

10. Resources

10.1 Essential Reading

  • “Algorithms in C” - Lists chapter
  • “C Interfaces and Implementations” - Containers

10.2 Video Resources

  • Data structure lectures (linked lists)

10.3 Tools & Documentation

  • man 3 malloc: Node allocation
  • Hash Table: Uses lists for chaining.
  • Memory Allocator: Uses free lists.

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain list invariants.
  • I can remove nodes without leaks.
  • I can compare lists vs arrays.

11.2 Implementation

  • All list operations work correctly.
  • Tests cover edge cases.
  • No memory leaks.

11.3 Growth

  • I can implement an intrusive list.
  • I can explain this project in an interview.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Push/pop at front and back.
  • Correct traversal.

Full Completion:

  • Remove arbitrary nodes and cleanup.

Excellence (Going Above & Beyond):

  • Intrusive list or iterator API.

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