singly linked list in c#

Singly Linked List in C#

A singly linked list is a fundamental data structure in computer science, often used in various programming scenarios where a dynamic data collection is needed. Unlike arrays or List<T> in C#, singly linked lists store elements in a non-contiguous fashion, providing efficient insertions and deletions. This article explains the concept of a singly linked list in C#, including how to implement one and typical operations such as adding, removing, and traversing nodes.

Understanding Singly Linked Lists

A singly linked list consists of a series of nodes, where each node contains a data part and a reference to the next node in the sequence. This structure allows for efficient insertion and deletion of nodes without reallocating or reorganizing the entire data structure.

Structure of a Node

Each node in a singly linked list contains at least two parts:

• Data: The actual data stored in the node.
• Next: A reference (or link) to the next node in the list.

Here’s a simple class definition for a node in C#:

public class ListNode
{
    public int Data { get; set; }
    public ListNode Next { get; set; }

    public ListNode(int data)
    {
        this.Data = data;
        this.Next = null;
    }
}

Implementing a Singly Linked List

The singly linked list itself needs to manage the nodes. It typically keeps a reference to the first node (head). Here's how you might implement a basic singly linked list:

public class SinglyLinkedList
{
    public ListNode Head { get; private set; }

    public void AddFirst(int data)
    {
        ListNode newNode = new ListNode(data);
        newNode.Next = Head;
        Head = newNode;
    }

    public void AddLast(int data)
    {
        ListNode newNode = new ListNode(data);
        if (Head == null)
        {
            Head = newNode;
        }
        else
        {
            ListNode current = Head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }
    }

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

    public void PrintAll()
    {
        ListNode current = Head;
        while (current != null)
        {
            Console.WriteLine(current.Data);
            current = current.Next;
        }
    }
}

Basic Operations on Singly Linked List

• Adding Elements: You can add elements at the beginning or the end of the list. Adding at the beginning is an O(1) operation, while adding at the end is O(n) since it requires traversing the whole list.
• Removing Elements: Similar to adding, you can remove from the beginning efficiently. Removing from the end or from the middle requires traversal.
• Traversal: To access or display all the elements, you traverse from the head to the end of the list.

Use Cases for Singly Linked Lists

Singly linked lists are particularly useful in scenarios where:

• Dynamic data storage is needed.
• Operations require frequent addition and removal of elements.
• Memory efficiency is a concern (no pre-allocation like arrays).

Conclusion

Understanding and implementing singly linked lists in C# can significantly help in situations where data structures with dynamic sizes are required, providing a flexible and efficient alternative to traditional arrays and generic lists.