《Hello算法》9、常见链表类型

lugl4313820

《Hello算法》9、常见链表类型 [复制链接]

 

《Hello算法》5、创建链表

《Hello算法》6、链表插入

《Hello算法》7、链表的节点删除

《Hello算法》8、链接表查找+MCU中验证

常见的链表类型包括三种：

• 单向链表：即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 null
• 环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
• 双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

如下图所示：

  测试代码：

濠电姷鏁告慨鐑藉极閸涘﹥鍙忛柣鎴ｆ閺嬩線鏌涘☉姗堟敾闁告瑥绻橀弻锝夊箣閿濆棭妫勯梺鍝勵儎缁舵岸寮诲☉妯锋婵鐗婇弫楣冩⒑閸涘﹦鎳冪紒缁橈耿瀵鏁愭径濠勵吅闂佹寧绻傚Λ顓炍涢崟顖涒拺闁告繂瀚烽崕搴ｇ磼閼搁潧鍝虹€殿喛顕ч埥澶娢熼柨瀣垫綌婵犳鍠楅〃鍛存偋婵犲洤鏋佸Δ锝呭暞閳锋垿鏌涘☉姗堝姛闁瑰啿鍟扮槐鎺旂磼濡搫顫掑┑鐘亾濞撴埃鍋撴慨濠呮缁瑧鎹勯妸褜鍞堕梻浣告啞閼归箖顢栭崶鈺傤潟闁绘劕鎼粻锝夋煥閺冨倹娅曢柛姗€浜跺娲濞淬劌缍婂畷鏇㈡焼瀹ュ懐鍔﹀銈嗗坊閸嬫挻绻涚亸鏍ゅ亾閹颁礁娈ㄦ繝鐢靛У绾板秹寮查幓鎺濈唵閻犺櫣灏ㄩ崝鐔搞亜閺冣偓鐢繝骞冨Δ鍐╁枂闁告洦鍓涢ˇ銉モ攽閻愯尙婀撮柛濠冪箓閻ｇ兘顢曢埛姘そ椤㈡棃宕ㄩ鍛伖闂傚倷绀侀幉锛勬崲閸屾壕鍋撳鍗炲幋鐎规洘娲熼獮鍥偋閸垹骞楁繝寰锋澘鈧挾娆㈤垾鏂ユ灁婵せ鍋撻柡宀€鍠栭悰顕€宕归鍙ユ偅闂備礁鐤囧Λ鍕囬崹顐ｅ弿闁逞屽墴閺岋絽螣濞茶鏅遍梺鍛婅壘閹虫ê顫忕紒妯诲闁惧繒鎳撶粭锟犳⒑閸涘﹥鈷愭繛鑼枛閵嗕礁顫濇０婵囨櫍闂佺粯鍔忛弲婊堟倶娓氣偓濮婃椽妫冨☉姘暫濡炪倧缂氶崡鎶藉春濞戙垹绠ｉ柣鎰暩椤旀洟姊洪悡搴涘仮妞ゃ倕鍊垮畷闈涒枎閹板灚顔旈梺缁樺姈閹苯鈻撳⿰鍫熺厸鐎光偓閳ь剟宕伴弽顓炵畺闁绘垼濮ら崑瀣煕椤愶絿绠栭柣蹇撻叄閺岋絾鎯旈姀鈺佹櫛闂佸摜濮甸悧鐘诲灳閿曞倹鍊婚柦妯侯槺閻ｆ椽姊洪棃娑氱疄闁稿﹥鐗犻獮鍡涙倷閻戞ḿ鍘遍梺鎸庢椤曆冾嚕鐠恒劎纾奸弶鍫涘妿閸欌偓濠殿喖锕︾划顖滅箔閻旂厧鐒垫い鎺嗗亾瀹€锝堝劵椤︽挳鏌熼獮鍨伈妤犵偞甯￠獮姗€寮堕幋婵呯礋闂傚倷鐒﹂惇褰掑垂瑜版帒绠熼柨鐔哄Т绾惧綊鏌涢锝嗙闁绘挻娲橀妵鍕箛椤斿す銏ゆ煕閺冣偓缁捇寮诲澶嬬叆閻庯綆浜炴导宀勬⒑閸濆嫭婀扮紒瀣灴閸╃偤骞嬮敃鈧獮銏′繆閵堝拑姊楅柟顕嗙稻娣囧﹪鎮欓鍕ㄥ亾閺囩姵宕查柛顐犲劚绾惧潡鏌ｉ姀鈶跺綊鎷戦悢鍝ョ闁瑰鍋熼幊鍕煕鎼达絽鏋涢柡灞诲妼閳规垿宕卞鍡橈紒婵犳鍣徊浠嬫偋閹捐绠栨俊銈傚亾闁崇粯鎹囧畷褰掝敊閻ｅ奔閭┑锛勫亼閸娿倝宕ｉ崘顔肩哗閺夊牄鍔庨埞宥呪攽閻樺弶鎼愮紒鐘垫嚀闇夐柨婵嗘噺閹叉悂鏌涘Ο缁樺€愭慨濠呮缁瑩骞愭惔銏″闂備焦妞块崣搴ㄥ窗濮樿埖鍤嶉弶鍫涘妿椤╃兘鎮楅敐搴′簮闁归绮换娑欐綇閸撗冨煂闂佺娅曢悷銊╁Φ閹版澘绠抽柟瀛樼箘瑜板淇婇悙顏勨偓鏍暜閹烘纾瑰┑鐘崇閸庢绻涢崱妯诲鞍闁绘挻鐟╁鍫曞醇閻斿嘲濮㈤梺浼欓檮缁捇寮婚埄鍐╁缂佸绨遍崑鎾诲锤濡も偓閽冪喖鏌曟繛鐐珕闁稿妫濋弻娑氫沪閸撗€妲堝銈呴獜閹凤拷

