Linked Lists vs. Arrays

Study Notes

Linked lists are linear data structures; they are like arrays, but they represent data in a different way
Arrays are a common data structure, but have limitations. Linked Lists are an alternative that overcomes some of these limitations.

Fixed size: Arrays have a predetermined size that's difficult or impossible to change during program execution
Memory Allocation: Arrays need to be allocated a specific block of contiguous memory, which may limit efficiency
Insertion/Deletion: Inserting or deleting elements can be slow as the whole array may need to be adjusted.
Storage: Arrays are required to store data in a contiguous block of memory
Joining/Splitting: Joining and splitting arrays can be complicated and computationally demanding

A linked list is a linear series of nodes where each node contains data and a link (pointer) to the next node.
Nodes are not necessarily stored together or contiguously in memory
Each node stores data, and a pointer to the next node in the list.

Dynamic Size: Linked lists can grow or shrink as needed at runtime
Efficient Memory Use: Memory is allocated on demand.
Fast Insertion/Deletion: Inserting or deleting elements is generally faster than in arrays.
Flexible Storage: Elements don't have to be stored contiguously, potentially improving memory efficiency.
Easy Joining/Splitting: Joining and splitting linked lists are simple compared to arrays.

A singly linked list consists of nodes, where each node holds data and a pointer to the next node.
The last node's "next" pointer points to NULL.
Accessing nodes requires traversal from the first node.

Singly Linked List: Each node points only to the next node.
Circular Linked List: The last node's "next" pointer points back to the first node.
Doubly Linked List: Each node contains two pointers: one to the next node and one to the previous node.
Circular Doubly Linked List: A doubly linked list where the last node points back to the first, and the first node points to the last.

Creating a linked list: Initialising a list structure and assigning it to a variable
Traversing/Display: Moving through the list, node by node, and printing each node's data
Insertion: Adding a new node at the beginning, middle, or end of the list
Deletion: Removing a node from the beginning, middle, or end of the list
Searching: Finding a node with a specific value
Reversing a linked list: Reversing the sequence of nodes in a linked list
Merging of linked lists: Combining two or more linked lists into one.