Chapter 4 - Problem Solving with Linked Lists

Problem Solving with Linked Lists

We can build chains of nodes and call methods on individual nodes. But most useful operations involve the entire chain: print every value, count the nodes, search for a specific element, add a node at a particular position. All of these require visiting nodes one at a time, which means we need a traversal pattern.

In Chapter 3, array traversal used an index variable that incremented from 0 to Length. Linked list traversal works differently. There are no indices. Instead, we use a reference variable that starts at the first node and follows Next references until it reaches null. The shape of the work is the same (visit every element, do something with it), but the mechanism changes because the data is organized differently.

There is also a structural problem. Right now, a “linked list” is a reference to the first node and nothing more. If we add a node at the front, we have to remember to update whatever variable holds that head reference. If outside code reaches into a node’s Next field and wires it back to an earlier node, it creates a cycle, and any traversal loop runs forever. The nodes are exposed, and nothing prevents these mistakes.

This section addresses both concerns. We start with traversal patterns for processing chains, then build a class that manages the chain and hides the nodes behind a controlled interface.

The Traversal Pattern

Here is array traversal and linked list traversal, side by side:

ARRAY TRAVERSAL                    LINKED LIST TRAVERSAL

for (int i = 0;                    LinkedListNode? current = head;
     i < arr.Length;               while (current != null)
     i++)                          {
{                                      // do something with current.Value
    // do something with arr[i]        current = current.Next;
}                                  }

The array version moves through elements by incrementing an index. The linked list version moves through elements by advancing a reference. Both stop when they have visited everything: the index reaches Length, or the reference reaches null.

Consider a three-node chain with values 85, 92, and 78:

  head
  ┌──────┐
  │ ref ──>┌──────────┐    ┌──────────┐    ┌──────────┐
  └──────┘ │ V: 85    │───>│ V: 92    │───>│ V: 78    │───> null
           └──────────┘    └──────────┘    └──────────┘

A traversal that displays every value:

LinkedListNode? current = head;
while (current != null)
{
    Console.WriteLine(current.Value);
    current = current.Next;
}

Translation: “Bind head to current. While current is not null, display current.Value, then advance current to current.Next.”

Trace through the loop:

Iteration	current points to	current.Value	Action	current after advance
1	node(85)	85	display 85	node(92)
2	node(92)	92	display 92	node(78)
3	node(78)	78	display 78	null
—	null	—	loop exits	—

After three iterations, current is null and the loop condition fails. Every node was visited exactly once.

The line current = current.Next is what advances through the chain. On each iteration, current is rebound to whatever current.Next refers to. When we reach the last node, current.Next is null, so after that advance current is null and the loop ends.

Try it yourself.

What does this code display? Assume head refers to a chain with values 10, 20, 30.

LinkedListNode? current = head;
while (current != null)
{
    Console.WriteLine(current.Value * 2);
    current = current.Next;
}

Reveal answer

Output:

20
40
60

Each value is doubled before display. The traversal visits 10, 20, 30 in order, and the loop body prints current.Value * 2 on each iteration.

If your answer differed, trace through each iteration and identify where your reasoning went wrong.

Try it yourself.

What does this code display? The chain holds values 5, 12, 3, 8.

LinkedListNode? current = head;
int count = 0;
while (current != null)
{
    if (current.Value > 7)
    {
        count++;
    }
    current = current.Next;
}
Console.WriteLine(count);

Reveal answer

Output:

The loop counts nodes whose value exceeds 7. Of the four values (5, 12, 3, 8), two satisfy the condition: 12 and 8.

If your answer differed, trace the state of count on each iteration.

Standalone Traversal Problems

Before wrapping operations inside a class, we write them as standalone code that operates on a head reference. Writing them this way lets us focus on the traversal logic without the overhead of class definitions and methods.

Each of the following patterns starts from a head variable that refers to the first node in a chain.

Count nodes:

