How to Implement Linked Lists in C#

To implement linked lists in C#, first define a Node class with data and next (for singly linked lists) or previous (for doubly linked lists) pointers. Then, create a LinkedList class with head and tail nodes. For singly lists, implement methods for insertion, deletion, and traversal, handling scenarios like inserting at various positions. For doubly lists, extend with prev references for bidirectional traversal. Ensure efficient traversal by iterating through nodes. Following these steps yields robust implementations of both singly and doubly linked lists, adept at managing dynamic data structures in C#.

In C#, a linked list is a linear data structure comprised of a sequence of elements, known as nodes, where each node contains a piece of data and a reference, commonly referred to as a pointer, to the next node in the sequence.

Table Of Contents

How Linked List is Different from Array?
Implementing a Singly Linked List
Implementing a Doubly Linked List
Time Complexity of Basic Operations in Linked List
Best and Worst-Case Scenarios

How Linked List is Different from Array?

Unlike arrays, linked lists do not require contiguous memory allocation, enabling dynamic memory management. This structure allows for efficient insertion and deletion operations, making linked lists particularly useful for scenarios where the size of the data structure may vary dynamically. Linked lists can be singly linked, with each node containing a reference to the next node, or doubly linked, with each node containing references to both the next and previous nodes, facilitating bidirectional traversal.

Implementing a Singly Linked List

Node class

Structure of a node:
- In C#, a node in a singly linked list is typically represented as a class with two properties: a data field to store the element, and a next field to store a reference to the next node in the list. Here’s how you can define the structure of a node in C#:

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

    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

In this code snippet, Node<T> represents a generic node class where T is the type of data the node will hold. The Data property holds the actual element, while the Next property is a reference to the next node in the list.

Properties and methods:
- Data: Property to access the data stored in the node.
- Next: Property to access the reference to the next node.
- Node(T data): Constructor to initialize the node with data.

Linked list class

Structure and initialization: The linked list class manages the nodes and operations on the list. Here’s a basic structure for the singly linked list class:

public class SinglyLinkedList<T>
{
    private Node<T> head;

    public SinglyLinkedList()
    {
        head = null;
    }
}

In this code, SinglyLinkedList<T> is a generic class where T represents the type of data stored in the list. The head variable serves as the entry point to the list and is initially set to null to indicate an empty list.

Basic operations:

Insertion:
- Inserting a new node involves updating references to maintain the list’s integrity.

Here’s how you can implement insertion at the Front of the Singly Linked List in C#

Create a new node with the given data.
Set the Next pointer of the new node to point to the current head of the list.
Update the head of the list to point to the new node.

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

Here’s how you can implement insertion at the End of the Singly Linked List in C#

Create a new node with the given data.
If the list is empty, set the head to point to the new node and return.
Traverse the list until the last node.
Set the Next pointer of the last node to point to the new node.

public void InsertAtEnd(T data)
{
    Node<T> newNode = new Node<T>(data);
    if (head == null)
    {
        head = newNode;
        return;
    }
    Node<T> current = head;
    while (current.Next != null)
    {
        current = current.Next;
    }
    current.Next = newNode;
}

Here’s how you can implement insertion After a Given Node of the Singly Linked List in C#

Create a new node with the given data.
Find the node after which you want to insert the new node.
Set the Next pointer of the new node to point to the next node of the given node.
Update the Next pointer of the given node to point to the new node.

public void InsertAfter(Node<T> previousNode, T data)
{
    if (previousNode == null)
    {
        Console.WriteLine("Previous node cannot be null");
        return;
    }
    Node<T> newNode = new Node<T>(data);
    newNode.Next = previousNode.Next;
    previousNode.Next = newNode;
}

Deletion: Deleting a node requires updating references to bypass the node to be deleted.

Here’s a method to delete the first occurrence of a node with a given data value:

Start with the head of the linked list.
If the head itself contains the data to be deleted, update the head to point to the next node and exit.
Traverse the list until the next node’s data matches the given data value or until the end of the list is reached.
If a node with the given data value is found, update the Next pointer of the previous node to skip the node with the given data value.

public void Delete(T data)
{
    if (head == null)
        return;

    if (head.Data.Equals(data))
    {
        head = head.Next;
        return;
    }

    Node<T> current = head;
    while (current.Next != null)
    {
        if (current.Next.Data.Equals(data))
        {
            current.Next = current.Next.Next;
            return;
        }
        current = current.Next;
    }
}

Here’s how you can Delete the node at the front of the Singly Linked List in C#

Check if the linked list is empty. If so, exit the operation.
Update the head of the linked list to point to the next node.
The node originally at the front is now disconnected from the list and will be garbage collected by the CLR.

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

Here’s how you can Delete the node at the end of the Singly Linked List in C#

