Linked Lists in C

01What is a Linked List?

A linked list is a linear data structure where elements (called nodes) are connected using pointers. Unlike arrays, linked list elements are not stored in contiguous memory locations.

Why Use Linked Lists?

Dynamic Size

Grow or shrink as needed - no fixed size

Easy Insertion/Deletion

O(1) insertion at head, no shifting needed

Memory Efficient

Allocate memory only when needed

Foundation for Other Structures

Stacks, queues, graphs use linked lists

Linked List Structure

HEAD

NULL

Each node contains data and a pointer to the next node

02Defining a Node

A node is a structure containing two parts: the data and a pointer to the next node.

node.c

1// Define a node structure
2struct Node {
3    int data;           // The actual data
4    struct Node* next;  // Pointer to the next node
5};
6
7// Using typedef for cleaner syntax
8typedef struct Node {
9    int data;
10    struct Node* next;
11} Node;

Self-referential structure: The node structure contains a pointer to itself (struct Node*). This is how nodes link to each other!

03Creating and Linking Nodes

create_list.c

1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct Node {
5    int data;
6    struct Node* next;
7} Node;
8
9// Function to create a new node
10Node* createNode(int data) {
11    Node* newNode = (Node*)malloc(sizeof(Node));
12    if (newNode == NULL) {
13        printf("Memory allocation failed!\n");
14        exit(1);
15    }
16    newNode->data = data;
17    newNode->next = NULL;
18    return newNode;
19}
20
21int main() {
22    // Create three nodes
23    Node* head = createNode(10);
24    Node* second = createNode(20);
25    Node* third = createNode(30);
26    
27    // Link them together
28    head->next = second;
29    second->next = third;
30    // third->next is already NULL
31    
32    // Traverse and print
33    Node* current = head;
34    while (current != NULL) {
35        printf("%d -> ", current->data);
36        current = current->next;
37    }
38    printf("NULL\n");
39    
40    // Free memory
41    free(head);
42    free(second);
43    free(third);
44    
45    return 0;
46}

Expected Output:

10 -> 20 -> 30 -> NULL

04Insertion Operations

Insert at Beginning (Push)

insert_beginning.c

1// Insert at the beginning - O(1) time complexity
2void insertAtBeginning(Node** head, int data) {
3    Node* newNode = createNode(data);
4    newNode->next = *head;  // New node points to current head
5    *head = newNode;        // Head now points to new node
6}
7
8// Usage:
9// Node* head = NULL;
10// insertAtBeginning(&head, 30);  // List: 30
11// insertAtBeginning(&head, 20);  // List: 20 -> 30
12// insertAtBeginning(&head, 10);  // List: 10 -> 20 -> 30

Insert at End (Append)

insert_end.c

1// Insert at the end - O(n) time complexity
2void insertAtEnd(Node** head, int data) {
3    Node* newNode = createNode(data);
4    
5    // If list is empty, new node becomes head
6    if (*head == NULL) {
7        *head = newNode;
8        return;
9    }
10    
11    // Traverse to the last node
12    Node* current = *head;
13    while (current->next != NULL) {
14        current = current->next;
15    }
16    
17    // Link last node to new node
18    current->next = newNode;
19}

Insert After a Node

insert_after.c

1// Insert after a given node - O(1) time complexity
2void insertAfter(Node* prevNode, int data) {
3    if (prevNode == NULL) {
4        printf("Previous node cannot be NULL\n");
5        return;
6    }
7    
8    Node* newNode = createNode(data);
9    newNode->next = prevNode->next;
10    prevNode->next = newNode;
11}

05Deletion Operations

delete_operations.c

