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 -> 1Explore 500+ free tutorials across 20+ languages and frameworks.