Linked List Data Structure: Introduction Tutorial

What Is a Linked List?

A linked list is a linear data structure where elements are stored in separate objects called nodes. Each node contains data and a reference to another node in the sequence.

Unlike an array, linked-list elements do not need to occupy consecutive memory locations. The links between nodes determine the order of the elements.

[10 | next] → [20 | next] → [30 | next] → null

The first node is called the head. The last node usually points to null, indicating that there are no more nodes in the list.

How a Linked List Is Structured

A basic singly linked-list node contains two important parts:

Data: the value stored in the node.
Next: a reference to the next node.

Node

+-------------+-------------+
|    data     |    next     |
+-------------+-------------+
      10            ↓
                    Node

The next reference is what connects one node to another. This connection creates the logical sequence of the linked list.

A Simple Linked List Example

Consider a linked list containing the values 10, 20, and 30.

head
 ↓
[10 | •] → [20 | •] → [30 | null]

The head reference points to the first node. The first node points to the second node, the second points to the third, and the third points to null.

What Is a Node?

A node is the basic building block of a linked list. In a singly linked list, it stores a value and a reference to the next node.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

const first = new Node(10);
const second = new Node(20);

first.next = second;

console.log(first.value);
// 10

console.log(first.next.value);
// 20

Here, first.next connects the first node to the second node.

What Is the Head of a Linked List?

The head is a reference to the first node in a linked list. It is the starting point for traversing the structure.

head
 ↓
[10] → [20] → [30] → null

If the first node changes, the head reference must also be updated. For an empty linked list, the head is usually null.

What Is the Tail of a Linked List?

The tail represents the final node of a linked list. In a basic singly linked list, the tail's next reference is null.

head                         tail
 ↓                             ↓
[10 | •] → [20 | •] → [30 | null]

Maintaining a separate tail reference can make insertion at the end more efficient, because the last node can be accessed directly.

How Does a Linked List Work?

A linked list works by following references from one node to the next. To access a node that is not directly referenced, the list must normally be traversed from the head.

head
 ↓
10 → 20 → 30 → 40 → null

To reach 40:

head
 ↓
10
 ↓
20
 ↓
30
 ↓
40

This sequential access is one of the most important differences between linked lists and arrays.

Linked List vs Array

Arrays and linked lists are both linear data structures, but they organize and access their elements differently.

Feature	Array	Linked List
Access by index	O(1)	O(n)
Insert at beginning	O(n)	O(1) with head reference
Delete at beginning	O(n) in a typical array	O(1)
Sequential traversal	O(n)	O(n)
Direct random access	Yes	No

Why Use a Linked List?

Linked lists are useful when elements need to be inserted or removed frequently and direct random access is not the primary requirement.

Efficient insertion at the beginning.
Efficient deletion when the required node or its predecessor is already known.
Flexible size without requiring contiguous storage.
Useful as a building block for stacks, queues, and other structures.
Useful for learning pointer and reference-based data structures.

Limitations of Linked Lists

Linked lists also introduce costs that arrays do not have.

Accessing an element by position requires traversal.
Each node requires additional memory for one or more references.
Nodes are less cache-friendly than contiguous array elements in many implementations.
Searching for a value generally takes O(n).
Pointer or reference updates must be handled carefully to avoid losing nodes.

How Do You Traverse a Linked List?

Traversal means visiting each node from the head until the end of the list.

function printList(head) {
  let current = head;

  while (current !== null) {
    console.log(current.value);
    current = current.next;
  }
}

The current reference moves from one node to the next until it reaches null.

Creating a Linked List in JavaScript

JavaScript does not provide a built-in general-purpose linked-list collection, but a linked list can be implemented using classes and object references.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }
}

const list = new LinkedList();

list.head = new Node(10);
list.head.next = new Node(20);
list.head.next.next = new Node(30);

Linked List Insertion

Insertion means adding a new node to the list. The exact complexity depends on where the node is inserted and whether the required position is already known.

Insert at the Beginning

To insert a node at the beginning, make the new node point to the current head and then move the head to the new node.

function insertAtBeginning(head, value) {
  const newNode = new Node(value);

  newNode.next = head;

  return newNode;
}

This operation takes O(1) time.

Insert After a Known Node

If the node after which insertion should occur is already known, the new node can be linked into the list in constant time.

function insertAfter(node, value) {
  if (node === null) {
    return;
  }

  const newNode = new Node(value);

  newNode.next = node.next;
  node.next = newNode;
}

The insertion itself is O(1), but finding the required node first may take O(n).

Linked List Deletion

Deletion removes a node by changing the references around it.

Before:

10 → 20 → 30

Delete 20:

10 ─────────→ 30

In a singly linked list, deleting a node generally requires access to its previous node so that the previous node can skip over the deleted node.

Deleting the First Node

Removing the first node is straightforward: move the head to the second node.

function deleteFirst(head) {
  if (head === null) {
    return null;
  }

  return head.next;
}

The operation takes O(1) time.

Searching a Linked List

Because linked lists do not normally provide direct indexing, searching for a value requires checking nodes sequentially.

