A linked list is a dynamic data structure where each element (called a node) contains data and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory - nodes can be scattered anywhere in the heap.
| Feature | Array | Linked List |
|---|---|---|
| Memory | Contiguous, fixed size | Dynamic, scattered |
| Access by index | O(1) - direct | O(n) - traverse |
| Insert at beginning | O(n) - shift elements | O(1) |
| Insert at end | O(1) (if space) | O(n) or O(1) with tail pointer |
| Delete | O(n) - shift elements | O(1) with pointer to node |
| Memory overhead | None | Extra pointer per node |
Each node has data and a next pointer. The last node's next is NULL.
#include <stdio.h>
#include <stdlib.h>
// Node structure
typedef struct Node {
int data;
struct Node *next;
} Node;
// Create a new node
Node* createNode(int data) {
Node *node = (Node*)malloc(sizeof(Node));
if (!node) { perror("malloc"); exit(1); }
node->data = data;
node->next = NULL;
return node;
}
// Insert at beginning - O(1)
Node* insertFront(Node *head, int data) {
Node *node = createNode(data);
node->next = head;
return node; // new head
}
// Insert at end - O(n)
Node* insertEnd(Node *head, int data) {
Node *node = createNode(data);
if (!head) return node;
Node *curr = head;
while (curr->next) curr = curr->next;
curr->next = node;
return head;
}
// Delete a node by value - O(n)
Node* deleteNode(Node *head, int data) {
if (!head) return NULL;
if (head->data == data) {
Node *temp = head->next;
free(head);
return temp;
}
Node *curr = head;
while (curr->next && curr->next->data != data)
curr = curr->next;
if (curr->next) {
Node *temp = curr->next;
curr->next = temp->next;
free(temp);
}
return head;
}
// Search - O(n)
int search(Node *head, int data) {
int pos = 0;
while (head) {
if (head->data == data) return pos;
head = head->next;
pos++;
}
return -1;
}
// Print the list
void printList(Node *head) {
while (head) {
printf("%d", head->data);
if (head->next) printf(" -> ");
head = head->next;
}
printf(" -> NULL\n");
}
// Free all nodes
void freeList(Node *head) {
while (head) {
Node *temp = head;
head = head->next;
free(temp);
}
}
int main() {
Node *head = NULL;
head = insertEnd(head, 10);
head = insertEnd(head, 20);
head = insertEnd(head, 30);
head = insertFront(head, 5);
printf("List: "); printList(head);
// 5 -> 10 -> 20 -> 30 -> NULL
head = deleteNode(head, 20);
printf("After deleting 20: "); printList(head);
// 5 -> 10 -> 30 -> NULL
printf("Search 30: position %d\n", search(head, 30)); // 2
printf("Search 99: position %d\n", search(head, 99)); // -1
freeList(head);
return 0;
}Each node has both a next and a prev pointer. This allows traversal in both directions and O(1) deletion when you have a pointer to the node.
#include <stdio.h>
#include <stdlib.h>
typedef struct DNode {
int data;
struct DNode *prev;
struct DNode *next;
} DNode;
DNode* createDNode(int data) {
DNode *node = (DNode*)malloc(sizeof(DNode));
node->data = data;
node->prev = NULL;
node->next = NULL;
return node;
}
DNode* insertFront(DNode *head, int data) {
DNode *node = createDNode(data);
if (head) {
node->next = head;
head->prev = node;
}
return node;
}
void printForward(DNode *head) {
printf("Forward: ");
DNode *tail = NULL;
while (head) {
printf("%d ", head->data);
tail = head;
head = head->next;
}
printf("\n");
printf("Backward: ");
while (tail) {
printf("%d ", tail->data);
tail = tail->prev;
}
printf("\n");
}
int main() {
DNode *head = NULL;
head = insertFront(head, 30);
head = insertFront(head, 20);
head = insertFront(head, 10);
printForward(head);
// Forward: 10 20 30
// Backward: 30 20 10
return 0;
}#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int data; struct Node *next; } Node;
Node* reverse(Node *head) {
Node *prev = NULL;
Node *curr = head;
while (curr) {
Node *next = curr->next; // save next
curr->next = prev; // reverse link
prev = curr; // move prev forward
curr = next; // move curr forward
}
return prev; // new head
}
// helper: build list from array
Node* buildList(int arr[], int n) {
Node *head = NULL, *tail = NULL;
for (int i = 0; i < n; i++) {
Node *node = malloc(sizeof(Node));
node->data = arr[i]; node->next = NULL;
if (!head) head = tail = node;
else { tail->next = node; tail = node; }
}
return head;
}
void printList(Node *h) {
while (h) { printf("%d%s", h->data, h->next ? " -> " : "\n"); h = h->next; }
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
Node *head = buildList(arr, 5);
printf("Original: "); printList(head);
head = reverse(head);
printf("Reversed: "); printList(head);
return 0;
}
// Original: 1 -> 2 -> 3 -> 4 -> 5
// Reversed: 5 -> 4 -> 3 -> 2 -> 1Once a link is overwritten, the remainder of the list may become unreachable. For insertion, establish the new node's links from the existing neighbors before changing the neighbor that leads into it.
The head variable belongs to the caller. Changing only a local copy does not update it.
Use Floyd's slow-and-fast pointer method. The slow pointer advances one node and the fast pointer advances two; if they meet, the list contains a cycle.
Explore 500+ free tutorials across 20+ languages and frameworks.