博主介紹：?全網(wǎng)粉絲喜愛+、前后端領(lǐng)域優(yōu)質(zhì)創(chuàng)作者、本質(zhì)互聯(lián)網(wǎng)精神、堅(jiān)持優(yōu)質(zhì)作品共享、掘金/騰訊云/阿里云等平臺(tái)優(yōu)質(zhì)作者、擅長(zhǎng)前后端項(xiàng)目開發(fā)和畢業(yè)項(xiàng)目實(shí)戰(zhàn)?有需要可以聯(lián)系作者我哦！

??附上相關(guān)C語(yǔ)言版源碼講解??

???? 精彩專欄推薦訂閱???? 不然下次找不到喲

一、鏈表定義

鏈表是一種數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點(diǎn)組成，這些節(jié)點(diǎn)按順序連接在一起形成鏈?zhǔn)浇Y(jié)構(gòu)。每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的引用（指針）。鏈表的最后一個(gè)節(jié)點(diǎn)通常指向一個(gè)特定的值（如空值或null），表示鏈表的結(jié)束。

鏈表是一種數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點(diǎn)組成，這些節(jié)點(diǎn)按順序連接在一起形成鏈?zhǔn)浇Y(jié)構(gòu)。每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的引用（指針）。鏈表的最后一個(gè)節(jié)點(diǎn)通常指向一個(gè)特定的值（如空值或null），表示鏈表的結(jié)束。

鏈表可以分為單鏈表和雙鏈表兩種主要類型：
1. 單鏈表（Singly Linked List）：每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。鏈表的最后一個(gè)節(jié)點(diǎn)指向null。

節(jié)點(diǎn)1      節(jié)點(diǎn)2      節(jié)點(diǎn)3
| 數(shù)據(jù)1 | -> | 數(shù)據(jù)2 | -> | 數(shù)據(jù)3 | -> null

2. 雙鏈表（Doubly Linked List）：每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)、指向下一個(gè)節(jié)點(diǎn)的指針，以及指向前一個(gè)節(jié)點(diǎn)的指針。這使得在雙鏈表中可以更方便地進(jìn)行前向和后向遍歷。

null <- | 數(shù)據(jù)1 | <-> | 數(shù)據(jù)2 | <-> | 數(shù)據(jù)3 | -> null

鏈表優(yōu)點(diǎn)：? 鏈表相對(duì)于數(shù)組的優(yōu)勢(shì)在于插入和刪除操作的效率較高，因?yàn)椴恍枰苿?dòng)大量元素，只需調(diào)整節(jié)點(diǎn)的指針。然而，鏈表的缺點(diǎn)是訪問元素時(shí)需要按順序遍歷，而數(shù)組可以通過索引直接訪問元素。鏈表在內(nèi)存中不需要連續(xù)的存儲(chǔ)空間，因此可以更靈活地分配內(nèi)存。

二、鏈表實(shí)戰(zhàn)

1、單鏈表（C語(yǔ)言實(shí)現(xiàn)版本）

#include <stdio.h>
#include <stdlib.h>

// 定義節(jié)點(diǎn)結(jié)構(gòu)
struct Node {
    int data;           // 節(jié)點(diǎn)數(shù)據(jù)
    struct Node* next;  // 指向下一個(gè)節(jié)點(diǎn)的指針
};

// 定義鏈表結(jié)構(gòu)
struct LinkedList {
    struct Node* head;   // 鏈表頭指針
};

// 初始化鏈表
void initLinkedList(struct LinkedList* list) {
    list->head = NULL;  // 將頭指針初始化為NULL，表示鏈表為空
}

// 在鏈表末尾添加節(jié)點(diǎn)
void append(struct LinkedList* list, int data) {
    // 創(chuàng)建新節(jié)點(diǎn)
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;

    // 判斷鏈表是否為空
    if (list->head == NULL) {
        // 如果為空，將新節(jié)點(diǎn)設(shè)為頭節(jié)點(diǎn)
        list->head = new_node;
    } else {
        // 如果不為空，找到鏈表末尾，將新節(jié)點(diǎn)鏈接到末尾
        struct Node* current = list->head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_node;
    }
}

// 在鏈表開頭添加節(jié)點(diǎn)
void prepend(struct LinkedList* list, int data) {
    // 創(chuàng)建新節(jié)點(diǎn)
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = list->head;

    // 將新節(jié)點(diǎn)設(shè)為頭節(jié)點(diǎn)
    list->head = new_node;
}

