A linked list in data structure is a linear collection of elements (called nodes) where each node stores some data and a reference (pointer/link) to the next node instead of sitting in a single contiguous block of memory like an array.

What Is Linked List in Data Structure? (Quick Scoop)

A linked list is like a flexible chain of nodes in memory, where every node knows where the next one is, but the nodes themselves can live anywhere in RAM. This makes inserting and deleting elements much easier than in arrays, especially in the middle of the list.

Core Idea in One Picture (Mentally)

Think of:

  • A node : a small box with two parts:
    • Data (e.g., 10, “A”, a struct, etc.)
* Pointer/link to the next node
  • The head : a special pointer that stores the address of the first node.
  • The last node : its next pointer is NULL, meaning "end of chain".

So the structure is: HEAD → [data | next] → [data | next] → [data | NULL]

Key Properties (Why It’s Different from Arrays)

  • Linear structure : Elements are logically in a sequence.
  • Dynamic size : The list can grow or shrink at runtime by allocating or freeing nodes.
  • Non-contiguous memory : Nodes can be scattered anywhere in memory; links keep the order.
  • Sequential access : You start at head and follow links; you can’t directly jump to the i‑th element in O(1) time.
  • Efficient insertion/deletion : Once you have a pointer to the node, you can insert/delete nearby nodes in O(1) time (no shifting as in arrays).

Basic Types of Linked Lists

  • Singly linked list : Each node has data and next (pointer to next node).
  • Doubly linked list : Each node has data, prev, and next, so you can traverse in both directions.
  • Circular linked list :
    • Singly circular: Last node’s next points back to the first node.
* Doubly circular: Both `next` and `prev` form a circle.

All are variations on the same linked concept: nodes connected by pointers.

Common Operations on Linked List

  1. Traversal
    • Start from head, follow next links, visit each node until NULL.
  1. Insertion
    • At beginning: Create a new node, set its next to current head, update head to new node.
 * At end: Traverse to last node, set its `next` to new node.

 * In middle: Adjust pointers so the new node’s `next` points to the successor, and the predecessor’s `next` points to the new node.
  1. Deletion
    • At beginning: Move head to head->next, free old first node.
 * At end or middle: Find previous node, set its `next` to skip the deleted node, free the node.
  1. Searching
    • Traverse from head and compare data at each node until found or end of list.

Linked List vs Array (Quick HTML Table)

Here’s a clear comparison showing why linked lists matter:

html

<table>
  <thead>
    <tr>
      <th>Feature</th>
      <th>Linked List</th>
      <th>Array</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>Memory layout</td>
      <td>Non-contiguous nodes connected by pointers[web:1][web:5]</td>
      <td>Contiguous block of memory[web:1][web:3]</td>
    </tr>
    <tr>
      <td>Size</td>
      <td>Dynamic; can grow/shrink at runtime[web:3][web:5]</td>
      <td>Usually fixed or expensive to resize[web:1][web:3]</td>
    </tr>
    <tr>
      <td>Access time</td>
      <td>Sequential; O(n) to reach i-th element[web:1][web:5]</td>
      <td>Random access; O(1) to reach i-th element[web:1][web:9]</td>
    </tr>
    <tr>
      <td>Insertion/deletion (middle)</td>
      <td>Efficient after you have the node; adjust pointers[web:1][web:3]</td>
      <td>Costly; requires shifting many elements[web:1]</td>
    </tr>
    <tr>
      <td>Memory overhead</td>
      <td>Extra pointer per node[web:3][web:5]</td>
      <td>No extra links; pure data[web:1]</td>
    </tr>
  </tbody>
</table>

Where Are Linked Lists Used?

  • Implementing stacks, queues, and deques when the size changes frequently.
  • Memory management, schedulers, and OS structures like ready queues and free lists.
  • Dynamic data like playlists, browser history, undo/redo lists where you often insert and delete.
  • Libraries and frameworks (for example, HTTP header lists in cURL are managed as linked lists).

Mini “Story” to Make It Stick

Imagine you’re organizing people in a line for a meetup:

  • With an array , you give everyone fixed numbered seats in one long bench. If you want to insert someone at seat 3, everyone from seat 3 onward must shift one place.
  • With a linked list , each person just holds the hand of the next person. To insert someone in the 3rd position, you break the link between person 2 and 3, put the new person in between, and reconnect hands. No one else needs to move; only the links change.

That “relink instead of move” idea is the heart of what a linked list is in data structures.

Quick TL;DR

  • A linked list is a linear, dynamic data structure made of nodes connected by pointers.
  • Each node stores data plus a link to the next node; the last node points to NULL.
  • It trades fast random access (arrays) for flexible insertion/deletion and dynamic size.

Information gathered from public forums or data available on the internet and portrayed here.