How to implement linked list in C language

The implementation and operation of the linked list.

1. Introduction to linked list.

A linked list is a common data structure that consists of a series of nodes, each of which contains a data element and a pointer to the next node.

Different from arrays, the elements in the linked list are not necessarily stored continuously in memory, so the linked list has the advantages of dynamic size, efficient insertion and deletion operations, etc.

Linked lists can be divided into singly linked lists, doubly linked lists and circular linked lists.

This article will focus on the implementation of singly linked list and its basic operations.

2. The node structure of the singly linked list.

In C language, we can define the nodes of the singly linked list through the structure.

Each node contains two parts: one is an element that stores data, and the other is a pointer to the next node.

The following is a simple node structure definition:

#include 
#include 

// 定义单链表节点结构
typedef struct Node {
    int data;          // 节点存储的数据
    struct Node* next; // 指向下一个节点的指针
} Node;

3. Create a singly linked list.

To create a singly linked list, you need to start nodes, and then add subsequent nodes one by one.

The following is an example function for creating a singly linked list:

// 创建单链表
Node* createLinkedList() {
    Node* head = (Node*)malloc(sizeof(Node)); // 分配头节点的内存
    if (!head) {
        perror("Failed to allocate memory for head node");
        exit(EXIT_FAILURE);
    }
    head->data = 0; // 初始化头节点数据
    head->next = NULL; // 头节点指针指向NULL
    return head;
}

4. Insert operation.

Inserting nodes in a singly linked list can be inserted at the head, middle, and tail.

The following takes the insertion in the head of the linked list as an example to demonstrate how to perform the insertion operation:

// 在链表头部插入节点
void insertAtHead(Node* head, int newData) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 分配新节点的内存
    if (!newNode) {
        perror("Failed to allocate memory for new node");
        exit(EXIT_FAILURE);
    }
    newNode->data = newData; // 设置新节点的数据
    newNode->next = head->next; // 新节点指向原来的头节点
    head->next = newNode; // 头节点指向新节点
}

5. Delete the operation.

Deleting nodes from the singly linked list can also be done at the head, middle and tail.

The following takes the deletion of the header node as an example to demonstrate how to perform the deletion operation:

// 删除链表头部节点
int deleteAtHead(Node* head) {
    if (head->next == NULL) {
        printf("List is empty, nothing to delete
");
        return -1; // 链表为空，无法删除
    }
    Node* temp = head->next; // 临时保存要删除的节点
    head->next = temp->next; // 头节点指向新的头节点
    int deletedData = temp->data; // 获取被删除节点的数据
    free(temp); // 释放被删除节点的内存
    return deletedData;
}

6. Traverse operations.

Traversing the singly linked list is to access each node in the linked list, and each node can be accessed in sequence from the beginning to the end of the linked list.

The following is an example of traversing a singly linked list and printing data for each node:

// 遍历链表并打印每个节点的数据
void traverseList(Node* head) {
    Node* current = head->next; // 从头节点的下一个节点开始遍历
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next; // 移动到下一个节点
    }
    printf("NULL
"); // 表示链表结束
}

7. Complete sample code.

The following is a complete example program that demonstrates how to create a singly linked list, insert a node in the head of the linked list, delete the head node, and traverse the linked list:

#include 
#include 

// 定义单链表节点结构
typedef struct Node {
    int data;          // 节点存储的数据
    struct Node* next; // 指向下一个节点的指针
} Node;

// 创建单链表
Node* createLinkedList() {
    Node* head = (Node*)malloc(sizeof(Node)); // 分配头节点的内存
    if (!head) {
        perror("Failed to allocate memory for head node");
        exit(EXIT_FAILURE);
    }
    head->data = 0; // 初始化头节点数据
    head->next = NULL; // 头节点指针指向NULL
    return head;
}

// 在链表头部插入节点
void insertAtHead(Node* head, int newData) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 分配新节点的内存
    if (!newNode) {
        perror("Failed to allocate memory for new node");
        exit(EXIT_FAILURE);
    }
    newNode->data = newData; // 设置新节点的数据
    newNode->next = head->next; // 新节点指向原来的头节点
    head->next = newNode; // 头节点指向新节点
}

// 删除链表头部节点
int deleteAtHead(Node* head) {
    if (head->next == NULL) {
        printf("List is empty, nothing to delete
");
        return -1; // 链表为空，无法删除
    }
    Node* temp = head->next; // 临时保存要删除的节点
    head->next = temp->next; // 头节点指向新的头节点
    int deletedData = temp->data; // 获取被删除节点的数据
    free(temp); // 释放被删除节点的内存
    return deletedData;
}

// 遍历链表并打印每个节点的数据
void traverseList(Node* head) {
    Node* current = head->next; // 从头节点的下一个节点开始遍历
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next; // 移动到下一个节点
    }
    printf("NULL
"); // 表示链表结束
}

int main() {
    Node* head = createLinkedList(); // 创建单链表
    insertAtHead(head, 3); // 在头部插入节点3
    insertAtHead(head, 2); // 在头部插入节点2
    insertAtHead(head, 1); // 在头部插入节点1
    printf("Initial list: ");
    traverseList(head); // 遍历并打印链表
    printf("Deleted element: %d
", deleteAtHead(head)); // 删除头部节点并打印被删除的数据
    printf("Updated list: ");
    traverseList(head); // 遍历并打印更新后的链表
    return 0;
}

8. Summarize.

This article introduces how to use C language to implement the basic operations of the singly linked list, including creating a linked list, inserting nodes, deleting nodes and traversing the linked list.

Through these basic operations, we can build more complex data structures and algorithms.

I hope this article will be helpful for you to understand and use linked lists!