int count = 0;
LinkedListNode? current = head;
while (current != null)
{
    count++;
    current = current.Next;
}

Translation: “Bind 0 to count. Bind head to current. While current is not null, increment count by 1, then advance current to current.Next.”

This is accumulation. The accumulator is count, initialized to 0, incremented on each iteration. The pattern is the same one we used for summing and counting in arrays. The loop structure changed, but the problem shape did not.

Sum all values:

int sum = 0;
LinkedListNode? current = head;
while (current != null)
{
    sum += current.Value;
    current = current.Next;
}

Another accumulation. The accumulator is sum, initialized to 0, and each node’s value is added to it.

Find maximum:

int max = head.Value;
LinkedListNode? current = head.Next;
while (current != null)
{
    if (current.Value > max)
    {
        max = current.Value;
    }
    current = current.Next;
}

This follows the same tracking pattern we used for finding the maximum in an array. Initialize max with the first element’s value, then start the traversal from the second element. On each iteration, update max if the current value is larger.

Notice that current starts at head.Next, not head. The first node’s value is already stored in max, so we begin comparing from the second node. This is the same decision we made for the array version, where max started at arr[0] and the loop started at index 1.

Contains (search):

bool found = false;
LinkedListNode? current = head;
while (current != null)
{
    if (current.Value == target)
    {
        found = true;
    }
    current = current.Next;
}

The contains pattern walks through every node, checking whether its value matches the target. If any node matches, found is set to true.

This version visits every node even after finding a match. We improve on that later when we write the method version.

Try it yourself.

Trace the sum traversal on a chain with values 4, 7, 2, 9. Fill in the state table:

Iteration	current points to	current.Value	sum (before)	sum (after)
1	?	?	?	?
2	?	?	?	?
3	?	?	?	?
4	?	?	?	?

What is the final value of sum?

Reveal answer

Iteration	current points to	current.Value	sum (before)	sum (after)
1	node(4)	4	0	4
2	node(7)	7	4	11
3	node(2)	2	11	13
4	node(9)	9	13	22

Final value of sum: 22.

Compare your table row by row and note any differences.

Try it yourself.

Write a standalone traversal that finds the minimum value in a chain. Assume the chain has at least one node. Model your code on the maximum pattern above.

Reveal answer

int min = head.Value;
LinkedListNode? current = head.Next;
while (current != null)
{
    if (current.Value < min)
    {
        min = current.Value;
    }
    current = current.Next;
}

The only change from the maximum version: < replaces >, and the variable is named min instead of max.

Self-correct against the model above.

Try it yourself.

Write a standalone traversal that counts how many nodes in a chain have a value greater than a given integer threshold.

Reveal answer

int count = 0;
LinkedListNode? current = head;
while (current != null)
{
    if (current.Value > threshold)
    {
        count++;
    }
    current = current.Next;
}

Self-correct against the model above.

The LinkedList Wrapper Class

The standalone traversal patterns work, but they operate on a bare head variable, and that creates problems.

When we add a node at the front of the chain, we have to update head. If a caller forgets that step, the new node is created but the list appears unchanged because head still points to the old first node. Worse, outside code has direct access to every node’s Next field and can rewire the chain in any way it wants. In the Section 1 review, we saw what happens when someone writes r.Next = p on a three-node chain: a cycle forms, and any traversal that follows Next references loops forever. And underlying both of these risks is a more basic issue: there is no object that represents “the list.” We pass around a node reference and rely on every piece of code to treat it as the head, with no enforcement.

A wrapper class solves these problems. It owns the head reference, provides operations through public methods, and keeps the nodes private so outside code cannot tamper with the chain.

class LinkedList
{
    private LinkedListNode? head;
 
    public LinkedList()
    {
        this.head = null;
    }
}

Description: “LinkedList is a class with a private nullable LinkedListNode field named head. The constructor creates an empty list by binding null to head.”