1// Delete a node by value
2void deleteNode(Node** head, int key) {
3    Node* temp = *head;
4    Node* prev = NULL;
5    
6    // If head contains the key
7    if (temp != NULL && temp->data == key) {
8        *head = temp->next;
9        free(temp);
10        return;
11    }
12    
13    // Search for the key
14    while (temp != NULL && temp->data != key) {
15        prev = temp;
16        temp = temp->next;
17    }
18    
19    // Key not found
20    if (temp == NULL) {
21        printf("Key %d not found\n", key);
22        return;
23    }
24    
25    // Unlink the node and free memory
26    prev->next = temp->next;
27    free(temp);
28}
29
30// Delete the entire list
31void deleteList(Node** head) {
32    Node* current = *head;
33    Node* next;
34    
35    while (current != NULL) {
36        next = current->next;
37        free(current);
38        current = next;
39    }
40    
41    *head = NULL;
42}

Memory leaks: Always free() nodes when deleting them. Forgetting to free causes memory leaks!

06Traversal and Search

traversal.c

1// Print all elements
2void printList(Node* head) {
3    Node* current = head;
4    while (current != NULL) {
5        printf("%d -> ", current->data);
6        current = current->next;
7    }
8    printf("NULL\n");
9}
10
11// Count nodes
12int countNodes(Node* head) {
13    int count = 0;
14    Node* current = head;
15    while (current != NULL) {
16        count++;
17        current = current->next;
18    }
19    return count;
20}
21
22// Search for a value
23int search(Node* head, int key) {
24    Node* current = head;
25    int position = 0;
26    
27    while (current != NULL) {
28        if (current->data == key) {
29            return position;  // Found at this position
30        }
31        current = current->next;
32        position++;
33    }
34    
35    return -1;  // Not found
36}

07Doubly Linked List

A doubly linked list has nodes with pointers to both the next and previous nodes, allowing bidirectional traversal.

doubly_linked.c

1typedef struct DNode {
2    int data;
3    struct DNode* prev;  // Pointer to previous node
4    struct DNode* next;  // Pointer to next node
5} DNode;
6
7// Create a new doubly linked node
8DNode* createDNode(int data) {
9    DNode* newNode = (DNode*)malloc(sizeof(DNode));
10    newNode->data = data;
11    newNode->prev = NULL;
12    newNode->next = NULL;
13    return newNode;
14}
15
16// Insert at beginning of doubly linked list
17void insertAtBeginningDL(DNode** head, int data) {
18    DNode* newNode = createDNode(data);
19    
20    newNode->next = *head;
21    
22    if (*head != NULL) {
23        (*head)->prev = newNode;
24    }
25    
26    *head = newNode;
27}
28
29// Traverse forward
30void printForward(DNode* head) {
31    DNode* current = head;
32    printf("Forward: ");
33    while (current != NULL) {
34        printf("%d <-> ", current->data);
35        current = current->next;
36    }
37    printf("NULL\n");
38}
39
40// Traverse backward (from tail)
41void printBackward(DNode* tail) {
42    DNode* current = tail;
43    printf("Backward: ");
44    while (current != NULL) {
45        printf("%d <-> ", current->data);
46        current = current->prev;
47    }
48    printf("NULL\n");
49}

08Arrays vs Linked Lists

Feature	Array	Linked List
Memory	Contiguous	Non-contiguous
Size	Fixed (or reallocate)	Dynamic
Access	O(1) random access	O(n) sequential
Insert at start	O(n) - shift elements	O(1)
Insert at end	O(1) if space, O(n) if resize	O(n) or O(1) with tail
Memory overhead	None	Extra pointer per node
Cache performance	Excellent	Poor

09Summary

Key Concepts

* Nodes contain data + pointer to next
* Head pointer tracks the first node
* Last node points to NULL
* Dynamic memory with malloc/free

Operations

* Insert: beginning O(1), end O(n)
* Delete: O(n) search + O(1) remove
* Search: O(n) linear
* Traverse: O(n)

01What is a Linked List?

A linked list is a linear data structure where elements (called nodes) are connected using pointers. Unlike arrays, linked list elements are not stored in contiguous memory locations.

Why Use Linked Lists?

Dynamic Size

Grow or shrink as needed - no fixed size

Easy Insertion/Deletion

O(1) insertion at head, no shifting needed

Memory Efficient

Allocate memory only when needed

