Computer Science · 12th Grade · Object-Oriented Design and Data Structures · Weeks 10-18

Implementing Linked Lists (Singly and Doubly)

Students build and manipulate singly and doubly linked lists from scratch, understanding dynamic memory allocation.

• Common Core State Standards
• CSTA: 3B-AP-12
• CSTA: 3B-AP-14

About This Topic

Implementing linked lists from scratch is one of the most important hands-on exercises in 12th-grade computer science. Unlike arrays, linked lists allocate memory dynamically for each element, connecting nodes through pointers or references rather than storing data in contiguous memory. Students build Node classes, connect them into chains, and implement insertion, deletion, and traversal. This topic aligns with CSTA standard 3B-AP-14 and builds the foundational data structures knowledge required for college CS programs and technical interviews.

Singly linked lists allow traversal in one direction only, making them simple and memory-efficient. Doubly linked lists store references to both the next and previous nodes, enabling bidirectional traversal at the cost of extra memory per node. Students compare these trade-offs and identify scenarios where each fits: a browser history or music playlist benefits from a doubly linked list's bidirectional navigation, while a print queue might work fine with a singly linked list. This comparative analysis develops the habit of choosing data structures based on concrete requirements rather than habit.

Pointer manipulation is notoriously confusing when taught only abstractly. Active learning is particularly effective here because when students act out linked list operations physically, moving between classroom 'nodes' or drawing collaborative diagrams, the logic of reconnecting pointers during insertion or deletion becomes far more intuitive than staring at code.

Key Questions

1. Why would a developer choose a linked list over a standard array for data storage?
2. Compare the advantages and disadvantages of singly versus doubly linked lists.
3. Construct a linked list implementation that handles edge cases like empty lists or single-node lists.

Learning Objectives

• Construct a functional singly linked list implementation in code, demonstrating insertion and deletion operations.
• Compare the memory usage and traversal efficiency of singly and doubly linked lists through empirical testing.
• Analyze scenarios to determine whether a singly or doubly linked list is the more appropriate data structure.
• Design and implement a doubly linked list, including methods for adding and removing nodes at arbitrary positions.
• Critique the trade-offs between singly and doubly linked lists for specific application requirements.

Before You Start

Introduction to Object-Oriented Programming

Why: Students need to understand classes, objects, and instance variables to create Node objects and link them together.

Basic Pointers and References in Programming

Why: A foundational understanding of how variables can store memory addresses is essential for manipulating node connections.

Arrays and Array Manipulation

Why: Comparing linked lists to arrays requires students to know how arrays store data contiguously and their limitations with insertions/deletions.

Key Vocabulary

Node	A fundamental building block of a linked list, containing data and a reference (or pointer) to the next node in the sequence.
Head	A reference to the very first node in a linked list, serving as the entry point for accessing the list's elements.
Tail	A reference to the last node in a linked list, often used to efficiently add new elements to the end.
Pointer/Reference	A variable that stores the memory address of another variable, used in linked lists to connect one node to the next.
Dynamic Memory Allocation	The process of assigning memory to data structures during program execution, allowing lists to grow or shrink as needed.

Watch Out for These Misconceptions

Common Misconception

Linked lists are always better than arrays because they can grow dynamically.

What to Teach Instead

Linked lists use more memory per element (storing a pointer alongside each value) and do not support O(1) random access by index. For scenarios where elements are frequently accessed by position, arrays are often the better choice. Real-world comparisons help students see that neither structure is universally superior and that the right choice depends on the access pattern.

Common Misconception

Deleting a node from a linked list removes it from memory immediately.

What to Teach Instead

In languages with automatic memory management like Java and Python, the deleted node becomes eligible for garbage collection but is not immediately freed. In C or C++, the programmer must explicitly free the memory or it becomes a memory leak. Running the same deletion code in different languages during lab makes this difference concrete.

Common Misconception

A doubly linked list is just a singly linked list traversed twice.

What to Teach Instead

A doubly linked list has a prev pointer in each node, allowing the list to be traversed in either direction without restarting from the head. This structural difference enables efficient operations like insertBefore or deletePrevious that would require O(n) traversal in a singly linked list.

Active Learning Ideas

Simulation Game: Human Linked List

Each student is a 'node' holding a card with a value and pointing to the next student in line. The teacher calls operations: insert after node 3, delete node 5, traverse and print all values. Students must physically rearrange and update their pointer cards. Edge cases like deleting the head or tail node become immediately visible, making the required pointer updates concrete.

30 min·Whole Class

Collaborative Lab: Build It From Scratch

Pairs implement a singly linked list with insert, delete, and display methods, then extend it to a doubly linked list by adding a prev pointer and an insertBefore method. After completing both, partners write a 5-sentence comparison focusing on what code changed and which operations become easier or harder with bidirectional links.

60 min·Pairs

Think-Pair-Share: Linked List vs. Array

Present 5 scenarios: storing a leaderboard, implementing undo history, managing a shopping cart, indexing a database, streaming media chunks. Students individually choose the better data structure for each and justify their choice in writing. Pairs compare and discuss disagreements, then the class builds a shared decision framework on the board.

25 min·Pairs

Gallery Walk: Edge Case Debugging

Post 6 stations showing buggy linked list code, each with a different edge case failure: null pointer on empty list, losing the head reference during deletion, infinite loop on a faulty traversal, and others. Student pairs identify the bug, trace the pointer error, and write a 2-line fix. During debrief, pairs share which bug was hardest to spot and why.

35 min·Pairs

Real-World Connections

• Software engineers developing operating system process schedulers might use linked lists to manage the queue of tasks waiting for CPU time, where efficient insertion and deletion are critical.
• Developers building browser history features or undo/redo functionality in applications like Adobe Photoshop often employ doubly linked lists to allow users to navigate forward and backward through states.

Assessment Ideas

Quick Check

Present students with a small, partially implemented linked list code snippet. Ask them to identify the missing lines of code required to insert a new node at the beginning of a singly linked list and explain their reasoning.

Discussion Prompt

Pose the question: 'Imagine you are building a music player playlist. Would a singly or doubly linked list be a better choice, and why? Consider features like playing the next song, playing the previous song, and adding a song to the end.' Facilitate a class discussion comparing student choices.

Exit Ticket

On an index card, have students write down one advantage of using a linked list over an array for a specific task (e.g., inserting into the middle) and one disadvantage of a doubly linked list compared to a singly linked list.

Frequently Asked Questions

When would a real developer use a linked list instead of an array or ArrayList?

Linked lists are useful when frequent insertions or deletions at the beginning or middle of a sequence are needed, since those operations are O(1) once you have a reference to the relevant node. Arrays require shifting elements for those operations. However, linked lists are poor choices when random access by index is common, since that requires O(n) traversal from the head.

How does active learning help students understand pointer manipulation in linked lists?

Pointer logic is highly abstract and error-prone when studied only on paper. When students physically act as nodes and pointers, holding cards and literally re-pointing to each other during insertions and deletions, the mental model for managing references becomes far more concrete. These physical simulations directly reduce the frequency of null pointer errors in student code.

What is a sentinel node in a linked list?

A sentinel (or dummy) node is a placeholder at the head or tail of the list that does not store meaningful data. It simplifies edge-case handling by ensuring the list is never truly empty from the traversal code's perspective, eliminating special cases for operations on an empty list or at the boundary between the list and null.

Is it possible to have a circular linked list?

Yes. In a circular linked list, the last node's next pointer points back to the head instead of to null. This is useful for applications that cycle through a fixed set of elements, like round-robin scheduling. However, it requires careful traversal logic to avoid infinite loops, since there is no null pointer to signal the end of the list.