The head field is private. Outside code cannot read it, write to it, or follow it to reach the nodes. The only way to interact with the list is through public methods that the LinkedList class defines.

An empty list has this.head bound to null. There are no nodes.

  myList
  ┌──────┐
  │ ref ──>┌───────────────┐
  └──────┘ │ head: null    │
           └───────────────┘

Prepend

The first operation to add is inserting at the front. In Section 1, we wrote this as three lines of standalone code:

LinkedListNode newFront = new LinkedListNode(90);
newFront.Next = a;
a = newFront;

As a method on LinkedList, the same logic operates on this.head instead of a loose variable:

public void Prepend(int value)
{
    LinkedListNode newNode = new LinkedListNode(value);
    newNode.Next = this.head;
    this.head = newNode;
}

Description: “Prepend creates a new node with the given value, points it at the current head, and makes it the new head.”

LinkedList scores = new LinkedList();
scores.Prepend(78);
scores.Prepend(92);
scores.Prepend(85);

After scores.Prepend(78), the list contains one node:

  scores
  ┌──────┐
  │ ref ──>┌───────────────┐
  └──────┘ │ head: ref ────────>┌──────────┐
           └───────────────┘    │ V: 78    │───> null
                                └──────────┘

After scores.Prepend(92), the new node points at the node holding 78:

  scores
  ┌──────┐
  │ ref ──>┌───────────────┐
  └──────┘ │ head: ref ────────>┌──────────┐    ┌──────────┐
           └───────────────┘    │ V: 92    │───>│ V: 78    │───> null
                                └──────────┘    └──────────┘

After scores.Prepend(85):

  scores
  ┌──────┐
  │ ref ──>┌───────────────┐
  └──────┘ │ head: ref ────────>┌──────────┐    ┌──────────┐    ┌──────────┐
           └───────────────┘    │ V: 85    │───>│ V: 92    │───>│ V: 78    │───> null
                                └──────────┘    └──────────┘    └──────────┘

Each Prepend adds to the front, so the values appear in reverse order of insertion. The last value prepended (85) is the first node in the chain.

Translation for scores.Prepend(85);: “Call the Prepend method on the object referred to by scores with argument 85.”

Try it yourself.

Starting from an empty LinkedList named items, what does the chain look like after these calls?

items.Prepend(10);
items.Prepend(20);
items.Prepend(30);

List the values in chain order, from head to tail.

Reveal answer

30, 20, 10.

Each Prepend inserts at the front. The first call puts 10 at the head. The second puts 20 ahead of 10. The third puts 30 ahead of 20. Reading from head to tail: 30 → 20 → 10 → null.

If your answer differed, trace each Prepend call and draw the chain after each one.

Display and Count

Display and Count both traverse the full chain. Each one uses the same while (current != null) pattern from the standalone versions, with this.head as the starting point.

public void Display()
{
    LinkedListNode? current = this.head;
    while (current != null)
    {
        Console.Write(current.Value + " ");
        current = current.Next;
    }
    Console.WriteLine();
}

Description: “Display prints every value in the list on one line, separated by spaces, followed by a newline.”

public int Count()
{
    int count = 0;
    LinkedListNode? current = this.head;
    while (current != null)
    {
        count++;
        current = current.Next;
    }
    return count;
}

Description: “Count traverses the list, incrementing a counter for each node, and returns the total.”

LinkedList scores = new LinkedList();
scores.Prepend(78);
scores.Prepend(92);
scores.Prepend(85);
 
scores.Display();                     // displays: 85 92 78
Console.WriteLine(scores.Count());    // displays: 3

These are the standalone display and count patterns from earlier, placed inside the class with this.head as the starting point instead of a standalone head variable.

Try it yourself.

Write a method named Sum on LinkedList that returns the sum of all values in the list. If the list is empty, it should return 0.

Reveal answer

