The Art of Dynamic Data: Unveiling Singly Linked Lists

Time： 2024-11-22 Column：Backend & Servers views：261

I. Introduction

The singly linked list is one of the most fundamental and widely used structures in data structures. Unlike arrays, the elements of a singly linked list do not need to be stored contiguously in memory. Each element (node) is connected to the next through pointers. This non-contiguous storage structure gives singly linked lists significant advantages in dynamic memory management, insertion, and deletion operations. Particularly efficient for scenarios involving dynamic data or frequent insertions and deletions, singly linked lists play a crucial role in many algorithms and applications.

This article provides a comprehensive introduction to the concept, structure, and common operations of singly linked lists, complete with detailed code implementations and explanations. By the end, you will gain a deep understanding of the characteristics of singly linked lists and their practical applications in programming.

II. Basic Concepts and Structure of Singly Linked Lists

1. Concept

A singly linked list is a chain-based data structure made up of a series of nodes. Each node contains two parts:

Data Field (Data): Stores the actual data content.
Pointer Field (Next): Points to the address of the next node in the list.

Unlike arrays, where elements are stored in contiguous memory locations, nodes in a linked list can be stored anywhere in memory. This feature allows insertion and deletion operations without shifting elements, making linked lists highly flexible and efficient for dynamic data management. Linked lists can dynamically expand to store any number of nodes, without being limited by predefined capacities like arrays.

Diagram of a linked list structure:

The Art of Dynamic Data: Unveiling Singly Linked Lists

2. Basic Structure

The basic structure of a singly linked list consists of nodes and pointers. Each node includes a data part and a pointer to the next node. Below is the definition of a singly linked list node in C:

typedef int DataType;  
typedef struct ListNode {  
    DataType data;           // Data field  
    struct ListNode* next;   // Pointer field, points to the next node  
} LN;

Each node connects to the next node through the next pointer. The next pointer of the last node is set to NULL, indicating the end of the list. The entry point of the list is called the head pointer, which points to the location of the first node. If the list is empty, the head pointer is NULL.

III. Advantages and Disadvantages of Singly Linked Lists

1. Advantages

Dynamic Memory Management: Nodes in a singly linked list do not need to be stored contiguously in memory. Memory can be dynamically allocated or freed as needed, adapting to changes in data.
Efficient Insertion and Deletion Operations: Insertion or deletion operations at any position in the list only require pointer adjustments, achieving a time complexity of $O(1)$ , which is more efficient than the $O(n)$ complexity of arrays.
Flexibility: Singly linked lists do not require predefined storage space, making them suitable for scenarios with uncertain data sizes.

2. Disadvantages

Extra Memory Overhead: Each node requires additional memory for storing a pointer, increasing overall memory usage.
Low Access Efficiency: To access the $n$ -th element, traversal from the head node is required, resulting in a time complexity of $O(n)$ . This is less efficient than arrays, which allow direct access using indices.
No Reverse Traversal: Singly linked lists only support forward traversal from the head node and cannot traverse backward from the tail node.

IV. Common Operations on Singly Linked Lists

The common operations include inserting, deleting, searching, traversing, and destroying nodes. Below is a detailed explanation and code examples for these operations.

1. Creating a Node

Each node forms the basic building block of a linked list. The following code creates a new node and initializes its data and pointer:

// Create a new node  
LN* CreateNode(DataType x) {  
    LN* newnode = (LN*)malloc(sizeof(LN));  // Allocate memory for a new node  
    if (newnode == NULL) {                 // Check if memory allocation succeeded  
        perror("malloc fail");             // Print error message  
        exit(-1);                          // Exit program  
    }  
    newnode->data = x;      // Set the data field  
    newnode->next = NULL;   // Initialize the next pointer as NULL  
    return newnode;         // Return the new node  
}

2. Initializing (Creating a Head Node)

The head node acts as the entry point for the list. During initialization, a head node is typically created, which may store unused or empty data in its data field:

