Sortedlist And Linkedlist In C# Complete Guide

SortedList and LinkedList in C#: A Comprehensive Guide

1. SortedList

Overview:

• Data Structure: SortedList is a dynamic array that stores a collection of key-value pairs in a sorted order based on the keys.
• Namespace: Defined within System.Collections namespace for non-generic collection, and System.Collections.Generic for generic collection (SortedList<TKey, TValue>).

Key Features:

• Sorted: Elements are always ordered by keys, providing easy access and retrieval.
• Dictionary-like: Supports fast key-based lookup, insertion, and deletion. However, it is typically slower than Dictionary<TKey, TValue> for these operations due to the need to maintain order.
• Index-based Access: Supports both key-based and index-based access to elements.

Performance Characteristics:

• Insertion: Average and worst-case performance for insertion is O(n) because elements might need to be shifted to maintain sorted order.
• Deletion: Deletion is also O(n) due to potential shifting of elements.
• Lookup: Fast lookup with average and worst-case performance of O(log n), owing to the binary search used for finding keys.

Use Cases:

• Ideal when you need to frequently access elements by their sorted order.
• Suitable for scenarios where maintaining a sorted collection of items is crucial for business logic.
• Not ideal for high-frequency insertions and deletions due to their linear time complexity.

Important Members:

• Add(TKey key, TValue value): Adds a key-value pair to the SortedList.
• Remove(TKey key): Removes the element with the specified key.
• ContainsKey(TKey key): Checks if the SortedList contains a specific key.
• Clear(): Removes all elements from the SortedList.

Examples:

Non-Generic SortedList:

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        SortedList mySortedList = new SortedList();
        mySortedList.Add(2, "Two");
        mySortedList.Add(1, "One");
        mySortedList.Add(3, "Three");

        // Output: [1, One] [2, Two] [3, Three]
        foreach (DictionaryEntry entry in mySortedList)
        {
            Console.Write($"[{entry.Key}, {entry.Value}] ");
        }
    }
}

Generic SortedList:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        SortedList<int, string> mySortedList = new SortedList<int, string>();
        mySortedList.Add(2, "Two");
        mySortedList.Add(1, "One");
        mySortedList.Add(3, "Three");

        // Output: [1, One] [2, Two] [3, Three]
        foreach (var entry in mySortedList)
        {
            Console.Write($"[{entry.Key}, {entry.Value}] ");
        }
    }
}

2. LinkedList

Overview:

• Data Structure: LinkedList is a doubly-linked list that stores elements sequentially. Each node in the list contains a reference to both the next and the previous node, facilitating efficient insertion and deletion from any position.
• Namespace: Found in System.Collections.Generic namespace as LinkedList<T>.

Key Features:

• Doubly-Linked: Enables traversal in both forward and reverse directions.
• Dynamic Length: No need to define an initial size; it grows and shrinks dynamically.
• No Indexing: Unlike ArrayList and List<T>, LinkedList does not support random access to elements based on their index.

Performance Characteristics:

• Insertion/Deletion: Average and worst-case performance are O(1) if you already have a reference to the node to be inserted or deleted. Otherwise, you must traverse the list in O(n) to find the node.
• Traversal: Efficient for forward and backward traversal with each step costing O(1).
• Lookup: Accessing elements by index is not supported; lookup based on index is O(n).

Use Cases:

• Ideal for situations where frequent insertions and deletions from any position are required.
• Suitable for creating queues or stacks where elements need to be added or removed from the beginning or end of the collection.
• Use in scenarios where the data needs to be maintained in a certain sequence without the overhead of maintaining a sorted order.

Important Members:

• AddFirst(T value) and AddLast(T value): Adds elements to the beginning or end of the list.
• RemoveFirst() and RemoveLast(): Removes elements from the beginning or end of the list.
• Find(T value): Finds the node that contains the specified value.
• Clear(): Removes all elements from the LinkedList.

Examples:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        LinkedList<string> myLinkedList = new LinkedList<string>();
        myLinkedList.AddFirst("B");
        myLinkedList.AddFirst("A");
        myLinkedList.AddLast("C");

        // Output: A B C
        foreach (string item in myLinkedList)
        {
            Console.Write($"{item} ");
        }

        LinkedListNode<string> node = myLinkedList.Find("B");
        if (node != null)
        {
            myLinkedList.AddAfter(node, "AB");
        }

        // Output: A B AB C
        foreach (string item in myLinkedList)
        {
            Console.Write($"{item} ");
        }
    }
}

Key Differences Between SortedList and LinkedList

| Feature | SortedList | LinkedList | |-------------------------|-------------------------------------------------|---------------------------------------------------| | Data Structure Type | Dynamic Array | Doubly-Linked List | | Sorting | Always sorted by keys | Not sorted | | Index-based Access | Supported | Not supported | | Insertion | O(n) | O(1) if node reference is known, otherwise O(n) | | Deletion | O(n) | O(1) if node reference is known, otherwise O(n) | | Traversal | Less efficient due to lack of direct indexing | Efficient in both forward and backward directions | | Lookup | Fast (O(log n)) | Slow (O(n)) | | Use Case | When maintaining a sorted order is critical | When frequent insertions and deletions occur |

Conclusion

Both SortedList and LinkedList are valuable tools in the C# developer's toolkit, each offering unique advantages suited to specific requirements. SortedList is advantageous when sorted data access is crucial and the cost of frequent insertions and deletions is manageable. Conversely, LinkedList excels in scenarios that demand efficient insertions and deletions from arbitrary positions, making it a preferred choice for implementing queues and stacks. Choosing between them depends on the specific characteristics and performance considerations of your application's data management needs.