// 刪除節(jié)點(diǎn)
void deleteNode(struct LinkedList* list, int data) {
    struct Node* current = list->head;
    struct Node* prev = NULL;

    // 遍歷鏈表，找到待刪除節(jié)點(diǎn)及其前一個(gè)節(jié)點(diǎn)
    while (current != NULL && current->data != data) {
        prev = current;
        current = current->next;
    }

    // 如果找到待刪除節(jié)點(diǎn)
    if (current != NULL) {
        // 如果待刪除節(jié)點(diǎn)不是頭節(jié)點(diǎn)
        if (prev != NULL) {
            prev->next = current->next;
        } else {
            // 如果待刪除節(jié)點(diǎn)是頭節(jié)點(diǎn)
            list->head = current->next;
        }
        free(current);  // 釋放內(nèi)存
    }
}

// 更新節(jié)點(diǎn)
void updateNode(struct LinkedList* list, int oldData, int newData) {
    struct Node* current = list->head;

    // 遍歷鏈表，找到待更新節(jié)點(diǎn)
    while (current != NULL && current->data != oldData) {
        current = current->next;
    }

    // 如果找到待更新節(jié)點(diǎn)
    if (current != NULL) {
        current->data = newData;  // 更新節(jié)點(diǎn)數(shù)據(jù)
    }
}

// 搜索節(jié)點(diǎn)
struct Node* searchNode(struct LinkedList* list, int data) {
    struct Node* current = list->head;

    // 遍歷鏈表，找到包含指定數(shù)據(jù)的節(jié)點(diǎn)
    while (current != NULL && current->data != data) {
        current = current->next;
    }

    return current;  // 返回節(jié)點(diǎn)指針
}

// 顯示鏈表內(nèi)容
void display(struct LinkedList* list) {
    struct Node* current = list->head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 釋放鏈表內(nèi)存
void freeLinkedList(struct LinkedList* list) {
    struct Node* current = list->head;
    struct Node* next = NULL;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    list->head = NULL;
}

int main() {
    struct LinkedList myLinkedList;
    initLinkedList(&myLinkedList);

    // 添加節(jié)點(diǎn)
    append(&myLinkedList, 1);
    append(&myLinkedList, 2);
    append(&myLinkedList, 3);

    // 顯示鏈表內(nèi)容
    printf("鏈表內(nèi)容：");
    display(&myLinkedList);

    // 在開頭添加節(jié)點(diǎn)
    prepend(&myLinkedList, 0);

    // 顯示鏈表內(nèi)容
    printf("在開頭添加節(jié)點(diǎn)后的鏈表：");
    display(&myLinkedList);

    // 刪除節(jié)點(diǎn)
    deleteNode(&myLinkedList, 2);

    // 顯示鏈表內(nèi)容
    printf("刪除節(jié)點(diǎn)后的鏈表：");
    display(&myLinkedList);

    // 更新節(jié)點(diǎn)
    updateNode(&myLinkedList, 1, 10);

    // 顯示鏈表內(nèi)容
    printf("更新節(jié)點(diǎn)后的鏈表：");
    display(&myLinkedList);

    // 搜索節(jié)點(diǎn)
    int searchData = 10;
    struct Node* searchResult = searchNode(&myLinkedList, searchData);
    if (searchResult != NULL) {
        printf("找到數(shù)據(jù)為 %d 的節(jié)點(diǎn)。\n", searchData);
    } else {
        printf("未找到數(shù)據(jù)為 %d 的節(jié)點(diǎn)。\n", searchData);
    }

    // 釋放鏈表內(nèi)存
    freeLinkedList(&myLinkedList);

    return 0;
}

執(zhí)行結(jié)果詳細(xì)：

2、雙鏈表（C++）

#include <iostream>  
#include <cstdlib>  
#include <cstdio>  
  
using namespace std;  
typedef struct Node  
{  
    int data;  
    struct Node *prior;  
    struct Node *next;  
} LinkList;  
  
LinkList *Create()  
{  
    LinkList *head;  
    head=(LinkList*)malloc(sizeof(LinkList));  
    if(head!=NULL)  
    {  
        head->prior=NULL;  
        head->next=NULL;  
        return head;  
    }  
    else return NULL;  
}  
  
int Insert(LinkList *head,int e)  //尾插法
{  
    LinkList *p;  
    LinkList *q=head;  
    p=(LinkList*)malloc(sizeof(LinkList));  
    if(p!=NULL)  
    {  
        p->data=e;  
        p->prior=NULL;  
        p->next=NULL;  
        while(q->next!=NULL)  
        {  
            q=q->next;  
        }  
        q->next=p;  
        return 1;  
    }  
    return 0;  
}  
  
LinkList* Change(LinkList *head) //變成雙向鏈表后返回一個(gè)尾指針  
{  
    LinkList *p,*q;  
    p=head;  
    q=p->next;  
    while(q!=NULL)  
    {  
        q->prior=p;  
        p=p->next;  
        q=q->next;  
    }  
    return p;  
}  
  
void Output1(LinkList *head) //從頭到尾遍歷輸出  
{  
    LinkList *p;  
    p=head->next;  
    while(p!=NULL)  
    {  
        printf("%d ",p->data);  
        p=p->next;  
    }  
    printf("\n");  
}  
  
void Output2(LinkList *tail) //從尾到頭遍歷輸出  
{  
    LinkList *p;  
    p=tail;  
    while(p->prior!=NULL)  
    {  
        printf("%d ",p->data);  
        p=p->prior;  
    }  
    printf("\n");  
}  
  
void FreeLink(LinkList *head)  //釋放
{  
    LinkList *p,*q;  
    p=head;  
    q=NULL;  
    while(p!=NULL)  
    {  
        q=p;  
        p=p->next;  
        free(q);  
    }  
}  
  
int main()  
{  
    LinkList *phead,*tail;  
    int n,e,flag;  
    phead=Create();  
    if(phead!=NULL)  
    {  
        cout<<"請(qǐng)輸入長(zhǎng)度:";
 scanf("%d",&n);  
        for(int i=0;i<n;i++)  
        {  
            scanf("%d",&e);  
            flag=Insert(phead,e);  
        }
 cout<<"從頭到尾輸出為: ";
        Output1(phead);  
        tail=Change(phead); 
 cout<<"從尾到頭輸出為: ";
        Output2(tail);  
        FreeLink(phead);  
    }  
    return 0;  
}

代碼執(zhí)行結(jié)果：

三、分析總結(jié)

鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，具有一些優(yōu)點(diǎn)和應(yīng)用：

優(yōu)點(diǎn)：

1. 動(dòng)態(tài)內(nèi)存分配：鏈表允許在運(yùn)行時(shí)動(dòng)態(tài)分配內(nèi)存，這使得它更加靈活，不需要預(yù)先指定存儲(chǔ)空間大小，通過動(dòng)態(tài)分配內(nèi)存可以實(shí)現(xiàn)降低時(shí)間運(yùn)行成本。

2. 插入和刪除效率高：在鏈表中插入和刪除節(jié)點(diǎn)相對(duì)容易且效率較高。相比之下，數(shù)組在中間或開頭插入/刪除元素可能需要移動(dòng)大量元素。

3. 大小可變：*鏈表可以根據(jù)需要?jiǎng)討B(tài)增長(zhǎng)或縮小，而不浪費(fèi)內(nèi)存。

