Introduction to Linked Lists

A linked list is a fundamental data structure used in computer science to store collections of data. Unlike arrays, which store data in contiguous memory locations, linked lists consist of nodes that are scattered throughout memory. Each node contains data and a reference (or pointer) to the next node in the sequence, allowing for dynamic memory allocation and efficient insertions and deletions.

Structure of a Linked List

A linked list typically consists of two main components:

Node:
- Each node contains:
  - Data: The value stored in the node (could be an integer, character, or any object).
  - Pointer: A reference to the next node in the list. In a singly linked list, this is a single pointer; in a doubly linked list, there are pointers to both the next and the previous nodes.
Head:
- The first node in the linked list. If the list is empty, the head is usually set to null or None.

Types of Linked Lists

Singly Linked List:
- Each node points to the next node in the list.
- Example:
```
  Head -> [Data | Next] -> [Data | Next] -> [Data | Next] -> null
```
Doubly Linked List:
- Each node contains two pointers: one to the next node and one to the previous node.
- Example:
```
  null <- [Prev | Data | Next] <-> [Prev | Data | Next] <-> [Prev | Data | Next] -> null
```
Circular Linked List:
- The last node points back to the first node, creating a circular structure.
- Can be singly or doubly linked.
- Example:
```
  Head -> [Data | Next] -> [Data | Next] -> [Data | Next] -> Head
```

Advantages of Linked Lists

Dynamic Size: Unlike arrays, linked lists can grow and shrink in size dynamically as elements are added or removed.
Efficient Insertions/Deletions: Inserting or deleting a node can be done in constant time O(1)O(1)O(1) if you have a pointer to the node, without the need for shifting elements like in arrays.

Disadvantages of Linked Lists

Memory Overhead: Each node requires additional memory for storing pointers, which can lead to higher memory consumption compared to arrays.
No Random Access: Accessing an element requires traversing the list from the head, resulting in a time complexity of O(n)O(n)O(n) for searches, compared to O(1)O(1)O(1) for arrays.
Cache Locality: Arrays have better cache performance because their elements are stored in contiguous memory locations, while linked lists do not have this advantage.

Linked List vs. Array

Feature	Linked List	Array
Memory Allocation	Dynamic; nodes can be allocated as needed, scattered in memory.	Static or dynamic; elements stored in contiguous memory locations.
Size	It can grow and shrink dynamically.	Fixed size (in static arrays); must allocate memory upfront.
Access Time	O(n) for accessing an element; must traverse nodes.	O(1) for accessing elements via index.
Insertion/Deletion	O(1) if you have a pointer to the node; otherwise, O(n) for searching.	O(n) for insertion/deletion (due to shifting).
Memory Overhead	Higher due to storage of pointers.	Lower, as only data is stored (no pointers).
Data Structure Type	Non-contiguous, dynamic.	Contiguous, static or dynamic.
Cache Performance	Poor cache performance due to scattered memory.	Better cache performance due to locality.
Use Cases	Ideal for applications where size changes frequently (e.g., queues, stacks).	Suitable for applications needing fast access and fixed size (e.g., lookup tables).