C DSA Linked List Operations
Create Nodes With malloc()
To create a node while the program runs, use malloc(). Put it in a function, so you can call it again and again:
Example
struct Node *createNode(int value) {
struct Node *newNode = malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = value;
newNode->next = NULL;
return newNode;
}The function asks for memory for one node, checks that it worked (see C NULL), fills in the value, and returns a pointer to the new node.
Free the Memory
Memory from malloc() must be given back with free() when you are done. For a linked list, you free every node, one by one:
Example
void freeList(struct Node *head) {
while (head != NULL) {
struct Node *next = head->next; // Remember the next node
free(head); // Free the current node
head = next; // Move on to the next node
}
}Now let's put it all together. This program builds the list 10, 20, 30 with createNode(), prints it, and frees it:
Example
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
struct Node *createNode(int value) {
struct Node *newNode = malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = value;
newNode->next = NULL;
return newNode;
}
void printList(struct Node *head) {
struct Node *current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
void freeList(struct Node *head) {
while (head != NULL) {
struct Node *next = head->next;
free(head);
head = next;
}
}
int main() {
struct Node *head = createNode(10);
head->next = createNode(20);
head->next->next = createNode(30);
printList(head);
freeList(head);
return 0;
}Result:
10 -> 20 -> 30 -> NULLIt works, but head->next->next is hard to read. Imagine a list with 100 nodes! Let's write a function that inserts nodes for us.
Insert at the Front
The fastest place to add a node is at the front of the list. It takes two steps:
- Make the new node point to the current head.
- Make the new node the new head.
The program uses the same createNode(), printList() and freeList() functions as before. The new part is insertAtFront():
Example
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
struct Node *createNode(int value) {
struct Node *newNode = malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = value;
newNode->next = NULL;
return newNode;
}
// Adds a node at the front, and returns the new head
struct Node *insertAtFront(struct Node *head, int value) {
struct Node *newNode = createNode(value);
newNode->next = head; // Step 1: point to the current head
return newNode; // Step 2: the new node is the new head
}
void printList(struct Node *head) {
struct Node *current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
void freeList(struct Node *head) {
while (head != NULL) {
struct Node *next = head->next;
free(head);
head = next;
}
}
int main() {
struct Node *head = NULL; // An empty list
head = insertAtFront(head, 30);
printList(head);
head = insertAtFront(head, 20);
printList(head);
head = insertAtFront(head, 10);
printList(head);
freeList(head);
return 0;
}Result:
30 -> NULL
20 -> 30 -> NULL
10 -> 20 -> 30 -> NULLWatch the list grow! Each new node goes in front, so we insert 30 first and 10 last.
Notice how we write head = insertAtFront(head, ...). The function returns the new head, and we store it, so head always points to the first node.
Run the simulation below to see how the code above works, one step at a time. The green arrow is the pointer that just changed:
Delete a Node
To delete a node, find the node before it. Then make that node skip over the one you want to delete, and free it.
Deleting the first node is a special case: there is no node before it. Instead, the second node becomes the new head.
The program uses the same createNode(), insertAtFront(), printList() and freeList() functions as before. The new part is deleteValue():
Example
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
struct Node *createNode(int value) {
struct Node *newNode = malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = value;
newNode->next = NULL;
return newNode;
}
struct Node *insertAtFront(struct Node *head, int value) {
struct Node *newNode = createNode(value);
newNode->next = head;
return newNode;
}
// Deletes the first node with this value, and returns the head
struct Node *deleteValue(struct Node *head, int value) {
// The list is empty
if (head == NULL) {
return NULL;
}
// Special case: delete the first node
if (head->data == value) {
struct Node *newHead = head->next;
free(head);
return newHead;
}
// Find the node before the one to delete
struct Node *current = head;
while (current->next != NULL && current->next->data != value) {
current = current->next;
}
// Skip over the node, then free it
if (current->next != NULL) {
struct Node *toDelete = current->next;
current->next = toDelete->next;
free(toDelete);
}
return head;
}
void printList(struct Node *head) {
struct Node *current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
void freeList(struct Node *head) {
while (head != NULL) {
struct Node *next = head->next;
free(head);
head = next;
}
}
int main() {
struct Node *head = NULL;
head = insertAtFront(head, 40);
head = insertAtFront(head, 30);
head = insertAtFront(head, 20);
head = insertAtFront(head, 10);
printList(head);
head = deleteValue(head, 20); // Delete from the middle
printList(head);
head = deleteValue(head, 10); // Delete the first node
printList(head);
freeList(head);
return 0;
}Result:
10 -> 20 -> 30 -> 40 -> NULL
10 -> 30 -> 40 -> NULL
30 -> 40 -> NULLExample Explained
- If the list is empty, there is nothing to delete.
- If the first node has the value, the second node becomes the new head, and the old head is freed.
- Otherwise, the
whileloop stops at the node before the one we want. current->next = toDelete->next;makes the list skip over the node. Then we free it.- If the value is not in the list, nothing changes.
Run the simulation below to see how the code above works, one step at a time. The green arrow is the pointer that just changed:
Summary
- Use
malloc()to create nodes while the program runs, and always check forNULL. - To insert at the front: point the new node to the head, then make it the new head.
- To delete: make the node before it skip over it, then
free()it. - When you are done, free every node in the list.
In a linked list, each node points to one next node. What if a node could point to two nodes? Then you get a tree. That is the next chapter!
