Linked List in C# with Example

A linked list is a fundamental data structure in computer science, widely used in applications where the efficiency of dynamic data operations is crucial. Unlike arrays, linked lists are made up of nodes that are not stored in contiguous memory locations; instead, each node points to the next node in the sequence. This flexibility allows for efficient insertions and deletions. This article explores the implementation and use of linked lists in C#, specifically focusing on the LinkedList<T> class provided by the .NET Framework.

Understanding Linked Lists

A linked list is a collection of elements called nodes, where each node contains a reference to the next node in the list. The primary benefit of linked lists over traditional arrays is their dynamic nature, allowing for efficient insertions and deletions without reallocating the entire structure.

Structure of a Node

In a linked list, each node typically contains:

Value: The data stored in the node.
Next: A reference to the next node in the list.

C# simplifies the implementation of linked lists with the LinkedList<T> class, where T represents the type of elements stored.

Implementing Linked List in C#

LinkedList<T> in the System.Collections.Generic namespace is a doubly linked list, which means each node has references to both the next and the previous nodes. Here's how to implement and utilize a LinkedList<T>:

LinkedList<string> linkedList = new LinkedList<string>();

// Adding elements
linkedList.AddLast("Apple");
linkedList.AddLast("Banana");
linkedList.AddFirst("Mango");

// Traversing the linked list
foreach (var item in linkedList)
{
    Console.WriteLine(item);
}

// Removing elements
linkedList.Remove("Banana");  // Removes Banana from the list

// Adding an element after a known node
LinkedListNode<string> node = linkedList.Find("Mango");
linkedList.AddAfter(node, "Orange");

// Displaying updated list
foreach (var item in linkedList)
{
    Console.WriteLine(item);
}

Basic Operations on Linked Lists

Adding Elements: You can add elements to the beginning (AddFirst), to the end (AddLast), or after/before a specified node (AddAfter, AddBefore).
Removing Elements: Elements can be removed from specific positions, or by directly specifying the value.
Traversal: You can traverse through the linked list using a foreach loop or by manually iterating through the Next references of the nodes.

Advantages of Using Linked Lists

Dynamic Size: The size of a linked list can grow or shrink dynamically, making it more flexible than static data structures like arrays.
Efficient Operations: Insertions and deletions are generally more efficient because they do not require the elements to be contiguous in memory.

Use Cases for Linked Lists

Linked lists are especially useful in applications where:

Insertions and deletions at several points are frequent and critical for performance.
The total number of elements is unknown beforehand, or frequent resizing is needed.

Conclusion

The LinkedList<T> class in C# provides a robust and flexible way to implement linked lists, making it easier to manage collections dynamically with efficient performance. Understanding how to effectively use linked lists is crucial for developers looking to optimize their applications for speed and memory usage.

Linked list in c# with example