function contains(head, target) {
  let current = head;

  while (current !== null) {
    if (current.value === target) {
      return true;
    }

    current = current.next;
  }

  return false;
}

The worst-case time complexity is O(n).

Finding the Length of a Linked List

If the list does not maintain a separate size property, its length can be calculated by traversing every node.

function getLength(head) {
  let length = 0;
  let current = head;

  while (current !== null) {
    length++;
    current = current.next;
  }

  return length;
}

This takes O(n) time. A linked-list implementation can instead maintain a size property and update it whenever nodes are added or removed.

Types of Linked Lists

Linked lists can be classified according to how their nodes reference other nodes. The three common types are singly linked lists, doubly linked lists, and circular linked lists.

Singly Linked List

10 → 20 → 30 → null

Each node contains a reference to only the next node.

Doubly Linked List

null ← 10 ⇄ 20 ⇄ 30 → null

Each node contains references to both the previous and next nodes.

Circular Linked List

10 → 20 → 30
↑           ↓
└───────────┘

In a circular linked list, the final node points back to another node, commonly the head, rather than pointing to null.

Singly vs Doubly Linked List

Feature	Singly	Doubly
Next reference	Yes	Yes
Previous reference	No	Yes
Memory per node	Lower	Higher
Backward traversal	No	Yes

Linked Lists and Memory

Linked-list nodes can be allocated independently. They do not require the complete sequence to occupy one contiguous region of memory.

However, each node needs additional memory for its references. A singly linked list therefore stores both the value and a reference to the next node.

Node 1:
[data | next]

Node 2:
[data | next]

Node 3:
[data | next]

Linked List Operation Complexity

Operation	Typical Complexity	Reason
Access by position	O(n)	Nodes must be traversed
Search	O(n)	Sequential traversal
Insert at head	O(1)	Only head reference changes
Delete at head	O(1)	Move head to next node
Insert after known node	O(1)	References can be updated directly
Delete after known predecessor	O(1)	References can be updated directly

When Should You Use a Linked List?

A linked list can be appropriate when the application performs frequent insertions or deletions at known positions and does not require frequent random access.

Examples include implementing queues, stacks, adjacency structures, and certain memory-management or scheduling structures.

When Is an Array Better?

Arrays are generally more suitable when the application frequently accesses elements by index, benefits from contiguous storage, or needs efficient iteration over a collection.

Need frequent index access?
        ↓
      Array

Need frequent linked insertion/deletion?
        ↓
   Linked List

Need both?
        ↓
Consider the actual access
and update patterns.

Common Linked List Mistakes

Losing the Next Node

When changing references, save the required node before overwriting a reference. Otherwise, the remaining part of the list may become unreachable.

Forgetting the Empty List

Operations should handle the case where head === null.

Confusing Node Access with Insertion Complexity

Inserting after a known node can be O(1), but finding that node by traversing from the head may take O(n).

Creating Accidental Cycles

Incorrectly assigning a next reference can make a list point back to an earlier node. Traversal may then continue indefinitely.

Forgetting to Update the Head

Operations that add or remove the first node must update the head reference.

Linked List Interview Concepts

Linked lists are frequently used in coding interviews because pointer manipulation exposes how well a developer understands references and edge cases.

Reverse a linked list.
Find the middle node.
Detect a cycle.
Merge two sorted linked lists.
Remove the nth node from the end.
Find the intersection of two linked lists.
Determine whether a linked list is a palindrome.
Reverse nodes in groups.

A Simple Linked List Class

The following example combines a node class with a basic linked-list class.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  append(value) {
    const newNode = new Node(value);

    if (this.head === null) {
      this.head = newNode;
      this.size++;
      return;
    }

    let current = this.head;

    while (current.next !== null) {
      current = current.next;
    }

    current.next = newNode;
    this.size++;
  }

  print() {
    const values = [];
    let current = this.head;

    while (current !== null) {
      values.push(current.value);
      current = current.next;
    }

    console.log(values.join(" → "));
  }
}

const list = new LinkedList();

list.append(10);
list.append(20);
list.append(30);

list.print();
// 10 → 20 → 30

Linked List vs Other Linear Data Structures

Structure	Access	Typical Strength
Array	O(1) by index	Fast random access
Singly linked list	O(n)	Simple sequential links and head operations
Doubly linked list	O(n)	Bidirectional traversal and local updates
Stack	Top-based	LIFO operations
Queue	Front/rear-based	FIFO operations

Key Takeaways

A linked list is a linear data structure made of connected nodes.
Each singly linked-list node stores data and a reference to the next node.
The head identifies the first node in the list.
The last node in a normal singly linked list points to null.
Linked lists provide sequential access rather than O(1) random access by index.
Insertion at the head can be performed in O(1) time.
Searching and positional access generally require O(n) traversal.
Singly, doubly, and circular linked lists are common linked-list variants.
Linked lists are useful as building blocks for stacks, queues, and other structures.
Careful reference manipulation is essential when inserting or deleting nodes.

Topics

Linked List Data Structure: Introduction