Chapter 4: Linked Lists
Welcome to Chapter 4! Now that you’ve become familiar with pointers and dynamic memory allocation, it’s time to explore how pointers unlock one of the most fundamental and powerful data structures: Linked Lists. If you’ve ever worked with arrays and found their fixed size to be limiting, you’re going to love linked lists. They provide flexibility, allowing you to dynamically manage data, making them perfect for scenarios where you don’t know the size of the data in advance.
What is a Linked List?
A Linked List is a linear data structure where each element (commonly called a node) points to the next element in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, each node contains:
- Data: The actual value or data stored in the node.
- Pointer: A reference (or pointer) to the next node in the list.
Here’s a simple graphical representation of a linked list:
[Data | Next] -> [Data | Next] -> [Data | Next] -> NULL
Each node points to the next, and the last node points to NULL, which signifies the end of the list.
Why Use Linked Lists?
Linked lists are dynamic, meaning you can add or remove elements from them without worrying about fixed size or shifting elements (as with arrays). Some reasons to use linked lists include:
- Dynamic Size: They can grow and shrink as needed.
- Efficient Insertion/Deletion: Unlike arrays, inserting or deleting an element doesn’t require shifting all other elements.
- Flexible Memory Usage: Since the nodes are not stored in contiguous memory, you don’t need a large block of continuous memory to create a large list.
Linked lists, like those used in the backend of platforms like Emancipation Edutech Private Limited, efficiently handle data structures that grow dynamically, such as managing student records or tracking progress across multiple courses.
Types of Linked Lists
There are several variations of linked lists, each suited to different tasks:
- Singly Linked List: Each node has a pointer to the next node only.
- Doubly Linked List: Each node has pointers to both the previous and next nodes.
- Circular Linked List: The last node points back to the first node, forming a circle.
For now, we’ll focus on Singly Linked Lists, as they form the foundation for understanding more complex linked lists.
Building a Singly Linked List
To create a linked list, we first need to define the node structure. In C/C++, this is usually done using struct:
#include <stdio.h>
#include <stdlib.h>
// Define a node structure
struct Node {
int data;
struct Node* next;
};
Each node will have two fields:
data: To store the value.next: To store a pointer to the next node.
Creating a Node
We’ll use dynamic memory allocation (malloc) to create nodes dynamically at runtime:
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
This function allocates memory for a new node, initializes its data field, and sets the next pointer to NULL.
Inserting Elements in a Linked List
Now that we have a node, let’s learn how to insert it into a linked list. There are three common ways to insert nodes:
At the Beginning:
void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = createNode(value);
newNode->next = *head;
*head = newNode;
}In this method, we create a new node and point its
nextto the current head of the list, then update the head pointer to the new node.At the End:
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = createNode(value);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}To insert a node at the end, we traverse the list until we find the last node (where
nextisNULL) and then link the new node there.Inserting After a Given Node:
void insertAfter(struct Node* prevNode, int value) {
if (prevNode == NULL) {
printf("The given previous node cannot be NULL");
return;
}
struct Node* newNode = createNode(value);
newNode->next = prevNode->next;
prevNode->next = newNode;
}This method allows you to insert a new node after a given node in the list.
Traversing a Linked List
After inserting elements, you’ll want to traverse the list to access or display the data:
void traverse(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
This function loops through the list, printing each node’s data until it reaches the end (where next is NULL).
Example: Creating and Traversing a Linked List
Here’s an example of creating a linked list and printing its contents:
int main() {
struct Node* head = NULL;
// Inserting nodes
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtBeginning(&head, 5);
insertAtEnd(&head, 30);
// Traverse the list
traverse(head);
return 0;
}
Output:
5 -> 10 -> 20 -> 30 -> NULL
In this example, we created a list with four nodes and then printed it.
Deleting Nodes in a Linked List
Removing nodes from a linked list is just as important as adding them. There are three common ways to delete nodes:
Deleting the First Node:
void deleteFirstNode(struct Node** head) {
if (*head == NULL) return;
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}Deleting the Last Node:
void deleteLastNode(struct Node** head) {
if (*head == NULL) return;
if ((*head)->next == NULL) {
free(*head);
*head = NULL;
return;
}
struct Node* temp = *head;
while (temp->next->next != NULL) {
temp = temp->next;
}
free(temp->next);
temp->next = NULL;
}Deleting a Node by Value:
void deleteNodeByValue(struct Node** head, int value) {
struct Node* temp = *head;
struct Node* prev = NULL;
if (temp != NULL && temp->data == value) {
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != value) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}
Advantages of Linked Lists
Linked lists offer several advantages over arrays, making them suitable for situations where dynamic memory management is essential:
- Dynamic Size: Unlike arrays, linked lists can grow or shrink as needed.
- Efficient Insertions/Deletions: You can easily insert or delete elements without shifting the entire structure, especially in scenarios where you don’t know the size of the data in advance, like tracking multiple student enrollments in online platforms such as Emancipation Edutech Private Limited.
- Efficient Memory Use: Memory allocation is done dynamically, reducing wastage.
Disadvantages of Linked Lists
Linked lists also come with a few drawbacks:
- Extra Memory: Each node requires extra memory for storing the pointer.
- Slow Access: You must traverse the list from the beginning to access an element, whereas arrays allow direct access by index.
- Complexity: Linked lists are more complex to implement and manage than arrays.
Wrapping Up Chapter 4
In this chapter, you’ve learned all about Singly Linked Lists, from creating and inserting nodes to deleting and traversing through them. Linked lists are the backbone of many advanced data structures, and mastering them opens up a world of possibilities in dynamic data management.
Key takeaways:
- Linked lists provide a flexible alternative to arrays.
- You can insert and delete nodes without worrying about shifting elements.
- Traversing linked lists requires starting at the head and moving through each node.
Keep practicing by implementing different types of linked lists, and if you ever need more resources, feel free to check out digilearn.cloud for interactive coding exercises.
Next up: Stacks and Queues
