【Linux】Linux中链表数据结构详细说明及用法代码

1，Linux中链表详细说明

在Linux中，链表是一种常用的数据结构，用于组织和存储有序的数据。链表通过指针将一系列数据节点连接成一条数据链，是线性表的一种重要实现方式。相对于数组，链表具有更好的动态性，建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中的任意位置实时插入或删除数据。

链表数据结构至少应包含两个域：数据域和指针域。数据域用于存储数据，指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式，链表又可以分为单链表、双链表、循环链表等多种类型。

单链表：它的特点是仅有一个指针域指向后继节点。对单链表的遍历只能从头至尾。
双链表：它有两个指针域，一个指向前驱节点，另一个指向后继节点。对双链表的遍历可以从头至尾，也可以从尾至头。
循环链表：它的尾节点的指针指向头节点，形成一个环。对循环链表的遍历可以从任何一个节点开始。

2，链表中的指针域作用是什么？

链表中的指针域主要作用是指向链表中的下一个节点。这样，我们可以通过遍历指针域来访问整个链表。指针域可以为空，表示该节点是链表的末尾，或者指向另一个节点，表示该节点后面还有其他节点。

链表中的指针域可以用来创建单向链表、双向链表和循环链表。在单向链表中，每个节点只有一个指针域，指向链表中的下一个节点；在双向链表中，每个节点有两个指针域，一个指向前一个节点，一个指向后一个节点；在循环链表中，链表的最后一个节点的指针域指向链表的头节点，形成一个环。指针域的使用方法可以根据不同的需求来设计，可以灵活地实现各种功能。

3，Linux中单链表结构

在Linux中，单链表是一种常用的数据结构，它由一组节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储数据，而指针域则用于指向下一个节点的地址。

以下是单链表的基本结构：

节点A -> 节点B -> 节点C -> ...

每个节点都有一个指向下一个节点的指针。在最后一个节点，指针指向NULL，表示链表的结尾。

在Linux中，单链表通常可以使用C语言进行实现。以下是一个简单的示例代码，展示了如何使用单链表：

#include <stdio.h>  
#include <stdlib.h>  
  
// 定义链表节点结构体  
struct Node {  
    int data;  
    struct Node* next;  
};  
  
// 创建新节点  
struct Node* createNode(int data) {  
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  
    newNode->data = data;  
    newNode->next = NULL;  
    return newNode;  
}  
  
// 在链表末尾插入新节点  
void insertAtEnd(struct Node** head, int data) {  
    struct Node* newNode = createNode(data);  
    if (*head == NULL) {  
        *head = newNode;  
        return;  
    }  
    struct Node* curr = *head;  
    while (curr->next != NULL) {  
        curr = curr->next;  
    }  
    curr->next = newNode;  
}  
  
// 打印链表中的所有节点  
void printList(struct Node* head) {  
    struct Node* curr = head;  
    while (curr != NULL) {  
        printf("%d ", curr->data);  
        curr = curr->next;  
    }  
    printf("\n");  
}  
  
int main() {  
    struct Node* head = NULL; // 定义链表的头节点指针  
    insertAtEnd(&head, 1);   // 在链表末尾插入节点1  
    insertAtEnd(&head, 2);   // 在链表末尾插入节点2  
    insertAtEnd(&head, 3);   // 在链表末尾插入节点3  
    printList(head);         // 打印链表中的所有节点：1 2 3   
    return 0;  
}

在这个示例代码中，我们首先定义了一个结构体Node来表示链表的节点，其中包含一个数据域data和一个指针域next。然后，我们定义了几个操作单链表的函数：createNode用于创建新节点，insertAtEnd用于在链表末尾插入新节点，printList用于打印链表中的所有节点。最后，在main函数中，我们使用这些函数来创建一个包含三个节点的单链表，并打印出链表中的所有节点。

4，Linux中双向链表数据结构

在Linux中，双向链表是一种更复杂的数据结构，它允许我们在链表的任意位置进行插入和删除操作。双向链表中的每个节点包含两个指针域：一个指向前一个节点，一个指向后一个节点。

在Linux中，双向链表的图形化表示可以使用箭头和节点来表示。以下是一个双向链表的图形化表示示例：

A <-> B <-> C <-> D

在这个示例中，箭头表示指针的指向，节点表示节点。节点A的后继指针指向节点B。节点B的前驱指针指向节点A，后继指针指向节点C。以此类推，每个节点都包含前驱指针和后继指针，形成了一个双向连接的链表。

在Linux中，双向链表的插入和删除操作可以通过修改指针域来实现。以下是一个简单的示例代码，展示了如何在双向链表中插入和删除节点：

#include <stdio.h>  
#include <stdlib.h>  
  
// 定义双向链表节点结构体  
struct Node {  
    int data;  
    struct Node* prev;  
    struct Node* next;  
};  
  
// 创建新节点  
struct Node* createNode(int data) {  
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  
    newNode->data = data;  
    newNode->prev = NULL;  
    newNode->next = NULL;  
    return newNode;  
}  
  
// 在链表头部插入新节点  
void insertAtHead(struct Node** head, int data) {  
    struct Node* newNode = createNode(data);  
    if (*head == NULL) {  
        *head = newNode;  
        return;  
    }  
    newNode->next = *head;  
    (*head)->prev = newNode;  
    *head = newNode;  
}  
  