// Initialize a list and create a head node  
LN* ListInit() {  
    LN* headnode = CreateNode(0);  // Create a head node with data field set to 0  
    return headnode;               // Return the head node  
}

3. Head Insertion

Inserts a new node at the head of the list (before the first element), with a time complexity of $O(1)$ :

// Add a node at the head of the list  
void ListPushHead(LN* phead, DataType x) {  
    assert(phead);                   // Ensure the head node is not NULL  
    LN* newnode = CreateNode(x);     // Create a new node  
    newnode->next = phead->next;     // Point the new node to the next node of the head  
    phead->next = newnode;           // Point the head node to the new node  
}

4. Tail Insertion

Adds a new node at the end of the list, with a time complexity of $O(n)$ :

// Add a node at the end of the list  
void ListPushBack(LN* phead, DataType x) {  
    assert(phead);                   // Ensure the head node is not NULL  
    LN* newnode = CreateNode(x);     // Create a new node  
    LN* pcur = phead;  
    while (pcur->next != NULL) {     // Traverse to the end of the list  
        pcur = pcur->next;  
    }  
    pcur->next = newnode;            // Attach the new node at the end  
}

5. Head Deletion

Deletes the first node of the list, with a time complexity of $O(1)$ :

// Delete the first node of the list  
void ListDelHead(LN* phead) {  
    assert(phead);                   // Ensure the head node is not NULL  
    if (phead->next == NULL) {       // Check if the list is empty  
        printf("The list is empty, cannot perform deletion!\n");  
        return;  
    }  
    LN* temp = phead->next;          // Save the first node  
    phead->next = phead->next->next; // Point the head node to the second node  
    free(temp);                      // Free the memory of the first node  
}

6. Tail Deletion

Deletes the last node of the list, with a time complexity of $O(n)$ :

// Delete the last node of the list  
void ListDelBack(LN* phead) {  
    assert(phead);                   // Ensure the head node is not NULL  
    if (phead->next == NULL) {       // Check if the list is empty  
        printf("The list is empty, cannot perform deletion!\n");  
        return;  
    }  
    LN* pcur = phead;  
    while (pcur->next->next != NULL) { // Traverse to the second-to-last node  
        pcur = pcur->next;  
    }  
    free(pcur->next);                // Free the memory of the last node  
    pcur->next = NULL;               // Set the second-to-last node's next pointer to NULL  
}

7. Searching

Search for a node with the value $x$ in the linked list:

// Search for a node with the value x in the linked list
LN* ListFind(LN* phead, DataType x) {
    assert(phead); // Ensure the head node is not NULL
    LN* pcur = phead->next;
    while (pcur) { // Traverse the linked list
        if (pcur->data == x) { // If a node with data equal to x is found
            return pcur; // Return the node
        }
        pcur = pcur->next;
    }
    return NULL; // Return NULL if no matching node is found
}

8. Insert Before a Specific Position

Insert a new node before the specified node $pos$ :

// Insert a new node before the specified node
void ListInsertFront(LN* phead, LN* pos, DataType x) {
    assert(phead); // Ensure the head node is not NULL
    LN* pcur = phead;
    if (pos == NULL) { // Check if the insertion position is valid
        printf("Invalid insertion position\n");
        return;
    }
    while (pcur->next != pos) { // Find the node preceding pos
        pcur = pcur->next;
    }
    LN* newnode = CreateNode(x); // Create a new node
    newnode->next = pos; // The new node's next points to pos
    pcur->next = newnode; // The previous node's next points to the new node
}

9. Insert After a Specific Position

Insert a new node after the specified node $pos$ :

// Insert a new node after the specified node
void ListInsertBack(LN* pos, DataType x) {
    if (pos == NULL) { // Check if the insertion position is valid
        printf("Invalid insertion position\n");
        return;
    }
    LN* newnode = CreateNode(x); // Create a new node
    newnode->next = pos->next; // The new node's next points to the next node of pos
    pos->next = newnode; // pos's next points to the new node
}