public int Sum()
{
    int sum = 0;
    LinkedListNode? current = this.head;
    while (current != null)
    {
        sum += current.Value;
        current = current.Next;
    }
    return sum;
}

When the list is empty, this.head is null, the loop body never executes, and the method returns 0.

Self-correct against the model above.

Contains

The standalone search version used a boolean flag and visited every node, even after finding a match. As a method, we can improve on that with an early return:

public bool Contains(int value)
{
    LinkedListNode? current = this.head;
    while (current != null)
    {
        if (current.Value == value)
        {
            return true;
        }
        current = current.Next;
    }
    return false;
}

Description: “Contains traverses the list looking for a node with the given value. If it finds one, it returns true immediately. If it reaches the end without finding a match, it returns false.”

LinkedList scores = new LinkedList();
scores.Prepend(78);
scores.Prepend(92);
scores.Prepend(85);
 
Console.WriteLine(scores.Contains(92));   // displays: True
Console.WriteLine(scores.Contains(100));  // displays: False

In the call scores.Contains(92), the traversal reaches the node with value 92 on the second iteration and returns true without visiting the third node. In the call scores.Contains(100), the traversal visits all three nodes, finds no match, and returns false.

Try it yourself.

A list contains the values 5, 10, 15, 20 (in chain order from head to tail). How many nodes does Contains visit when called with each of these arguments?

Contains(5)
Contains(15)
Contains(25)

Reveal answer

Contains(5) visits 1 node. The first node matches, and the method returns immediately.
Contains(15) visits 3 nodes. It checks 5, then 10, then finds 15 and returns.
Contains(25) visits 4 nodes. It checks all four values, finds no match, and returns false.

If your answers differed, trace the traversal for each call.

Append

Prepend adds at the front in three steps, regardless of list size. Adding at the end requires more work, because the list must be traversed to find the last node.

public void Append(int value)
{
    LinkedListNode newNode = new LinkedListNode(value);
    if (this.head == null)
    {
        this.head = newNode;
        return;
    }
    LinkedListNode current = this.head;
    while (current.Next != null)
    {
        current = current.Next;
    }
    current.Next = newNode;
}

Description: “Append creates a new node with the given value. If the list is empty, the new node becomes the head. Otherwise, the method traverses to the last node in the chain and wires the new node onto the end.”

There are two cases to handle. When the list is empty, this.head is null, and there is no chain to traverse. The new node simply becomes the head. When the list has at least one node, the method walks current forward until current.Next is null, meaning current is the last node. Then it sets current.Next to the new node, extending the chain by one.

Notice the loop condition: current.Next != null, not current != null. The traversal stops at the last node, not past it. If we advanced until current was null, we would have no reference to wire the new node onto, because null does not refer to any object.

LinkedList data = new LinkedList();
data.Append(10);
data.Append(20);
data.Append(30);
data.Display();   // displays: 10 20 30

Unlike Prepend, Append preserves insertion order. The first value appended is the first node in the chain, and the last value appended is the last node.

The cost difference matters. Prepend takes the same three steps regardless of how many nodes are in the list. Append walks through every existing node to find the end, so appending to a list with 1,000 nodes takes 1,000 steps. This is the first concrete case where the cost of a linked list operation depends on which operation we call.

Try it yourself.

Starting from an empty LinkedList, predict the output of Display after these calls:

LinkedList mix = new LinkedList();
mix.Append(1);
mix.Prepend(2);
mix.Append(3);
mix.Prepend(4);
mix.Display();

Reveal answer

Output:

4 2 1 3

After Append(1): chain is 1.

After Prepend(2): 2 is placed before 1. Chain is 2 → 1.

After Append(3): 3 is placed after 1. Chain is 2 → 1 → 3.

After Prepend(4): 4 is placed before 2. Chain is 4 → 2 → 1 → 3.

If your answer differed, trace each call and draw the chain after each one.

Try it yourself.

