Home › DSA › Foundations

Linked List

A Linked List is a data structure where each element (node) contains a value and a reference (or link) to the next node in the sequence. Linked lists are dynamic and can grow or shrink easily by adding or removing nodes. Let’s explore the time and space complexities for common linked list operations.

Basic Operations on Linked List

java

class Node {

  int data;
  Node next;

  public Node(int data) {
    this.data = data;
    this.next = null;
  }
}

public class Solution {

  private Node head;

  // Insert at the end (O(n))
  public void insertAtEnd(int data) {
    Node newNode = new Node(data);
    if (head == null) {
      head = newNode;
      return;
    }
    Node current = head;
    while (current.next != null) {
      current = current.next;
    }
    current.next = newNode;
  }

  // Insert at the start (O(1))
  public void insertAtStart(int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    head = newNode;
  }

  // Search for an element (O(n))
  public boolean search(int target) {
    Node current = head;
    int index = 0;
    while (current != null) {
      if (current.data == target) {
        System.out.println("Element " + target + " found at index " + index);
        return true;
      }
      current = current.next;
      index++;
    }
    System.out.println("Element " + target + " not found.");
    return false;
  }

  // Delete from the start (O(1))
  public void deleteFromStart() {
    if (head != null) {
      head = head.next;
    }
  }

  // Delete from the end (O(n))
  public void deleteFromEnd() {
    if (head == null) return; // List is empty
    if (head.next == null) { // Only one element in the list
      head = null;
      return;
    }
    Node current = head;
    while (current.next.next != null) {
      current = current.next;
    }
    current.next = null; // Remove the last node
  }

  // Print the linked list (O(n))
  public void printList() {
    Node current = head;
    while (current != null) {
      System.out.print(current.data + " -> ");
      current = current.next;
    }
    System.out.println("null");
  }

  public static void main(String[] args) {
    Solution list = new Solution();

    // Insert at the end
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    System.out.println("List after inserting elements at the end:");
    list.printList();

    // Insert at the start
    list.insertAtStart(5);
    System.out.println("List after inserting element at the start:");
    list.printList();

    // Search for an element
    list.search(20);

    // Delete from the start
    list.deleteFromStart();
    System.out.println("List after deleting element from the start:");
    list.printList();

    // Delete from the end
    list.deleteFromEnd();
    System.out.println("List after deleting element from the end:");
    list.printList();
  }
}

Time Complexity Analysis for Linked List Operations

Access Element: – Traversing each node from the head is necessary to reach a specific node.
Insertion:
- Beginning: – Adding a node to the head is immediate.
- End: – Reaching and inserting after the last node takes linear time.
- Middle: – Requires traversal to the desired position.
Deletion:
- Beginning: – Removing the head node is efficient.
- End: – Reaching and removing the last node takes time.
- Middle: – Requires traversal to reach the node to delete.
Searching: – Each node might need checking to find a specific value.
Sorting: - It takes time, same as array

Space Complexity for Linked Lists

The space complexity for a linked list depends on the number of nodes. Each node stores:

Data: The actual value of the element.
Pointer: A reference to the next node (or in doubly linked lists, pointers to both the next and previous nodes).

Space Complexity: , where n is the number of nodes in the linked list. Each node requires constant space, making the overall space proportional to the list’s length.

Array Vs. Dynamic Array Vs. Linked List

Operation	Static Array	Dynamic Array
Access by Index
Insertion (end)	(fixed size)	Average , Worst
Insertion (beginning)
Insertion (middle)
Deletion (end)
Deletion (beginning)
Deletion (middle)
Searching
Space Complexity		(with resizing overhead)

🤖 Don't fully get this? Learn it with Claude

Stuck on Linked List? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Linked List** (DSA) and want to truly understand it. Explain Linked List from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Linked List** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Linked List** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Linked List** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Array Hash Table and Set →