> For the complete documentation index, see [llms.txt](https://tanias-workspace.gitbook.io/tanias-little-corner/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tanias-workspace.gitbook.io/tanias-little-corner/data-structures/linked-list.md).

# Linked-List

A linked list is a data structure used in computer science to store a collection of elements, where each element, called a "node," contains two parts:

1. **Data**: The value or data that the node holds.
2. **Pointer (or Reference)**: A link to the next node in the sequence.

Unlike arrays, where elements are stored in contiguous memory locations, the nodes in a linked list can be scattered in memory, with each node pointing to the next one in the sequence. This allows for efficient insertion and deletion of elements, as it doesn't require shifting other elements like in an array.

#### Types of Linked Lists

1. **Singly Linked List**:
   * Each node points to the next node in the list.
   * The last node points to `null` (or `nullptr` in C++), indicating the end of the list.
2. **Doubly Linked List**:
   * Each node has two pointers: one pointing to the next node and another pointing to the previous node.
   * This allows traversal in both directions (forward and backward).
3. **Circular Linked List**:
   * The last node points back to the first node, forming a loop.
   * This can be either singly or doubly linked.

<figure><img src="/files/92pWzTCchNpBUeSyKmgE" alt=""><figcaption></figcaption></figure>

## Basic Operations (Singly Linked List in C++)

* **Insertion**: Add a new node at the beginning, end, or any position in the list.
* **Deletion**: Remove a node from the list.
* **Traversal**: Visit each node in the list to access its data.
* **Searching**: Find a node containing a specific value.

<figure><img src="/files/CLCbGbUGcoUlrRJw1uZX" alt=""><figcaption></figcaption></figure>

## Advantages

* Dynamic size: Can grow and shrink in size as needed.
* Efficient insertions/deletions: O(1) time complexity for adding or removing elements at the beginning.

## Disadvantages

* No direct access: Unlike arrays, accessing an element requires traversing the list.
* Extra memory: Requires additional memory for storing pointers.