A LinkedList has 500 nodes. How many nodes does Prepend visit (not counting the new node it creates)? How many does Append visit?

Reveal answer

Prepend visits 0 existing nodes. It creates a new node, points it at the current head, and updates head. The number of nodes in the list does not matter.

Append visits all 500 existing nodes. It traverses from head to the last node, then wires the new node onto the end.

If your answer differed, review the code for both methods and identify which one contains a traversal loop.

RemoveFirst

Removing the first node advances head past it:

public void RemoveFirst()
{
    if (this.head != null)
    {
        this.head = this.head.Next;
    }
}

Description: “RemoveFirst sets the head to the second node. If the list is empty, it does nothing.”

LinkedList data = new LinkedList();
data.Prepend(3);
data.Prepend(2);
data.Prepend(1);
// chain: 1 → 2 → 3
 
data.RemoveFirst();
// chain: 2 → 3
 
data.RemoveFirst();
// chain: 3
 
data.Display();    // displays: 3

After this.head = this.head.Next, the old first node has no references pointing to it. The LinkedList no longer knows about it, and the runtime will eventually reclaim its memory.

When the list has one node, this.head.Next is null, so this.head becomes null and the list is empty. When the list is already empty, the if condition fails and the method does nothing.

Try it yourself.

A list contains values 10, 20, 30 (from head to tail). What does the list contain after calling RemoveFirst twice?

Reveal answer

After the first RemoveFirst: 20, 30. (The node with 10 was removed.)

After the second RemoveFirst: 30. (The node with 20 was removed.)

If your answer differed, trace each call and note which node head points to after each one.

Why Encapsulation Matters

Return to the cycle problem from Section 1. With raw nodes, outside code can write:

LinkedListNode p = new LinkedListNode(1);
LinkedListNode q = new LinkedListNode(2);
LinkedListNode r = new LinkedListNode(3);
p.Next = q;
q.Next = r;
r.Next = p;  // cycle: any traversal loops forever

Nothing prevents this. The Next fields are public, and any code can wire any node to any other node.

With the LinkedList class, outside code never touches Next fields. The only operations available are Prepend, Append, Display, Count, Contains, Sum, and RemoveFirst. None of them can create a cycle, because every method that modifies the chain does so in a controlled way: Prepend always points the new node at the current head, Append always wires the new node onto the end where Next is null, and RemoveFirst always advances head forward.

Encapsulation is the practice of hiding a class’s internal data and exposing only controlled operations. The LinkedList class encapsulates its node chain: head is private, the nodes are unreachable from outside, and the public methods are the only way to interact with the list. Because the class is the only code that touches its own fields, it can guarantee that the chain is well-formed: no cycles, and head always points to the true first node or null.

InsertAt

Inserting at a specific position requires traversing to the node before the insertion point, then rewiring references to fit the new node into the chain.

public void InsertAt(int index, int value)
{
    if (index == 0)
    {
        Prepend(value);
        return;
    }
 
    LinkedListNode? current = this.head;
    for (int i = 0; i < index - 1; i++)
    {
        if (current == null)
        {
            return;
        }
        current = current.Next;
    }
 
    if (current == null)
    {
        return;
    }
 
    LinkedListNode newNode = new LinkedListNode(value);
    newNode.Next = current.Next;
    current.Next = newNode;
}

Description: “InsertAt places a new node with the given value at the specified index. Index 0 is equivalent to Prepend. For any other index, the method traverses to the node at position index minus 1, then wires the new node between that node and its successor.”

Consider a list with values 10, 20, 30 (from head to tail), and the call InsertAt(2, 99).

Before insertion:

  head ──> [10] ──> [20] ──> [30] ──> null
                     ^
                     current stops here (index - 1 = 1)

The method traverses to the node at position 1 (the node with value 20). Then it creates a new node with value 99, points the new node’s Next at current.Next (the node with 30), and sets current.Next to the new node.

