IT培训机构|91免费精品视频|专注编程培训|91免费精品|软件开发培训_91免费国产视频_华清远见教育

    嵌入式linux內核雙向鏈表的組織與存儲

    在單向鏈表中，每個節點中只包括一個指向下個節點的指針域，因此要在單向鏈表中插入一個新節點，就必須從鏈表頭指針開始逐個遍歷鏈表中的節點。雙向鏈表與單向鏈表不同，它的每個節點中包括兩個指針域，分別指向該節點的前一個節點和后一個節點，如圖1.1所示：

圖1.1 雙向鏈表結構

    這樣，在雙向鏈表中由任何一個節點都可以很容易地找到其前面的節點和后面的節點，而不需要在上述的插入（及刪除）操作中由頭節點開始尋找，定義雙向鏈表的節點結構為：

    struct link_node
    {
        element_type data; /*element_type為有效數據類型*/
        struct link_node *next;
        struct link_node *priv;
    };

    嵌入式linux內核雙向鏈表的常見操作

    （1）增加節點

    在雙向鏈表中增加一個節點要比在單鏈表中的插入操作復雜地多，因為在此處節點next指針和priv指針會同時變化，如圖1.2所示：

圖1.2 雙向鏈表插入操作

    由圖中可以看出，在雙向鏈表中增加一個節點會依次完成以下操作。
    ●  創建新節點
    ●  使B前方指向C：B→priv = C。
    ●  使C后方指向B：C→next = B。
    ●  使A后方指向C：A→next = C。
    ●  使C前方指向A：C→priv = A。

    （2）刪除節點

    雙鏈表中刪除節點與單鏈表類似，也是增加過程的反操作，如圖1.3所示

圖1.3 雙向鏈表刪除操作

    由圖中可以看出，在雙向鏈表中刪除元素指針會依次有以下變化。
    ●  使C前方指向A：C→priv = A。
    ●  使A后方指向C：A→next = C。
    ●  使B前后方指向NULL：B->priv = NULL和B->next = NULL ，或（若不再需要該節點）釋放節點B。

   熱點鏈接：

   1、Linux內核模塊程序結構
   2、嵌入式Linux內核如何編譯
   3、嵌入式linux內核數據結構之單向鏈表

更多新聞>>