C# singly linked list implementation
Categories:
Implementing a Singly Linked List in C#
Explore the fundamentals of singly linked lists in C#, including node structure, common operations like insertion and deletion, and practical implementation details.
A singly linked list is a fundamental data structure consisting of a sequence of nodes, where each node contains data and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations, offering dynamic resizing and efficient insertions/deletions at specific points, provided you have a reference to the preceding node. This article will guide you through implementing a basic singly linked list in C#.
Understanding the Node Structure
The building block of any linked list is the Node. In a singly linked list, each node needs to store the actual data and a pointer to the next node. The last node in the list will have its Next pointer set to null.
public class Node<T>
{
public T Data { get; set; }
public Node<T> Next { get; set; }
public Node(T data)
{
Data = data;
Next = null;
}
}
The basic Node class for a singly linked list.
<T>) for the Node class makes your linked list implementation flexible, allowing it to store any data type (e.g., int, string, custom objects) without modification.Implementing the SinglyLinkedList Class
The SinglyLinkedList class will manage the collection of nodes. It typically holds a reference to the Head (the first node) of the list. If the list is empty, Head will be null. We'll implement common operations like adding elements, removing elements, and traversing the list.
public class SinglyLinkedList<T>
{
public Node<T> Head { get; private set; }
public int Count { get; private set; }
public SinglyLinkedList()
{
Head = null;
Count = 0;
}
// Add a new node to the end of the list
public void Add(T data)
{
Node<T> newNode = new Node<T>(data);
if (Head == null)
{
Head = newNode;
}
else
{
Node<T> current = Head;
while (current.Next != null)
{
current = current.Next;
}
current.Next = newNode;
}
Count++;
}
// Remove the first occurrence of a node with the specified data
public bool Remove(T data)
{
if (Head == null) return false; // List is empty
if (Head.Data.Equals(data))
{
Head = Head.Next;
Count--;
return true;
}
Node<T> current = Head;
while (current.Next != null && !current.Next.Data.Equals(data))
{
current = current.Next;
}
if (current.Next != null) // Found the node to remove
{
current.Next = current.Next.Next;
Count--;
return true;
}
return false; // Data not found
}
// Find a node by its data
public Node<T> Find(T data)
{
Node<T> current = Head;
while (current != null)
{
if (current.Data.Equals(data))
{
return current;
}
current = current.Next;
}
return null; // Data not found
}
// Display all elements in the list
public void Display()
{
Node<T> current = Head;
if (current == null)
{
Console.WriteLine("List is empty.");
return;
}
Console.Write("List: ");
while (current != null)
{
Console.Write($"{current.Data} -> ");
current = current.Next;
}
Console.WriteLine("null");
}
}
The SinglyLinkedList class with basic operations.
flowchart TD
subgraph Singly Linked List Operations
A[Start] --> B{Is Head null?}
B -- Yes --> C[New node becomes Head]
B -- No --> D[Traverse to last node]
D --> E[Last node's Next points to new node]
C & E --> F[Increment Count]
F --> G[End Add]
H[Start Remove] --> I{Is Head null?}
I -- Yes --> J[Return false]
I -- No --> K{Is Head data target?}
K -- Yes --> L[Head becomes Head.Next]
K -- No --> M[Traverse to node before target]
M --> N{Target found?}
N -- Yes --> O[Node before target's Next skips target]
N -- No --> P[Return false]
L & O --> Q[Decrement Count]
Q --> R[Return true]
J & P & R --> S[End Remove]
endFlowchart of Add and Remove operations in a Singly Linked List.
Using the Singly Linked List
Once the SinglyLinkedList class is implemented, you can create instances of it and perform operations. Here's an example of how to use the list in a Main method.
public class Program
{
public static void Main(string[] args)
{
SinglyLinkedList<int> myIntList = new SinglyLinkedList<int>();
Console.WriteLine("Adding elements:");
myIntList.Add(10);
myIntList.Add(20);
myIntList.Add(30);
myIntList.Add(40);
myIntList.Display(); // Output: List: 10 -> 20 -> 30 -> 40 -> null
Console.WriteLine($"Count: {myIntList.Count}"); // Output: Count: 4
Console.WriteLine("\nRemoving 20:");
myIntList.Remove(20);
myIntList.Display(); // Output: List: 10 -> 30 -> 40 -> null
Console.WriteLine($"Count: {myIntList.Count}"); // Output: Count: 3
Console.WriteLine("\nRemoving 10 (Head):");
myIntList.Remove(10);
myIntList.Display(); // Output: List: 30 -> 40 -> null
Console.WriteLine($"Count: {myIntList.Count}"); // Output: Count: 2
Console.WriteLine("\nFinding 30:");
Node<int> foundNode = myIntList.Find(30);
if (foundNode != null)
{
Console.WriteLine($"Found: {foundNode.Data}"); // Output: Found: 30
}
else
{
Console.WriteLine("30 not found.");
}
Console.WriteLine("\nRemoving non-existent element 50:");
myIntList.Remove(50);
myIntList.Display(); // Output: List: 30 -> 40 -> null
Console.WriteLine($"Count: {myIntList.Count}"); // Output: Count: 2
Console.WriteLine("\nRemoving 40 (Last element):");
myIntList.Remove(40);
myIntList.Display(); // Output: List: 30 -> null
Console.WriteLine($"Count: {myIntList.Count}"); // Output: Count: 1
Console.WriteLine("\nRemoving 30 (Last element):");
myIntList.Remove(30);
myIntList.Display(); // Output: List is empty.
Console.WriteLine($"Count: {myIntList.Count}"); // Output: Count: 0
}
}
Example usage of the SinglyLinkedList class.
System.Collections.Generic.LinkedList<T> provides a more robust and optimized doubly linked list implementation for production use cases.