After insertion:

  head ──> [10] ──> [20] ──> [99] ──> [30] ──> null

The existing nodes did not move. Only two references changed: the new node’s Next, and the predecessor’s Next.

Index 0 is a special case because there is no predecessor node. Inserting at position 0 means placing the new node before the current head, which is exactly what Prepend does. The method calls Prepend and returns.

If the index is beyond the end of the list, the traversal reaches null before arriving at the target position, and the method does nothing.

Try it yourself.

A list contains values 5, 10, 15. Draw the chain after each of these calls, in order:

InsertAt(1, 7)
InsertAt(0, 3)
InsertAt(5, 20)

Reveal answer

After InsertAt(1, 7): 5 → 7 → 10 → 15. The new node with 7 is inserted between the node at index 0 (value 5) and the node at index 1 (value 10).

After InsertAt(0, 3): 3 → 5 → 7 → 10 → 15. Index 0 triggers Prepend, placing 3 at the front.

After InsertAt(5, 20): 3 → 5 → 7 → 10 → 15 → 20. The list currently has 5 nodes (indices 0 through 4). Index 5 is one past the last node, so the method traverses to the node at position 4 (value 15) and wires 20 onto the end.

If your answers differed, trace each call through the method body.

RemoveAt

Removing a node at a specific position follows a similar structure to InsertAt: traverse to the predecessor, then rewire its Next to skip over the target node.

public void RemoveAt(int index)
{
    if (this.head == null)
    {
        return;
    }
 
    if (index == 0)
    {
        this.head = this.head.Next;
        return;
    }
 
    LinkedListNode? current = this.head;
    for (int i = 0; i < index - 1; i++)
    {
        if (current.Next == null)
        {
            return;
        }
        current = current.Next;
    }
 
    if (current.Next == null)
    {
        return;
    }
 
    current.Next = current.Next.Next;
}

Description: “RemoveAt removes the node at the given index. Index 0 removes the head. For any other index, the method traverses to the predecessor and skips over the target by pointing the predecessor’s Next to the node after the target.”

The key line is current.Next = current.Next.Next. The predecessor (current) no longer points at the target node. It points at whatever came after the target. The target node is now unreachable from the list.

Consider a list with values 10, 20, 30, 40 and the call RemoveAt(2):

Before removal:

  head ──> [10] ──> [20] ──> [30] ──> [40] ──> null
                     ^
                     current (predecessor, at index 1)

After current.Next = current.Next.Next:

  head ──> [10] ──> [20] ──> [40] ──> null

The node with value 30 is no longer part of the chain.

Try it yourself.

A list contains values 1, 2, 3, 4, 5. What does the list contain after these calls, in order?

RemoveAt(0)
RemoveAt(2)
RemoveAt(1)

Reveal answer

Starting list: 1, 2, 3, 4, 5.

After RemoveAt(0): 2, 3, 4, 5. The head is removed.

After RemoveAt(2): 2, 3, 5. The node at index 2 (value 4) is removed.

After RemoveAt(1): 2, 5. The node at index 1 (value 3) is removed.

If your answers differed, trace each call. Pay attention to how the indices shift after each removal.

Building a Complete Program

Here is a program that creates a LinkedList, adds values, queries it, and displays results. Trace through it before reading the output.

LinkedList scores = new LinkedList();
scores.Append(85);
scores.Append(92);
scores.Append(78);
scores.Append(95);
scores.Append(88);
 
scores.Display();
Console.WriteLine("Count: " + scores.Count());
Console.WriteLine("Sum: " + scores.Sum());
Console.WriteLine("Contains 92: " + scores.Contains(92));
Console.WriteLine("Contains 100: " + scores.Contains(100));
 
scores.RemoveFirst();
scores.Display();
 
scores.InsertAt(2, 99);
scores.Display();
 
scores.RemoveAt(1);
scores.Display();

Reveal output