// 在链表尾部插入新节点  
void insertAtTail(struct Node** tail, int data) {  
    struct Node* newNode = createNode(data);  
    if (*tail == NULL) {  
        *tail = newNode;  
        return;  
    }  
    struct Node* curr = *tail;  
    while (curr->prev != NULL) {  
        curr = curr->prev;  
    }  
    curr->prev = newNode;  
    newNode->next = NULL;  
}  
  
// 在链表中间插入新节点  
void insertAfterNode(struct Node* prevNode, int data) {  
    if (prevNode == NULL) {  
        printf("Previous node is not in the list\n");  
        return;  
    }  
    struct Node* newNode = createNode(data);  
    newNode->next = prevNode->next;  
    newNode->prev = prevNode;  
    if (prevNode->next != NULL) {  
        prevNode->next->prev = newNode;  
    } else {  
        // 如果前一个节点是链表的最后一个节点，则需要更新尾节点指针  
        struct Node* tail = prevNode->prev;  
        while (tail->prev != NULL) {  
            tail = tail->prev;  
        }  
        tail->prev = newNode;  
    }  
    prevNode->next = newNode;  
}  
  
// 删除指定节点（包括其前驱和后继）  
void deleteNode(struct Node* node) {  
    if (node == NULL) {  
        printf("Node is not in the list\n");  
        return;  
    }  
    if (node->prev != NULL) {  
        node->prev->next = node->next;  
    } else {  
        // 如果要删除的节点是链表的第一个节点，则需要更新头节点指针  
        struct Node* head = node->next;  
        while (head != NULL) {  
            head = head->next;  
        }  
        head = node->prev;  
    }  
    if (node->next != NULL) {  
        node->next->prev = node->prev;  
    } else {  
        // 如果要删除的节点是链表的最后一个节点，则需要更新尾节点指针  
        struct Node* tail = node->prev;  
        while (tail != NULL) {  
            tail = tail->prev;  
        }  
        tail = node->next;  
    }  
    free(node); // 释放节点的内存空间  
}

5，循环链表

循环链表是一种链表的变体，其中最后一个节点指向头节点，形成一个环形结构。这种链表结构在某些应用场景中非常有用，例如需要快速插入和删除操作的数据结构。

在Linux中，循环链表通常通过定义一个循环链表结构体来实现。以下是一个简单的示例代码，展示了如何在Linux中实现循环链表：

#include <stdio.h>  
#include <stdlib.h>  
  
// 定义循环链表节点结构体  
struct Node {  
    int data;  
    struct Node* next;  
};  
  
// 定义循环链表结构体  
struct CircularLinkedList {  
    struct Node* head; // 头节点指针  
};  
  
// 创建新节点  
struct Node* createNode(int data) {  
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  
    newNode->data = data;  
    newNode->next = NULL;  
    return newNode;  
}  
  
// 初始化循环链表  
void initializeCircularLinkedList(struct CircularLinkedList* list) {  
    list->head = NULL; // 头节点指针初始化为空  
}  
  
// 在循环链表的头部插入新节点  
void insertAtHead(struct CircularLinkedList* list, int data) {  
    struct Node* newNode = createNode(data);  
    if (list->head == NULL) {  
        list->head = newNode; // 如果链表为空，将新节点作为头节点  
        newNode->next = newNode; // 将新节点的下一个指针指向自己，形成环形结构  
    } else {  
        newNode->next = list->head; // 将新节点的下一个指针指向头节点  
        list->head->prev = newNode; // 将头节点的上一个指针指向新节点  
        list->head = newNode; // 将头节点指向新节点，形成环形结构  
    }  
}  
  
// 在循环链表的尾部插入新节点  
void insertAtTail(struct CircularLinkedList* list, int data) {  
    struct Node* newNode = createNode(data);  
    if (list->head == NULL) {  
        list->head = newNode; // 如果链表为空，将新节点作为头节点  
        newNode->next = newNode; // 将新节点的下一个指针指向自己，形成环形结构  
    } else {  
        struct Node* curr = list->head; // 从头节点开始遍历链表  
        while (curr->next != list->head) {  
            curr = curr->next; // 找到链表的最后一个节点  
        }  
        curr->next = newNode; // 将最后一个节点的下一个指针指向新节点，形成环形结构  
        newNode->prev = curr; // 将新节点的上一个指针指向最后一个节点  
    }  
}  
  
// 在循环链表的指定位置插入新节点（插入位置由索引决定）  
void insertAtIndex(struct CircularLinkedList* list, int index, int data) {  
    if (index == 0) {  
        insertAtHead(list, data); // 如果插入位置是0，则在头部插入新节点  
    } else {  
        struct Node* newNode = createNode(data);  
        struct Node* prev = list->head; // 从头节点开始遍历链表，找到插入位置的前一个节点  
        int count = 0; // 记录当前遍历到的节点数（从0开始计数）  
        while (count < index - 1 && prev != NULL) {  
            prev = prev->next; // 继续遍历链表，直到找到插入位置的前一个节点或链表结束为止  
            count++;  
        }  
        if (prev != NULL) {  
            newNode->next = prev->next; // 将新节点的下一个指针指向插入位置的后继节点（如果存在）  
            prev->next->prev = newNode; // 将后继节点的上一个指针指向新节点（如果存在）  
            prev->next = newNode; // 将插入位置的后继节点的指针指向新节点，形成环形结构（如果存在）  
            newNode->prev = prev; // 将新节点的上一个指针指向插入位置的前一个节点（如果存在）  
        } else {  
            printf("Invalid index\n"); // 如果索引无效（超出范围），则输出错误信息并退出程序（可以根据实际需求进行其他处理）  
        }  
    }  
}