LinkedList usage in C Sharp (C#)

Introduction

A linked list helps you store items in order, where each item points to the next one. It is useful when you want to add or remove items easily without moving everything.

When you want to add or remove items from the middle of a list quickly.

When you do not know the total number of items in advance.

When you want to keep items in order but expect frequent changes.

When you want to avoid the cost of shifting items in an array.

When you want to traverse items one by one in sequence.

Syntax

C Sharp (C#)

public class Node<T>
{
    public T Value { get; set; }
    public Node<T>? Next { get; set; }

    public Node(T value)
    {
        Value = value;
        Next = null;
    }
}

public class LinkedList<T>
{
    private Node<T>? head;

    public LinkedList()
    {
        head = null;
    }

    public void AddFirst(T value)
    {
        Node<T> newNode = new Node<T>(value);
        newNode.Next = head;
        head = newNode;
    }

    public void AddLast(T value)
    {
        Node<T> newNode = new Node<T>(value);
        if (head == null)
        {
            head = newNode;
            return;
        }

        Node<T> current = head;
        while (current.Next != null)
        {
            current = current.Next;
        }
        current.Next = newNode;
    }

    public bool Remove(T value)
    {
        if (head == null) return false;

        if (head.Value!.Equals(value))
        {
            head = head.Next;
            return true;
        }

        Node<T>? current = head;
        while (current.Next != null && !current.Next.Value!.Equals(value))
        {
            current = current.Next;
        }

        if (current.Next == null) return false;

        current.Next = current.Next.Next;
        return true;
    }

    public void PrintAll()
    {
        Node<T>? current = head;
        while (current != null)
        {
            Console.Write(current.Value + " ");
            current = current.Next;
        }
        Console.WriteLine();
    }
}

The Node<T> class holds the value and a reference to the next node.

The LinkedList<T> class manages the nodes starting from head.

Examples

This shows an empty linked list with no items.

C Sharp (C#)

// Empty list
LinkedList<int> emptyList = new LinkedList<int>();
emptyList.PrintAll(); // prints nothing

Adding one item at the start creates a list with one node.

C Sharp (C#)

// One element
LinkedList<string> singleItemList = new LinkedList<string>();
singleItemList.AddFirst("Hello");
singleItemList.PrintAll(); // prints: Hello

Adding items at the end appends nodes after the last one.

C Sharp (C#)

// Add at end
LinkedList<int> numbers = new LinkedList<int>();
numbers.AddFirst(1);
numbers.AddLast(2);
numbers.AddLast(3);
numbers.PrintAll(); // prints: 1 2 3

Removing a node with value 20 deletes it from the list.

C Sharp (C#)

// Remove element
LinkedList<int> list = new LinkedList<int>();
list.AddLast(10);
list.AddLast(20);
list.AddLast(30);
list.Remove(20);
list.PrintAll(); // prints: 10 30

Sample Program

This program creates a linked list of integers. It shows the list when empty, adds items at the start and end, removes an item, and tries to remove a non-existing item. It prints the list after each step.

C Sharp (C#)

using System;

public class Node<T>
{
    public T Value { get; set; }
    public Node<T>? Next { get; set; }

    public Node(T value)
    {
        Value = value;
        Next = null;
    }
}

public class LinkedList<T>
{
    private Node<T>? head;

    public LinkedList()
    {
        head = null;
    }

    public void AddFirst(T value)
    {
        Node<T> newNode = new Node<T>(value);
        newNode.Next = head;
        head = newNode;
    }

    public void AddLast(T value)
    {
        Node<T> newNode = new Node<T>(value);
        if (head == null)
        {
            head = newNode;
            return;
        }

        Node<T> current = head;
        while (current.Next != null)
        {
            current = current.Next;
        }
        current.Next = newNode;
    }

    public bool Remove(T value)
    {
        if (head == null) return false;

        if (head.Value!.Equals(value))
        {
            head = head.Next;
            return true;
        }

        Node<T>? current = head;
        while (current.Next != null && !current.Next.Value!.Equals(value))
        {
            current = current.Next;
        }

        if (current.Next == null) return false;

        current.Next = current.Next.Next;
        return true;
    }

    public void PrintAll()
    {
        Node<T>? current = head;
        while (current != null)
        {
            Console.Write(current.Value + " ");
            current = current.Next;
        }
        Console.WriteLine();
    }
}

class Program
{
    static void Main()
    {
        LinkedList<int> numbers = new LinkedList<int>();

        Console.WriteLine("Initial list (empty):");
        numbers.PrintAll();

        numbers.AddFirst(5);
        numbers.AddLast(10);
        numbers.AddLast(15);

        Console.WriteLine("After adding 5 at start, then 10 and 15 at end:");
        numbers.PrintAll();

        bool removed = numbers.Remove(10);
        Console.WriteLine($"Removing 10: {removed}");
        numbers.PrintAll();

        removed = numbers.Remove(100);
        Console.WriteLine($"Trying to remove 100 (not in list): {removed}");
        numbers.PrintAll();
    }
}

Important Notes

Adding or removing at the start is very fast (constant time).

Adding at the end takes time proportional to the list length (linear time) if no tail pointer is used.

Removing requires searching, which takes linear time.

Common mistake: forgetting to update the head when removing the first node.

Use linked lists when you need fast insertions/removals and don't need fast random access.

Summary

A linked list stores items in nodes linked by references.

You can add items at the start or end, and remove items by value.

Linked lists are good for dynamic collections with frequent changes.

Practice

1. What is a key characteristic of a LinkedList in C#?

easy

A. It stores elements in nodes linked by references.

B. It stores elements in a fixed-size array.

C. It only allows adding elements at the end.

D. It cannot remove elements once added.

Solution

1. Step 1: Understand LinkedList structure

   A LinkedList stores elements in nodes, where each node points to the next (and possibly previous) node.

2. Step 2: Compare options with LinkedList behavior

   Only It stores elements in nodes linked by references. correctly describes this linked node structure; others describe arrays or incorrect behaviors.

3. Final Answer:

   It stores elements in nodes linked by references. -> Option A

4. Quick Check:

   LinkedList = nodes linked by references [OK]

Hint: LinkedList uses nodes connected by links, not arrays. [OK]

Common Mistakes:

• Thinking LinkedList uses arrays internally
• Assuming LinkedList only adds at the end
• Believing LinkedList cannot remove elements

2. Which of the following is the correct way to add an element at the start of a LinkedList<int> named list?

easy

A. list.AddStart(10);

B. list.AddFirst(10);

C. list.InsertAt(0, 10);

D. list.PushFront(10);

Solution

1. Step 1: Recall LinkedList method names

   The method to add an element at the start is AddFirst.

2. Step 2: Check each option's validity

   Only AddFirst is a valid LinkedList method; others are invalid or do not exist.

3. Final Answer:

   list.AddFirst(10); -> Option B

4. Quick Check:

   AddFirst adds at start [OK]

Hint: Use AddFirst to add at the start of LinkedList. [OK]

Common Mistakes:

• Using non-existent methods like AddStart or PushFront
• Confusing LinkedList with List methods
• Trying to use InsertAt which LinkedList does not have

3. What will be the output of this C# code?

var list = new LinkedList<string>();
list.AddLast("apple");
list.AddFirst("banana");
list.AddLast("cherry");
foreach(var item in list) Console.Write(item + " ");

medium

A. banana apple cherry

B. apple banana cherry

C. cherry apple banana

D. banana cherry apple

Solution

1. Step 1: Track insertion order

   First, "apple" is added last, so list: apple. Then "banana" added first, so list: banana, apple. Then "cherry" added last, so list: banana, apple, cherry.

2. Step 2: Understand foreach iteration order

   Foreach iterates from first to last node, so output is "banana apple cherry ".

3. Final Answer:

   banana apple cherry -> Option A

4. Quick Check:

   First = banana, last = cherry [OK]

Hint: AddFirst puts item at start; AddLast at end. [OK]

Common Mistakes:

• Assuming AddLast adds at start
• Confusing order of AddFirst and AddLast
• Expecting output in reverse order

4. Identify the error in this code snippet:

var list = new LinkedList<int>();
list.AddFirst(1);
list.AddLast(2);
list.Remove(3);
Console.WriteLine(list.Count);

medium

A. Remove(3) throws an exception because 3 is not in the list.

B. Count property does not exist on LinkedList.

C. AddFirst and AddLast methods are invalid for LinkedList.

D. Remove(3) does nothing since 3 is not found; Count remains 2.

Solution

1. Step 1: Understand Remove behavior

   Remove(value) tries to remove the first node with that value. If not found, it does nothing and returns false; no exception is thrown.

2. Step 2: Check Count after removal attempt

   Since 3 is not in the list, list remains with 2 elements; Count is 2.

3. Final Answer:

   Remove(3) does nothing since 3 is not found; Count remains 2. -> Option D

4. Quick Check:

   Remove missing value = no error, Count unchanged [OK]

Hint: Remove missing item does not throw error, just returns false. [OK]

Common Mistakes:

• Expecting Remove to throw exception if item missing
• Thinking AddFirst/AddLast are invalid
• Assuming Count is not a property

5. Given a LinkedList<int> with values 1, 2, 3, 4, 5, which code snippet correctly removes all even numbers from the list?

hard

A. foreach(var node in list) { if(node % 2 == 0) list.Remove(node); }

B. for(int i = 0; i < list.Count; i++) { if(list.ElementAt(i) % 2 == 0) list.Remove(list.ElementAt(i)); }

C. var current = list.First; while(current != null) { var next = current.Next; if(current.Value % 2 == 0) list.Remove(current); current = next; }

D. list.RemoveAll(x => x % 2 == 0);

Solution

1. Step 1: Understand safe removal during iteration

   Removing nodes while iterating requires storing next node before removal to avoid invalid references.

2. Step 2: Analyze each option

   foreach(var node in list) { if(node % 2 == 0) list.Remove(node); } uses foreach which throws error on modification during iteration. var current = list.First; while(current != null) { var next = current.Next; if(current.Value % 2 == 0) list.Remove(current); current = next; } correctly uses a while loop with next node saved. for(int i = 0; i < list.Count; i++) { if(list.ElementAt(i) % 2 == 0) list.Remove(list.ElementAt(i)); } uses ElementAt which is inefficient and unsafe. list.RemoveAll(x => x % 2 == 0); is invalid as LinkedList has no RemoveAll method.

3. Final Answer:

   var current = list.First; while(current != null) { var next = current.Next; if(current.Value % 2 == 0) list.Remove(current); current = next; } -> Option C

4. Quick Check:

   Use while loop with next saved to remove nodes safely [OK]

Hint: Save next node before removal to avoid iteration errors. [OK]

Common Mistakes:

• Modifying list inside foreach causes runtime error
• Using RemoveAll which LinkedList does not have
• Using ElementAt which is inefficient and unsafe