85 92 78 95 88
Count: 5
Sum: 438
Contains 92: True
Contains 100: False
92 78 95 88
92 78 99 95 88
92 99 95 88

After the five Append calls, the chain is 85 → 92 → 78 → 95 → 88 (Append preserves insertion order).

RemoveFirst removes 85. The chain is 92 → 78 → 95 → 88.

InsertAt(2, 99) inserts 99 at index 2, between 78 and 95. The chain is 92 → 78 → 99 → 95 → 88.

RemoveAt(1) removes the node at index 1 (value 78). The chain is 92 → 99 → 95 → 88.

If your predicted output differed, identify which call produced a different result than you expected and trace through that method’s code.

The Full LinkedList Class

Here is the complete class with every method from this section. Use this as a reference when working through the review exercises.

class LinkedListNode
{
    public int Value;
    public LinkedListNode? Next;
 
    public LinkedListNode(int value)
    {
        this.Value = value;
        this.Next = null;
    }
 
    public bool HasNext()
    {
        return this.Next != null;
    }
}
 
class LinkedList
{
    private LinkedListNode? head;
 
    public LinkedList()
    {
        this.head = null;
    }
 
    public void Prepend(int value)
    {
        LinkedListNode newNode = new LinkedListNode(value);
        newNode.Next = this.head;
        this.head = newNode;
    }
 
    public void Append(int value)
    {
        LinkedListNode newNode = new LinkedListNode(value);
        if (this.head == null)
        {
            this.head = newNode;
            return;
        }
        LinkedListNode current = this.head;
        while (current.Next != null)
        {
            current = current.Next;
        }
        current.Next = newNode;
    }
 
    public void Display()
    {
        LinkedListNode? current = this.head;
        while (current != null)
        {
            Console.Write(current.Value + " ");
            current = current.Next;
        }
        Console.WriteLine();
    }
 
    public int Count()
    {
        int count = 0;
        LinkedListNode? current = this.head;
        while (current != null)
        {
            count++;
            current = current.Next;
        }
        return count;
    }
 
    public int Sum()
    {
        int sum = 0;
        LinkedListNode? current = this.head;
        while (current != null)
        {
            sum += current.Value;
            current = current.Next;
        }
        return sum;
    }
 
    public bool Contains(int value)
    {
        LinkedListNode? current = this.head;
        while (current != null)
        {
            if (current.Value == value)
            {
                return true;
            }
            current = current.Next;
        }
        return false;
    }
 
    public void RemoveFirst()
    {
        if (this.head != null)
        {
            this.head = this.head.Next;
        }
    }
 
    public void InsertAt(int index, int value)
    {
        if (index == 0)
        {
            Prepend(value);
            return;
        }
 
        LinkedListNode? current = this.head;
        for (int i = 0; i < index - 1; i++)
        {
            if (current == null)
            {
                return;
            }
            current = current.Next;
        }
 
        if (current == null)
        {
            return;
        }
 
        LinkedListNode newNode = new LinkedListNode(value);
        newNode.Next = current.Next;
        current.Next = newNode;
    }
 
    public void RemoveAt(int index)
    {
        if (this.head == null)
        {
            return;
        }
 
        if (index == 0)
        {
            this.head = this.head.Next;
            return;
        }
 
        LinkedListNode? current = this.head;
        for (int i = 0; i < index - 1; i++)
        {
            if (current.Next == null)
            {
                return;
            }
            current = current.Next;
        }
 
        if (current.Next == null)
        {
            return;
        }
 
        current.Next = current.Next.Next;
    }
}

Review

Before continuing, test yourself on what you have learned. Attempt each exercise from memory, then search this section to check your answers, then note what you missed.

Part 1: Definitions

Write the definitions from memory, then find them in this section to check.

What is encapsulation?

If your answer differed from the definition in this section, note what you missed and write the corrected version.

Review from earlier sections:

