Linked Lists in Data Structures

Study Notes

A data structure in which a sequence of nodes are linked together through pointers
Each node contains a value and a reference (i.e., a "link") to the next node in the sequence
Advantages:
- Dynamic memory allocation: nodes can be added or removed as needed
- Efficient insertion and deletion operations
Disadvantages:
- Slow search time (O(n) in the worst case)
- More complex implementation compared to arrays
Types of linked lists:
- Singly linked list: each node only has a reference to the next node
- Doubly linked list: each node has references to both the previous and next nodes
- Circularly linked list: the last node points back to the first node

A First-In-First-Out (FIFO) data structure
Elements are added to the end of the queue (enqueue) and removed from the front of the queue (dequeue)
Operations:
- Enqueue: add an element to the end of the queue
- Dequeue: remove the element from the front of the queue
- Peek: look at the element at the front of the queue without removing it
Types of queues:
- Linear queue: a simple queue with a fixed maximum size
- Circular queue: a queue that wraps around to the beginning when the end is reached
- Priority queue: elements are ordered based on their priority, with the highest-priority element at the front

A linked list is a dynamic data structure where a sequence of nodes are linked together through pointers.
Each node in a linked list contains a value and a reference (or "link") to the next node in the sequence.
Linked lists have advantages, including:
- Dynamic memory allocation, allowing nodes to be added or removed as needed.
- Efficient insertion and deletion operations.
However, linked lists also have disadvantages, including:
- Slow search time, with a worst-case time complexity of O(n).
- More complex implementation compared to arrays.
There are several types of linked lists, including:
- Singly linked lists, where each node only has a reference to the next node.
- Doubly linked lists, where each node has references to both the previous and next nodes.
- Circularly linked lists, where the last node points back to the first node.

A queue is a First-In-First-Out (FIFO) data structure.
Elements are added to the end of the queue (enqueue) and removed from the front of the queue (dequeue).
Queue operations include:
- Enqueue: adding an element to the end of the queue.
- Dequeue: removing the element from the front of the queue.
- Peek: looking at the element at the front of the queue without removing it.
There are several types of queues, including:
- Linear queues, which are simple queues with a fixed maximum size.
- Circular queues, which wrap around to the beginning when the end is reached.
- Priority queues, where elements are ordered based on their priority, with the highest-priority element at the front.