Foundation for Other Structures

Stacks, queues, graphs use linked lists

Linked List Structure

HEAD

NULL

Each node contains data and a pointer to the next node

02Defining a Node

A node is a structure containing two parts: the data and a pointer to the next node.

node.c

1// Define a node structure
2struct Node {
3    int data;           // The actual data
4    struct Node* next;  // Pointer to the next node
5};
6
7// Using typedef for cleaner syntax
8typedef struct Node {
9    int data;
10    struct Node* next;
11} Node;

Self-referential structure: The node structure contains a pointer to itself (struct Node*). This is how nodes link to each other!

03Creating and Linking Nodes

create_list.c

1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct Node {
5    int data;
6    struct Node* next;
7} Node;
8
9// Function to create a new node
10Node* createNode(int data) {
11    Node* newNode = (Node*)malloc(sizeof(Node));
12    if (newNode == NULL) {
13        printf("Memory allocation failed!\n");
14        exit(1);
15    }
16    newNode->data = data;
17    newNode->next = NULL;
18    return newNode;
19}
20
21int main() {
22    // Create three nodes
23    Node* head = createNode(10);
24    Node* second = createNode(20);
25    Node* third = createNode(30);
26    
27    // Link them together
28    head->next = second;
29    second->next = third;
30    // third->next is already NULL
31    
32    // Traverse and print
33    Node* current = head;
34    while (current != NULL) {
35        printf("%d -> ", current->data);
36        current = current->next;
37    }
38    printf("NULL\n");
39    
40    // Free memory
41    free(head);
42    free(second);
43    free(third);
44    
45    return 0;
46}

Expected Output:

10 -> 20 -> 30 -> NULL

04Insertion Operations

Insert at Beginning (Push)

insert_beginning.c

1// Insert at the beginning - O(1) time complexity
2void insertAtBeginning(Node** head, int data) {
3    Node* newNode = createNode(data);
4    newNode->next = *head;  // New node points to current head
5    *head = newNode;        // Head now points to new node
6}
7
8// Usage:
9// Node* head = NULL;
10// insertAtBeginning(&head, 30);  // List: 30
11// insertAtBeginning(&head, 20);  // List: 20 -> 30
12// insertAtBeginning(&head, 10);  // List: 10 -> 20 -> 30

Insert at End (Append)

insert_end.c

1// Insert at the end - O(n) time complexity
2void insertAtEnd(Node** head, int data) {
3    Node* newNode = createNode(data);
4    
5    // If list is empty, new node becomes head
6    if (*head == NULL) {
7        *head = newNode;
8        return;
9    }
10    
11    // Traverse to the last node
12    Node* current = *head;
13    while (current->next != NULL) {
14        current = current->next;
15    }
16    
17    // Link last node to new node
18    current->next = newNode;
19}

Insert After a Node

insert_after.c

1// Insert after a given node - O(1) time complexity
2void insertAfter(Node* prevNode, int data) {
3    if (prevNode == NULL) {
4        printf("Previous node cannot be NULL\n");
5        return;
6    }
7    
8    Node* newNode = createNode(data);
9    newNode->next = prevNode->next;
10    prevNode->next = newNode;
11}

05Deletion Operations

delete_operations.c

1// Delete a node by value
2void deleteNode(Node** head, int key) {
3    Node* temp = *head;
4    Node* prev = NULL;
5    
6    // If head contains the key
7    if (temp != NULL && temp->data == key) {
8        *head = temp->next;
9        free(temp);
10        return;
11    }
12    
13    // Search for the key
14    while (temp != NULL && temp->data != key) {
15        prev = temp;
16        temp = temp->next;
17    }
18    
19    // Key not found
20    if (temp == NULL) {
21        printf("Key %d not found\n", key);
22        return;
23    }
24    
25    // Unlink the node and free memory
26    prev->next = temp->next;
27    free(temp);
28}
29
30// Delete the entire list
31void deleteList(Node** head) {
32    Node* current = *head;
33    Node* next;
34    
35    while (current != NULL) {
36        next = current->next;
37        free(current);
38        current = next;
39    }
40    
41    *head = NULL;
42}