Check if the linked list is empty or contains only one node. If so, set the head to null and exit the operation.
Traverse the list until the second-to-last node.
Update the Next pointer of the second-to-last node to null, effectively disconnecting the last node from the list.
The last node is now disconnected from the list and will be garbage collected by the CLR.

public void DeleteLast()
{
    if (head == null || head.Next == null)
    {
        head = null;
        return;
    }

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

Searching: Searching involves traversing the list to find a specific data value.

Here’s how you can implement a method to search for a node with a given data value:

public bool Contains(T data)
{
    Node<T> current = head;
    while (current != null)
    {
        if (current.Data.Equals(data))
            return true;
        current = current.Next;
    }
    return false;
}

Traversal: Traversing the list allows accessing each node sequentially.

Here’s a method to Traverse from the beginning to the end in Singly Linked List in C#

public void Print()
{
    Node<T> current = head;
    while (current != null)
    {
        Console.WriteLine(current.Data);
        current = current.Next;
    }
}

These basic operations form the foundation of a singly linked list implementation in C#. They enable efficient manipulation and traversal of the list, empowering developers to work with dynamic collections of data seamlessly.

Implementing a Doubly Linked List

Node class

Node Structure in Doubly Linked List:
- In a doubly linked list, each node needs to maintain references to both the next and previous nodes. Here’s how you can modify the node class to accommodate these changes:

public class DoublyNode<T>
{
    public T Data { get; set; }
    public DoublyNode<T> Next { get; set; }
    public DoublyNode<T> Previous { get; set; }

    public DoublyNode(T data)
    {
        Data = data;
        Next = null;
        Previous = null;
    }
}

In this code, DoublyNode<T> represents a generic node class for a doubly linked list. In addition to the Data property, there are Next and Previous properties to reference the next and previous nodes, respectively.

Linked list class

Structure and initialization: The structure of the doubly linked list class is similar to that of the singly linked list, but with modifications to handle the doubly linked nodes:

public class DoublyLinkedList<T>
{
    private DoublyNode<T> head;

    public DoublyLinkedList()
    {
        head = null;
    }
}

Here, DoublyLinkedList<T> is a generic class representing a doubly linked list. The head variable serves as the entry point to the list, initially set to null for an empty list.

Basic operations:

Insertion: Inserting a node in a doubly linked list requires updating references to maintain both the next and previous pointers.

Here’s how you can implement insertion at the beginning of the Doubly Linked List in C#

Create a new node with the given data.
If the list is empty, set the head to point to the new node and return.
Set the Next pointer of the new node to point to the current head.
Set the Previous pointer of the current head (if it exists) to point to the new node.
Update the head to point to the new node.

public void InsertAtBeginning(T data)
{
    DoublyNode<T> newNode = new DoublyNode<T>(data);
    newNode.Next = head;
    if (head != null)
        head.Previous = newNode;
    head = newNode;
}

Here’s how you can implement insertion at the End of the Doubly Linked List in C#

Create a new node with the given data.
If the list is empty, set the head to point to the new node and return.
Traverse the list until the last node.
Set the Next pointer of the last node to point to the new node.
Set the Previous pointer of the new node to point to the last node.

public void InsertAtEnd(T data)
{
    DoublyNode<T> newNode = new DoublyNode<T>(data);
    if (head == null)
    {
        head = newNode;
        return;
    }
    DoublyNode<T> current = head;
    while (current.Next != null)
    {
        current = current.Next;
    }
    current.Next = newNode;
    newNode.Previous = current;
}

Here’s how you can implement insertion After a Given Node of the Doubly Linked List in C#

Create a new node with the given data.
Find the node after which you want to insert the new node.
Set the Next pointer of the new node to point to the next node of the given node.
Set the Previous pointer of the new node to point to the given node.
Update the Next pointer of the given node to point to the new node.

public void InsertAfter(DoublyNode<T> previousNode, T data)
{
    if (previousNode == null)
    {
        Console.WriteLine("Previous node cannot be null");
        return;
    }
    DoublyNode<T> newNode = new DoublyNode<T>(data);
    newNode.Next = previousNode.Next;
    if (previousNode.Next != null)
        previousNode.Next.Previous = newNode;
    previousNode.Next = newNode;
    newNode.Previous = previousNode;
}

Deletion: Deleting a node in a doubly linked list involves updating references of the neighboring nodes to bypass the node to be deleted.

Here’s a method to delete the first occurrence of a node in Doubly Linked List with a given data value in C#:

Delete the First Occurrence of a Node with a Given Data Value:

Start with the head of the linked list.
If the head itself contains the data to be deleted, update the head to point to the next node and return.
Traverse the list until the next node’s data matches the given data value or until the end of the list is reached.
If a node with the given data value is found, update the Next pointer of the previous node to skip the node with the given data value and update the Previous pointer of the next node to skip the node with the given data value.

public void Delete(T data)
{
    DoublyNode<T> current = head;

    while (current != null)
    {
        if (current.Data.Equals(data))
        {
            if (current.Previous != null)
                current.Previous.Next = current.Next;
            if (current.Next != null)
                current.Next.Previous = current.Previous;
            if (current == head)
                head = current.Next;
            return;
        }
        current = current.Next;
    }
}

Here’s a method to Delete the node at the front in Doubly Linked List in C#:

Check if the linked list is empty. If so, exit the operation.
Update the head of the linked list to point to the next node.
Set the Previous pointer of the new head (if it exists) to null.
The node originally at the front is now disconnected from the list and will be garbage collected by the CLR.

public void DeleteFirst()
{
    if (head != null)
    {
        head = head.Next;
        head.Previous = null;
    }
}

Here’s a method to Delete the node at the end of the Doubly Linked List in C#:

Check if the linked list is empty or contains only one node. If so, set the head to null and return.
Traverse the list until the last node.
Set the Next pointer of the second-to-last node to null, effectively disconnecting the last node from the list.
The last node is now disconnected from the list and will be garbage collected by the CLR.

public void DeleteLast()
{
    if (head == null || head.Next == null)
    {
        head = null;
        return;
    }

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

Searching: Searching in a doubly linked list is similar to that in a singly linked list, but traversal can occur in both forward and backward directions. Here’s how you can implement a method to search for a node with a given data value:

public bool Contains(T data)
{
    DoublyNode<T> current = head;
    while (current != null)
    {
        if (current.Data.Equals(data))
            return true;
        current = current.Next;
    }
    return false;
}

Traversal: Traversing a doubly linked list allows accessing nodes in both forward and backward directions. Here’s a method to traverse and print the elements of the list:

public void Print()
{
    DoublyNode<T> current = head;
    while (current != null)
    {
        Console.WriteLine(current.Data);
        current = current.Next;
    }
}

Traverse the list from the end to the beginning in doubly linked list in C#

public void PrintReverse()
{
    DoublyNode<T> current = head;
    while (current.Next != null)
    {
        current = current.Next;
    }
    while (current != null)
    {
        Console.WriteLine(current.Data);
        current = current.Previous;
    }
}

These basic operations enable efficient manipulation and traversal of a doubly linked list in C#. The doubly linked list offers the advantage of bidirectional traversal, enhancing its versatility in various programming scenarios

Time Complexity of Basic Operations in Linked List

In a linked list, the time complexity of basic operations varies depending on the operation and the position of the target node.

Insertion:
- Beginning: O(1) – Inserting a node at the beginning of a linked list involves updating the head pointer, which takes constant time.
- End: O(n) – Inserting a node at the end requires traversing the entire list to reach the last node, resulting in linear time complexity.
- Middle: O(n) – Inserting a node in the middle of the list also involves traversal, requiring O(n) time in the worst case.
Deletion:
- Beginning: O(1) – Deleting a node from the beginning involves updating the head pointer, which takes constant time.
- End: O(n) – Deleting a node from the end requires traversal to reach the last node, resulting in linear time complexity.
- Middle: O(n) – Deleting a node from the middle of the list also involves traversal, requiring O(n) time in the worst case.
Searching:
- Linear Search: O(n) – Searching for a specific node in a linked list requires traversing the list from the head to the target node, resulting in linear time complexity in the worst case.

Best and Worst-Case Scenarios

Best Case:
- Insertion/Deletion at Beginning: O(1) – In scenarios where insertion or deletion occurs at the beginning of the list, linked lists offer optimal constant-time performance.
- Searching: O(1) – If the target node is found at the beginning of the list, searching can be accomplished in constant time.
Worst Case:
- Insertion/Deletion at End/Middle: O(n) – When insertion or deletion involves traversing the entire list, the time complexity becomes linear.
- Searching: O(n) – If the target node is located at the end of the list or is not present, searching requires traversing the entire list, resulting in linear time complexity.

We provide insightful content and resources to empower developers on their coding journey. If you found this content helpful, be sure to explore more of our materials for in-depth insights into various Programming Concepts.

Also check out(Our Data Structures Series in C#):

Stay tuned for future articles and tutorials that illustrate complex topics, helping you become a more proficient and confident developer.

How Linked List is Different from Array?

Implementing a Singly Linked List

Node class

Linked list class

Implementing a Doubly Linked List

Node class

Linked list class

Time Complexity of Basic Operations in Linked List

Best and Worst-Case Scenarios

Related Posts

How to Implement Middleware Pipeline in ASP.NET Core

How to Implement Serialization and Deserialization in C#

How to Use Common Table Expressions (CTEs) in SQL