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

2023-12-20 10:24:40

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"); // 如果索引无效(超出范围),则输出错误信息并退出程序(可以根据实际需求进行其他处理)  
        }  
    }  
}

文章来源:https://blog.csdn.net/jiangchaobing_2017/article/details/135078107
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。