Imagine you want to store a list of items but you don't know how many items there will be, and you want to add or remove items often. Why might a linked list be better than an array in this case?
Think about what happens when you add or remove items in an array versus a linked list.
Arrays have a fixed size or need to be resized, which involves copying all items to a new space. Linked lists use nodes connected by pointers, so adding or removing nodes is easy and does not require moving other items.
What will be the printed linked list after running this C code that adds nodes at the front?
typedef struct Node {
int data;
struct Node* next;
} Node;
#include <stdio.h>
#include <stdlib.h>
void printList(Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
int main() {
Node* head = NULL;
for (int i = 1; i <= 3; i++) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = i;
newNode->next = head;
head = newNode;
}
printList(head);
return 0;
}Nodes are added at the front, so the last added node becomes the new head.
Each new node is added before the current head, so the list order is reversed from insertion order: 3, then 2, then 1.
Consider this code snippet that tries to traverse a linked list. Why does it crash?
typedef struct Node {
int data;
struct Node* next;
} Node;
void traverse(Node* head) {
while (head->next != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}Think about what happens when the list has only one node or when head becomes NULL.
The loop condition checks head->next != NULL, so when head is the last node, it stops before printing it. Also, if head is NULL, accessing head->next causes a crash. The loop should check head != NULL instead.
What is the linked list after removing the node with value 2 from this list?
typedef struct Node {
int data;
struct Node* next;
} Node;
#include <stdio.h>
#include <stdlib.h>
void printList(Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
Node* removeNode(Node* head, int val) {
Node* temp = head;
Node* prev = NULL;
while (temp != NULL && temp->data != val) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return head;
if (prev == NULL) {
head = temp->next;
} else {
prev->next = temp->next;
}
free(temp);
return head;
}
int main() {
Node* head = (Node*)malloc(sizeof(Node));
head->data = 1;
head->next = (Node*)malloc(sizeof(Node));
head->next->data = 2;
head->next->next = (Node*)malloc(sizeof(Node));
head->next->next->data = 3;
head->next->next->next = NULL;
head = removeNode(head, 2);
printList(head);
return 0;
}Removing node with value 2 means it should no longer appear in the list.
The node with value 2 is found and removed by adjusting the previous node's next pointer. The list becomes 1 -> 3 -> NULL.
Memory fragmentation happens when free memory is split into small pieces scattered around. How does a linked list help solve this problem compared to arrays?
Think about how linked list nodes are stored in memory compared to arrays.
Linked lists allocate nodes individually anywhere in memory and link them with pointers. This flexibility avoids the need for large continuous memory blocks, reducing fragmentation issues common with arrays.