> For the complete documentation index, see [llms.txt](https://sr-tamim.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sr-tamim.gitbook.io/algorithm/2.data_structures/linked_list.md).

# Linked List

A linked list is a linear data structure where elements are stored in a non-contiguous manner. Each element, known as a node, contains a value and a reference (pointer) to the next node in the sequence. The first node is called the head, and the last node points to null.

## Key Characteristics:

* **Node Structure:** Each node contains a value and a pointer to the next node.
  * **Node Value:** The data stored in the node (e.g., an integer, string).
  * **Next Pointer:** Points to the next node in the sequence.
* **Head Pointer:** Points to the first node in the linked list.
* **Null Termination:** The last node points to null, indicating the end of the list.

![Singly Linked List](https://github.com/user-attachments/assets/fd54c976-b87c-4712-bf49-c36d7c7d80d4)

## Types of Linked Lists:

* **Singly Linked List:** Each node contains a value and a pointer to the next node.
* **Doubly Linked List:** Each node contains a value, a pointer to the next node, and a pointer to the previous node.
* **Circular Linked List:** The last node points back to the first node, forming a circular structure.

## Advantages of Linked Lists:

* **Dynamic Size:** Linked lists can grow or shrink in size without the need to specify the size beforehand.
* **Efficient Insertion/Deletion:** Adding or removing elements is efficient, as it involves changing pointers.
* **Memory Utilization:** Linked lists use memory efficiently by allocating space only when needed.
* **No Memory Wastage:** There is no memory wastage due to fixed-size allocation.
* **Versatility:** Linked lists can be used to implement various data structures like stacks, queues, and graphs.
* **Non-contiguous Memory:** Elements can be stored anywhere in memory, unlike arrays that require contiguous memory.

## Limitations of Linked Lists:

* **No Random Access:** Accessing elements by index is inefficient, as it requires traversing the list from the beginning.
* **Extra Memory:** Each node requires additional memory for the pointer, increasing memory overhead.
* **Complexity:** Implementing linked lists can be more complex than arrays due to pointer manipulation.
* **Traversal Overhead:** Traversing the list to access elements can be slower than arrays.
* **Cache Inefficiency:** Linked lists may not utilize the cache efficiently due to non-contiguous memory access.
* **No Constant Time Operations:** Operations like accessing the middle element or finding the size are not constant time.
* **Memory Fragmentation:** Frequent insertions and deletions can lead to memory fragmentation.

## Use Cases of Linked Lists:

* **Dynamic Data Structures:** Linked lists are used in scenarios where the size of the data structure is not known in advance.
  * **Stack Implementation:** It can be used to implement stack data structures due to efficient insertion and deletion.
  * **Queue Implementation:** It can be used to implement queue data structures due to efficient enqueue and dequeue operations.
* **Complex Data Structures:** Linked lists are used to implement more complex data structures like graphs and trees.
  * **Graph Representation:** Linked lists are used to represent graphs as adjacency lists for efficient traversal.
  * **Tree Data Structures:** Linked lists are used to implement tree data structures like binary trees and binary search trees. Each node contains pointers to child nodes (left and right).
* **File Systems:** Linked lists are used in file systems to maintain the structure of directories and files.
  * **Directory Structure:** Each directory can be represented as a node in a linked list, with pointers to subdirectories and files.
  * **File Allocation Table:** Linked lists are used to manage file allocation tables in file systems for efficient storage management.
* **Implementation of Algorithms:** Linked lists are used in various algorithms like sorting, searching, and graph traversal.
  * **Merge Sort:** Linked lists are used in merge sort algorithms for efficient sorting of elements.
  * **Depth-First Search:** Linked lists are used to represent graphs for depth-first search traversal.
* **Memory Management:** Linked lists are used in memory management systems to allocate and deallocate memory blocks.
  * **Dynamic Memory Allocation:** Linked lists are used to manage memory blocks of varying sizes efficiently.
  * **Garbage Collection:** Linked lists are used to track memory blocks that are no longer in use for garbage collection.

## Summary:

* Linked lists are linear data structures where elements are stored in a non-contiguous manner using pointers.
* They consist of nodes, each containing a value and a pointer to the next node in the sequence.
* Linked lists provide dynamic size, efficient insertion/deletion, and memory utilization advantages.
* They are used in scenarios where the size of the data structure is not known in advance or when efficient insertion/deletion is required.
* Understanding linked lists is essential for implementing more complex data structures and algorithms.

## Example Code:

```cpp
#include <iostream>
using namespace std;

// Node structure for a singly linked list
struct Node {
    int data;
    Node* next;
};

// Function to print the elements of a linked list
void printList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main() {
    // Creating nodes for a linked list
    Node* head = new Node{1, nullptr};
    Node* second = new Node{2, nullptr};
    Node* third = new Node{3, nullptr};

    // Connecting the nodes to form a linked list
    head->next = second;
    second->next = third;

    // Printing the linked list
    printList(head);

    return 0;
}
```

## Additional Resources:

* [Linked List by GeekforGeeks](https://www.geeksforgeeks.org/linked-list-data-structure/)
* [Linked List by w3schools](https://www.w3schools.com/dsa/dsa_theory_linkedlists.php)
* [Linked List Visualization](https://visualgo.net/en/list)