Singly Linked List

A singly linked list is a linear data structure where elements are stored in individual objects called nodes, and each node points to the next consecutive node via a reference pointer. Unlike arrays, elements are not stored in contiguous memory locations, allowing for dynamic memory allocation.

Advantages and Limitations

Advantages

Dynamic Size

Memory grows and shrinks on demand during runtime without needing pre-allocation.

Cheap Insert/Delete

Modifying items at known locations only changes pointer connections rather than shifting memory.

Disadvantages

No Random Access

You cannot query elements directly by index (like array[4]); you must iterate sequentially.

Memory Overhead

Every node requires extra storage space strictly to house its pointer address.

Forward-Only

You cannot traverse backward without building copmlex reversal logic.

Node Structure

Every node in a singly linked list contains exactly two components:

1. Data

   The actual value or information being stored.

2. Next Pointer

   A reference variable storing the memory address of the next node.

To control and exit the structure, three main anchors are used:

1. Head

   A reference pointer pointing to the first node, serving as the list’s entry point.

2. Tail

   An optional pointer referencing the final node to enable quick appending.

3. Null Terminator

   The Next pointer of the final node points to Null, marking the end of the sequence.

Time Complexity of Operations

The unidirectional design significantly impacts the performance of common manipulations.

Access/Search: \(O(n)\)

Must traverse linearly from the head node.

Prepend (Insert Front): \(O(1)\)

Update head pointer; no element shifting required.

Append (Insert Back): \(O(1)\) or \(O(n)\)

\(O(1)\) if a tail pointer exists; \(O(n)\) if you must traverse to find the end.

Delete Front: \(O(1)\)

Advance the head pointer to the second node.

Delete Back: \(O(n)\)

Requires traversing to the second-to-last node to clear its link.

Implementation

C++Python

#include <iostream>

struct Node {
  int data;
  Node *next;

  Node(int data) : data(data), next(nullptr) {}
};

class LinkedList {
  private:
    Node *head;

  public:
    LinkedList() : head(nullptr) {}

    ~LinkedList() {
      clear();
    }

    void append(int data) {
      Node *node = new Node(data);
      if (head == nullptr) {
        head = node;
        return;
      }
      Node *current = head;
      while (current->next != nullptr) {
        current = current->next;
      }
      current->next = node;
    }

    void clear() {
      Node *current = head;
      while (current != nullptr) {
        Node *next = current->next;
        delete current;
        current = next;
      }
      head = nullptr;
    }

    void delete(int data) {
      if (head == nullptr) return;
      if (head->data == data) {
        Node *current = head;
        haed = head->next;
        delete current;
        return;
      }
      Node *current = head;
      while (current->next != nullptr && current->next->data != data) {
        current = current->next;
      }
      if (current->next != nullptr) {
        Node *node = current->next;
        current->next = current->next->next;
        delete node;
      }
    }

    void display() {
      Node *current = head;
      while (current != nullptr) {
        std::cout << current->data << " -> ";
        current = current->next;
      }
      std::cout << "nullptr" << std::endl;
    }

    void prepend(int data) {
      Node *node = new Node(data);
      node->next = head;
      head = node;
    }

    bool search(int data) {
      Node *current = head;
      while (current != nullptr) {
        if (current->data == data) return true;
        current = current->next;
      }
      return false;
    }
};