Memory leaks: Always free() nodes when deleting them. Forgetting to free causes memory leaks!

06Traversal and Search

traversal.c

1// Print all elements
2void printList(Node* head) {
3    Node* current = head;
4    while (current != NULL) {
5        printf("%d -> ", current->data);
6        current = current->next;
7    }
8    printf("NULL\n");
9}
10
11// Count nodes
12int countNodes(Node* head) {
13    int count = 0;
14    Node* current = head;
15    while (current != NULL) {
16        count++;
17        current = current->next;
18    }
19    return count;
20}
21
22// Search for a value
23int search(Node* head, int key) {
24    Node* current = head;
25    int position = 0;
26    
27    while (current != NULL) {
28        if (current->data == key) {
29            return position;  // Found at this position
30        }
31        current = current->next;
32        position++;
33    }
34    
35    return -1;  // Not found
36}

07Doubly Linked List

A doubly linked list has nodes with pointers to both the next and previous nodes, allowing bidirectional traversal.

doubly_linked.c

1typedef struct DNode {
2    int data;
3    struct DNode* prev;  // Pointer to previous node
4    struct DNode* next;  // Pointer to next node
5} DNode;
6
7// Create a new doubly linked node
8DNode* createDNode(int data) {
9    DNode* newNode = (DNode*)malloc(sizeof(DNode));
10    newNode->data = data;
11    newNode->prev = NULL;
12    newNode->next = NULL;
13    return newNode;
14}
15
16// Insert at beginning of doubly linked list
17void insertAtBeginningDL(DNode** head, int data) {
18    DNode* newNode = createDNode(data);
19    
20    newNode->next = *head;
21    
22    if (*head != NULL) {
23        (*head)->prev = newNode;
24    }
25    
26    *head = newNode;
27}
28
29// Traverse forward
30void printForward(DNode* head) {
31    DNode* current = head;
32    printf("Forward: ");
33    while (current != NULL) {
34        printf("%d <-> ", current->data);
35        current = current->next;
36    }
37    printf("NULL\n");
38}
39
40// Traverse backward (from tail)
41void printBackward(DNode* tail) {
42    DNode* current = tail;
43    printf("Backward: ");
44    while (current != NULL) {
45        printf("%d <-> ", current->data);
46        current = current->prev;
47    }
48    printf("NULL\n");
49}

08Arrays vs Linked Lists

Feature	Array	Linked List
Memory	Contiguous	Non-contiguous
Size	Fixed (or reallocate)	Dynamic
Access	O(1) random access	O(n) sequential
Insert at start	O(n) - shift elements	O(1)
Insert at end	O(1) if space, O(n) if resize	O(n) or O(1) with tail
Memory overhead	None	Extra pointer per node
Cache performance	Excellent	Poor

What You Will Learn

01What is a Linked List?

Why Use Linked Lists?

Linked List Structure

02Defining a Node

03Creating and Linking Nodes

Expected Output:

04Insertion Operations

Insert at Beginning (Push)

Insert at End (Append)

Insert After a Node

05Deletion Operations

06Traversal and Search

07Doubly Linked List

08Arrays vs Linked Lists

09Summary

Key Concepts

Operations

Test Your Knowledge

Related Tutorials

Pointers in C

Structures in C

Dynamic Memory Allocation

Have Feedback?

What You Will Learn

01What is a Linked List?

Why Use Linked Lists?

Linked List Structure

02Defining a Node

03Creating and Linking Nodes

Expected Output:

04Insertion Operations

Insert at Beginning (Push)

Insert at End (Append)

Insert After a Node

05Deletion Operations

06Traversal and Search

07Doubly Linked List

08Arrays vs Linked Lists

09Summary

Key Concepts

Operations

Test Your Knowledge

Related Tutorials

Pointers in C

Structures in C

Dynamic Memory Allocation

Have Feedback?