10. Delete a Specific Node

Delete the node at the specified position $pos$ :

// Delete the node at the specified position
void ListErase(LN* phead, LN* pos) {
    assert(phead); // Ensure the head node is not NULL
    if (pos == NULL) { // Check if the deletion position is valid
        printf("Invalid deletion position\n");
        return;
    }
    if (phead->next == NULL) { // Check if the list is empty
        printf("The list is empty, deletion operation cannot be performed!\n");
        return;
    }
    LN* pcur = phead;
    while (pcur->next != pos) { // Find the node preceding pos
        pcur = pcur->next;
    }
    pcur->next = pos->next; // The previous node's next points to the next node of pos
    free(pos); // Free the memory of the node pos
}

11. Print the Linked List

Traverse and print all elements of the linked list:

// Print all nodes in the linked list
void ListPrint(LN* phead) {
    assert(phead); // Ensure the head node is not NULL
    LN* pcur = phead->next;
    while (pcur) { // Traverse each node in the list
        printf("%d->", pcur->data); // Print the data of the current node
        pcur = pcur->next;
    }
    printf("NULL\n"); // Print NULL at the end of the list
}

12. Destroy the Linked List

Free the memory of all nodes in the linked list to prevent memory leaks:

// Destroy the linked list and free the memory of all nodes
void ListDestroy(LN** pphead) {
    LN* pcur = *pphead;
    LN* temp = NULL;
    while (pcur) { // Traverse and free each node in the list
        temp = pcur->next;
        free(pcur);
        pcur = temp;
    }
    *pphead = NULL; // Set the head pointer to NULL
}

V.Complete Code

The complete code consists of three parts: List.h, List.c, and test.c, which correspond to the definition of the linked list, the implementation of linked list operations, and test cases.

List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;

typedef struct ListNode {
    DataType data;          // Data field
    struct ListNode* next;  // Pointer field, pointing to the next node
} LN;

// Function declarations
LN* CreateNode(DataType x);                // Create a new node
LN* ListInit();                            // Initialize a linked list (create the head node)
void ListPushBack(LN* phead, DataType x);  // Add a node at the end
void ListPushHead(LN* phead, DataType x);  // Add a node at the beginning
void ListDelBack(LN* phead);               // Delete the last node
void ListDelHead(LN* phead);               // Delete the first node
void ListPrint(LN* phead);                 // Print the linked list
LN* ListFind(LN* phead, DataType x);       // Search for a node with a given value
void ListInsertFront(LN* phead, LN* pos, DataType x);  // Insert a new node before a specified node
void ListInsertBack(LN* pos, DataType x);              // Insert a new node after a specified node
void ListErase(LN* phead, LN* pos);                    // Delete a specified node
void ListDestroy(LN** pphead);                         // Destroy the linked list

List.c

#define _CRT_SECURE_NO_WARNINGS
#include "List.h"

// Create a new node
LN* CreateNode(DataType x) {
    LN* newnode = (LN*)malloc(sizeof(LN));  // Allocate memory for the node
    if (newnode == NULL) {                 // Check if allocation was successful
        perror("malloc fail");
        exit(-1);  // Exit if allocation fails
    }
    newnode->data = x;      // Initialize the data field
    newnode->next = NULL;   // Initialize the next pointer as NULL
    return newnode;         // Return the new node
}

// Initialize the linked list by creating a head node
LN* ListInit() {
    LN* headnode = CreateNode(0);  // Create a head node with data initialized to 0
    return headnode;
}

// Add a node to the end of the linked list
void ListPushBack(LN* phead, DataType x) {
    assert(phead);  // Ensure the head node is not NULL
    LN* newnode = CreateNode(x);
    LN* pcur = phead;
    while (pcur->next != NULL) {  // Traverse to the end of the list
        pcur = pcur->next;
    }
    pcur->next = newnode;  // Add the new node at the end
}

