Sorted Linked List

Sorted Linked List

A sorted linked list is a variation of a linked list where the nodes are arranged in a sorted order based on their values. Every time a new node is inserted, it is placed in its correct position to maintain the sorted order. This makes it different from a regular linked list, where new elements can be added at any arbitrary position (start, end, or any specific index).

Operations on a Sorted Linked List

1. Insertion: The new node is inserted in the correct position to maintain the sorted order.
2. Traversal: Similar to a regular linked list, traversal happens from the head node to the last node.
3. Deletion: Like a regular linked list, a node can be deleted from the beginning, end, or any position.

C++ Implementation of Sorted Insertion

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

class SortedLinkedList {
    Node* head;

public:
    SortedLinkedList() {
        head = nullptr;
    }

    // Function to insert a node in a sorted manner
    void insertSorted(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = nullptr;

        // If the list is empty or the new value is smaller than the head's data
        if (head == nullptr || head->data >= value) {
            newNode->next = head;
            head = newNode;
        } else {
            Node* current = head;
            // Traverse to find the proper position
            while (current->next != nullptr && current->next->data < value) {
                current = current->next;
            }
            newNode->next = current->next;
            current->next = newNode;
        }
        cout << value << " inserted in sorted list.\n";
    }

    // Function to display the sorted linked list
    void display() {
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "nullptr\n";
    }
};

int main() {
    SortedLinkedList list;
    list.insertSorted(30);
    list.insertSorted(10);
    list.insertSorted(20);
    list.insertSorted(40);
    list.display();
    return 0;
}

Time Complexity of Insertion:

• Best Case: $O(1)$ if the element is inserted at the beginning.
• Worst Case: $O(n)$ if the element is inserted at the end (requires traversing the entire list).

Advantages:

• The list is always sorted, so searching for elements can be more efficient in specific use cases.