What is a linked list?
What is a node?
What does private mean for a member?

Part 2: Translations

Translate each piece of code to English.

scores.Prepend(42);
int n = scores.Count();
bool found = scores.Contains(7);

LinkedListNode? current = this.head;
while (current != null)
{
    Console.WriteLine(current.Value);
    current = current.Next;
}

Check your translations against the patterns shown earlier in this section.

Part 3: Writing Methods

Write each method from the description alone. Do not look at the examples in this section.

Write a method named Max on LinkedList that returns the largest value in the list. You may assume the list has at least one node.
Write a method named CountAbove on LinkedList that takes an integer threshold and returns the number of nodes whose value is greater than threshold.
Write a method named RemoveLast on LinkedList that removes the last node in the chain. If the list has one node, the list becomes empty. If the list is already empty, it does nothing.

Hint for RemoveLast: think about the two special cases (empty list, single node) separately. For the general case, traverse to the node whose Next.Next is null.

Check your code against the patterns in this section.

Part 4: Predict the State

Trace through this code and write the output of each Display call:

LinkedList data = new LinkedList();
data.Append(5);
data.Append(10);
data.Append(15);
data.Append(20);
data.Display();
 
data.RemoveFirst();
data.InsertAt(1, 12);
data.Display();
 
data.RemoveAt(3);
data.Prepend(1);
data.Display();

Part 5: Memory Diagrams

Draw the memory diagram for this code. Show the LinkedList object, its head reference, all nodes, and all Next references.

LinkedList items = new LinkedList();
items.Prepend(30);
items.Prepend(20);
items.Prepend(10);
items.RemoveAt(1);

How many nodes exist in the chain after RemoveAt? What values do they hold? Which node does head point to?

Part 6: Bug Identification

Find and fix the bug in each piece of code.

Bug 1. This traversal is supposed to display every value, but it skips the first one.

public void Display()
{
    LinkedListNode? current = this.head.Next;
    while (current != null)
    {
        Console.Write(current.Value + " ");
        current = current.Next;
    }
    Console.WriteLine();
}

Bug 2. This method is supposed to count the nodes, but it has two problems. On a non-empty list, it returns one less than the correct count. On an empty list, it crashes.

public int Count()
{
    int count = 0;
    LinkedListNode? current = this.head;
    while (current.Next != null)
    {
        count++;
        current = current.Next;
    }
    return count;
}

Bug 3. This method is supposed to append a value, but it crashes when called on an empty list.

public void Append(int value)
{
    LinkedListNode newNode = new LinkedListNode(value);
    LinkedListNode current = this.head;
    while (current.Next != null)
    {
        current = current.Next;
    }
    current.Next = newNode;
}

Search this section for the correct versions to verify your fixes.

Part 7: Encapsulation

Explain why the LinkedList class makes head private. Your answer should address at least two specific problems that would be possible if head were public.

You can now build and manipulate linked lists through a controlled interface. The LinkedList class encapsulates its node chain: outside code interacts through methods, and the methods guarantee the chain stays well-formed. The traversal pattern (a reference that follows Next until null) is the linked list equivalent of the index-based loops from Chapter 3, and every problem pattern you learned there (accumulation, search, tracking) transfers directly.

Next, we give the linked list configurable behavior.

Fundamentals of Computer Science

Explorer

Chapter 4 - Problem Solving with Linked Lists

Problem Solving with Linked Lists

The Traversal Pattern

Standalone Traversal Problems

The LinkedList Wrapper Class

Prepend

Display and Count

Contains

Append

RemoveFirst

Why Encapsulation Matters

InsertAt

RemoveAt

Building a Complete Program

The Full LinkedList Class

Review

Part 1: Definitions

Part 2: Translations

Part 3: Writing Methods

Part 4: Predict the State

Part 5: Memory Diagrams

Part 6: Bug Identification

Part 7: Encapsulation

Table of Contents

Backlinks