// Add a node to the beginning of the linked list
void ListPushHead(LN* phead, DataType x) {
    assert(phead);
    LN* newnode = CreateNode(x);
    newnode->next = phead->next;  // New node points to the first node
    phead->next = newnode;        // Head points to the new node
}

// Delete the last node in the linked list
void ListDelBack(LN* phead) {
    assert(phead);
    if (phead->next == NULL) {  // Check if the list is empty
        printf("The list is empty, cannot delete!\n");
        return;
    }
    LN* pcur = phead;
    while (pcur->next->next != NULL) {  // Find the second-to-last node
        pcur = pcur->next;
    }
    free(pcur->next);  // Free the memory of the last node
    pcur->next = NULL;
}

// Delete the first node in the linked list
void ListDelHead(LN* phead) {
    assert(phead);
    if (phead->next == NULL) {
        printf("The list is empty, cannot delete!\n");
        return;
    }
    LN* temp = phead->next;
    phead->next = phead->next->next;  // Update the head to skip the first node
    free(temp);
}

// Print all nodes in the linked list
void ListPrint(LN* phead) {
    assert(phead);
    LN* pcur = phead->next;
    while (pcur) {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("NULL\n");
}

// Search for a node with a specific value
LN* ListFind(LN* phead, DataType x) {
    assert(phead);
    LN* pcur = phead->next;
    while (pcur) {
        if (pcur->data == x) {  // Node found
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;  // Node not found
}

// Insert a node before a specific position
void ListInsertFront(LN* phead, LN* pos, DataType x) {
    assert(phead);
    LN* pcur = phead;
    if (pos == NULL) {
        printf("Invalid insertion position\n");
        return;
    }
    while (pcur->next != pos) {  // Find the node preceding pos
        pcur = pcur->next;
    }
    LN* newnode = CreateNode(x);
    newnode->next = pos;
    pcur->next = newnode;
}

// Insert a node after a specific position
void ListInsertBack(LN* pos, DataType x) {
    if (pos == NULL) {
        printf("Invalid insertion position\n");
        return;
    }
    LN* newnode = CreateNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

// Delete a specific node
void ListErase(LN* phead, LN* pos) {
    assert(phead);
    if (pos == NULL) {
        printf("Invalid deletion position\n");
        return;
    }
    if (phead->next == NULL) {
        printf("The list is empty, cannot delete!\n");
        return;
    }
    LN* pcur = phead;
    while (pcur->next != pos) {
        pcur = pcur->next;
    }
    pcur->next = pos->next;
    free(pos);
}

// Destroy the linked list by freeing all nodes
void ListDestroy(LN** pphead) {
    LN* pcur = *pphead;
    LN* temp = NULL;
    while (pcur) {
        temp = pcur->next;
        free(pcur);
        pcur = temp;
    }
    *pphead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#include "List.h"

void test1() {
    LN* phead = ListInit();  // Create head node
    ListPushHead(phead, 1);
    ListPushHead(phead, 2);
    ListPushHead(phead, 3);
    
    // Test finding a node
    LN* find = ListFind(phead, 2);
    
    /* Uncomment for other tests
    if (find == NULL) {
        printf("Node not found!\n");
    } else {
        printf("Node found!\n");
    }
    ListInsertFront(phead, find, 99);
    ListInsertBack(find, 88);
    ListErase(phead, find);
    */
    
    ListPrint(phead);
    // ListDestroy(&phead);
}

int main() {
    test1();
    return 0;
}

Summary

The singly linked list is a simple yet powerful data structure suitable for dynamic data storage and management. This article introduces the basic concepts, common operations, and implementations of singly linked lists. Mastering these operations can help solve practical programming problems, especially in scenarios requiring frequent insertion and deletion operations.

💰 Support Us