A linked list is a linear data structure where elements, called nodes, are stored in non-contiguous memory locations. Each node contains data and a reference (pointer) to the next node in the sequence, forming a chain-like structure.
Unlike arrays, linked lists provide efficient O(1) insertion and deletion at the beginning, but require O(n) time for accessing elements by position since traversal from the head is necessary.
Initialize: Enter the number of nodes and click "Initialize" to create a linked list with null values.
Add Node: Enter a position and value, then click "Add" to insert a new node at that position.
Remove Node: Click "Remove" to delete the last node from the linked list.
Visualization: Watch how pointers connect nodes and how they update during insertions and deletions.
Traversal: Follow the arrows from head to tail to understand sequential access in linked lists.
Initialize: Create multiple nodes with default "null" values
Add Node: Insert a new node with a value at a specific position
Remove Node: Delete the last node from the linked list
Access by Index: O(n) - Must traverse from head to reach the nth node.
Search: O(n) - Linear traversal to find a value.
Insert at Head: O(1) - Create node and update head pointer.
Insert at Tail: O(n) without tail pointer; O(1) with tail pointer.
Insert at Position: O(n) - Traverse to position, then O(1) pointer updates.
Delete at Head: O(1) - Update head to next node.
Delete at Position: O(n) - Traverse to find previous node, then O(1) removal.
vs Array: Linked lists have O(1) insertion/deletion at known positions but O(n) access; arrays have O(1) access but O(n) insertion/deletion.
vs Doubly Linked List: Singly linked list uses less memory (one pointer); doubly linked list allows backward traversal and easier deletion.
vs Dynamic Array: Linked list never needs resizing; dynamic array has better cache locality and random access.
vs Stack/Queue: Linked lists are general-purpose; stacks/queues restrict operations but can be implemented with linked lists.
Best Use Case: When you need frequent insertions/deletions, don't know size in advance, or implement stacks/queues with dynamic size.
Music Playlists: Media players use linked lists to navigate between songs, allowing easy insertion and removal of tracks.
Image Viewer: Photo gallery apps use linked lists to navigate through images sequentially with next/previous functionality.
Symbol Tables: Compilers use linked lists in hash table chaining to handle collisions and store identifiers.
Polynomial Representation: Mathematical software represents polynomials as linked lists where each node stores a coefficient and exponent.
File System Allocation: Operating systems use linked allocation to store file blocks scattered across disk with pointers connecting them.
Undo Functionality: Applications can implement undo as a linked list of states, traversing backward through changes.
Process Scheduling: Operating systems maintain linked lists of ready, waiting, and running processes for CPU scheduling.
Sparse Matrices: Large matrices with mostly zero values are efficiently stored as linked lists of non-zero elements.
Fast & Slow Pointers: Detect cycles (Floyd's algorithm), find middle element, or detect nth node from end in single pass.
Reverse Linked List: Iteratively reverse pointers or use recursion; fundamental for many linked list problems.
Merge Two Sorted Lists: Use dummy head and compare nodes; basis for merge sort on linked lists.
Detect & Remove Cycle: Use Floyd's algorithm to detect cycle, then find cycle start by resetting one pointer to head.
Palindrome Check: Find middle, reverse second half, compare with first half, optionally restore.
Add Two Numbers: Traverse both lists simultaneously, track carry, handle different lengths.
Intersection Point: Find length difference, advance longer list, then traverse together until nodes match.
/* Singly linked list operations in C (conceptual) */
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* create_node(int val) {
Node* n = (Node*)malloc(sizeof(Node));
n->data = val;
n->next = NULL;
return n;
}
void insert_at_head(Node** head, int val) {
Node* n = create_node(val);
n->next = *head;
*head = n;
}
void delete_head(Node** head) {
if (!*head) return;
Node* tmp = *head;
*head = (*head)->next;
free(tmp);
}
int main() {
Node* head = NULL;
insert_at_head(&head, 1);
insert_at_head(&head, 2);
delete_head(&head);
// traverse and print
Node* cur = head;
while (cur) { printf("%d ", cur->data); cur = cur->next; }
printf("
");
return 0;
}