應(yīng)用：

1. 實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)：鏈表常用于實(shí)現(xiàn)其他動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，如棧、隊(duì)列、圖等。

2. 內(nèi)存分配：動(dòng)態(tài)鏈表的能力使其在動(dòng)態(tài)內(nèi)存分配的場(chǎng)景中非常有用，例如，動(dòng)態(tài)分配內(nèi)存的鏈表可用于管理操作系統(tǒng)的進(jìn)程列表。

3. 實(shí)現(xiàn)算法：鏈表常用于算法實(shí)現(xiàn)，例如，鏈表在排序算法、圖算法等方面有廣泛的應(yīng)用。

4. 嵌入式系統(tǒng)：?在資源受限的嵌入式系統(tǒng)中，鏈表可以更好地處理動(dòng)態(tài)數(shù)據(jù)。

5. LRU緩存淘汰算法：鏈表可以用于實(shí)現(xiàn)LRU（Least Recently Used）緩存淘汰算法，用于管理緩存中的數(shù)據(jù)。

6. 數(shù)據(jù)庫(kù)：數(shù)據(jù)庫(kù)中的索引通常使用鏈表實(shí)現(xiàn)，以支持高效的插入和刪除操作。

總的來說，鏈表在許多場(chǎng)景中都是一種強(qiáng)大且靈活的數(shù)據(jù)結(jié)構(gòu)，特別適合那些需要頻繁插入和刪除操作的應(yīng)用。文章來源地址http://www.zghlxwxcb.cn/news/detail-819635.html

小結(jié)

大家點(diǎn)贊、收藏、關(guān)注、評(píng)論啦 ！

謝謝哦！如果不懂，歡迎大家下方討論學(xué)習(xí)哦。

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】鏈表(單鏈表與雙鏈表實(shí)現(xiàn)+原理+源碼)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！