登录后复制

//创建双向链表的初始化函数 构造函数 测试

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

typedef struct ListNode {
    int val;                //节点的值
    struct ListNode *next;  //指向下一个节点的指针
    struct ListNode *prev;  //指向前一个节点的指针
} ListNode;

/* 构造函数    */
ListNode *newListNode(int val)
{
    ListNode *node;
    node = (ListNode *) malloc(sizeof(ListNode));
    if(node == NULL)
    {
        printf("申请内存失败\n");
        return NULL;
    }
    node->val = val;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

/* 链表节点的释放 */
void freeListNode(ListNode *node)
{
    if(node == NULL)
    {
        return;
    }
    free(node);
}

/* 链表节点的打印 */
void printListNode(ListNode *ListNode)
{
    if(ListNode == NULL)
    {
        printf("链表为空\n");
        return;
    }

    printf("%d \n", ListNode->val);
}

//打印所有节点
void printAllListNode(ListNode *head)
{
    ListNode *p = head;
    while(p != NULL)
    {
        printf("%d \n", p->val);
        p = p->next;
    }
    printf("\n");
}

/* 插入一个节点并插入数据 */
ListNode *insertListNode(ListNode *head, int val)
{
    ListNode *node = newListNode(val);
    if(head == NULL)
    {
        head = node;
    }
    else
    {
        ListNode *temp = head;
        while(temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = node;
        node->prev = temp;
    }
    return head;
}


int main(int argc, char *argv[])
{
    ListNode *head = NULL;
    ListNode *node = NULL;

    head = newListNode(1);
    printListNode(head);
    head = insertListNode(head, 2);
    
    node = head->next;
    printListNode(node);
    printf("插一个值为：");
    head = insertListNode(head, 5);
    printListNode(node->next);
    printf("上一个节点值为：\n");
    printListNode(node->prev);
    printf("所有节点：\n");
    printAllListNode(head);
    freeListNode(head);
}

测试结果：

濠电姷鏁告慨鐑藉极閸涘﹥鍙忛柣鎴ｆ閺嬩線鏌涘☉姗堟敾闁告瑥绻橀弻锝夊箣閿濆棭妫勯梺鍝勵儎缁舵岸寮诲☉妯锋婵鐗婇弫楣冩⒑閸涘﹦鎳冪紒缁橈耿瀵鏁愭径濠勵吅闂佹寧绻傚Λ顓炍涢崟顖涒拺闁告繂瀚烽崕搴ｇ磼閼搁潧鍝虹€殿喛顕ч埥澶娢熼柨瀣垫綌婵犳鍠楅〃鍛存偋婵犲洤鏋佸Δ锝呭暞閳锋垿鏌涘☉姗堝姛闁瑰啿鍟扮槐鎺旂磼濡搫顫掑┑鐘亾濞撴埃鍋撴慨濠呮缁瑧鎹勯妸褜鍞堕梻浣告啞閼归箖顢栭崶鈺傤潟闁绘劕鎼粻锝夋煥閺冨倹娅曢柛姗€浜跺娲濞淬劌缍婂畷鏇㈡焼瀹ュ懐鍔﹀銈嗗坊閸嬫挻绻涚亸鏍ゅ亾閹颁礁娈ㄦ繝鐢靛У绾板秹寮查幓鎺濈唵閻犺櫣灏ㄩ崝鐔搞亜閺冣偓鐢繝骞冨Δ鍐╁枂闁告洦鍓涢ˇ銉モ攽閻愯尙婀撮柛濠冪箓閻ｇ兘顢曢埛姘そ椤㈡棃宕ㄩ鍛伖闂傚倷绀侀幉锛勬崲閸屾壕鍋撳鍗炲幋鐎规洘娲熼獮鍥偋閸垹骞楁繝寰锋澘鈧挾娆㈤垾鏂ユ灁婵せ鍋撻柡宀€鍠栭悰顕€宕归鍙ユ偅闂備礁鐤囧Λ鍕囬崹顐ｅ弿闁逞屽墴閺岋絽螣濞茶鏅遍梺鍛婅壘閹虫ê顫忕紒妯诲闁惧繒鎳撶粭锟犳⒑閸涘﹥鈷愭繛鑼枛閵嗕礁顫濇０婵囨櫍闂佺粯鍔忛弲婊堟倶娓氣偓濮婃椽妫冨☉姘暫濡炪倧缂氶崡鎶藉春濞戙垹绠ｉ柣鎰暩椤旀洟姊洪悡搴涘仮妞ゃ倕鍊垮畷闈涒枎閹板灚顔旈梺缁樺姈閹苯鈻撳⿰鍫熺厸鐎光偓閳ь剟宕伴弽顓炵畺闁绘垼濮ら崑瀣煕椤愶絿绠栭柣蹇撻叄閺岋絾鎯旈姀鈺佹櫛闂佸摜濮甸悧鐘诲灳閿曞倹鍊婚柦妯侯槺閻ｆ椽姊洪棃娑氱疄闁稿﹥鐗犻獮鍡涙倷閻戞ḿ鍘遍梺鎸庢椤曆冾嚕鐠恒劎纾奸弶鍫涘妿閸欌偓濠殿喖锕︾划顖滅箔閻旂厧鐒垫い鎺嗗亾瀹€锝堝劵椤︽挳鏌熼獮鍨伈妤犵偞甯￠獮姗€寮堕幋婵呯礋闂傚倷鐒﹂惇褰掑垂瑜版帒绠熼柨鐔哄Т绾惧綊鏌涢锝嗙闁绘挻娲橀妵鍕箛椤斿す銏ゆ煕閺冣偓缁捇寮诲澶嬬叆閻庯綆浜炴导宀勬⒑閸濆嫭婀扮紒瀣灴閸╃偤骞嬮敃鈧獮銏′繆閵堝拑姊楅柟顕嗙稻娣囧﹪鎮欓鍕ㄥ亾閺囩姵宕查柛顐犲劚绾惧潡鏌ｉ姀鈶跺綊鎷戦悢鍝ョ闁瑰鍋熼幊鍕煕鎼达絽鏋涢柡灞诲妼閳规垿宕卞鍡橈紒婵犳鍣徊浠嬫偋閹捐绠栨俊銈傚亾闁崇粯鎹囧畷褰掝敊閻ｅ奔閭┑锛勫亼閸娿倝宕ｉ崘顔肩哗閺夊牄鍔庨埞宥呪攽閻樺弶鎼愮紒鐘垫嚀闇夐柨婵嗘噺閹叉悂鏌涘Ο缁樺€愭慨濠呮缁瑩骞愭惔銏″闂備焦妞块崣搴ㄥ窗濮樿埖鍤嶉弶鍫涘妿椤╃兘鎮楅敐搴′簮闁归绮换娑欐綇閸撗冨煂闂佺娅曢悷銊╁Φ閹版澘绠抽柟瀛樼箘瑜板淇婇悙顏勨偓鏍暜閹烘纾瑰┑鐘崇閸庢绻涢崱妯诲鞍闁绘挻鐟╁鍫曞醇閻斿嘲濮㈤梺浼欓檮缁捇寮婚埄鍐╁缂佸绨遍崑鎾诲锤濡も偓閽冪喖鏌曟繛鐐珕闁稿妫濋弻娑氫沪閸撗€妲堝銈呴獜閹凤拷

登录后复制

liujianhua@liujianhuadeMac-mini HelloC % ./a.out        
1 
2 
插一个值为：5 
上一个节点值为：
1 
所有节点：
1 
2 
5 

双向链表提供了可以向上，向后的访问。

查看本帖全部内容，请登录或者注册

Jacktang

看了楼主的这个介绍，大致了解了单向链表和环形链、双向链表的不同了