一：概述

鏈表（Linked list）由一些節(jié)點組成，物理存儲非連續(xù)的線性表。其中每個節(jié)點都會存儲下個節(jié)點的指針，由于實際存儲空間不連續(xù)，對鏈表插入節(jié)點，刪除節(jié)點可以達(dá)到O(1)的復(fù)雜度，但是對一個節(jié)點的訪問需要O(n)的時間。

鏈表有單向鏈表，雙向鏈表。

二：單向鏈表

單向鏈表的每個節(jié)點有數(shù)據(jù)項和指針(指向下個節(jié)點地址數(shù)據(jù))組成，下圖為一個單向鏈表，表頭沒有數(shù)據(jù)項，只有指向下一個節(jié)點的指針。表尾節(jié)點指向下一個節(jié)點pNext指針為NULL（空）。

結(jié)構(gòu)體表示為：

//單向鏈表節(jié)點數(shù)據(jù)結(jié)構(gòu) typedef?struct?linkNode {void?*val;?//數(shù)據(jù)項(任意類型)struct?linkNode *next; }node;

插入節(jié)點操作：

單向鏈表中由四個數(shù)據(jù)節(jié)點，數(shù)據(jù)1，數(shù)據(jù)2，數(shù)據(jù)3，數(shù)據(jù)4，現(xiàn)在數(shù)據(jù)1和數(shù)據(jù)2節(jié)點間插入數(shù)據(jù)5，只需把數(shù)據(jù)1節(jié)點的pNext指向新的節(jié)點，把新節(jié)點的pNext指向數(shù)據(jù)2節(jié)點即可。

刪除節(jié)點操作：

刪除節(jié)點2，只需把第一個節(jié)點的pNext執(zhí)行數(shù)據(jù)3節(jié)點，同時釋放節(jié)點2的存儲空間即可。

三：雙向鏈表

雙向鏈表有別于單向的，每個節(jié)點除了數(shù)據(jù)項外有兩個指針分別指向前一個節(jié)點和后一個節(jié)點，占用空間會大一些，可以實現(xiàn)從頭到尾的遍歷，又可以從尾到頭遍歷。

結(jié)構(gòu)體表示為：

//雙向鏈表節(jié)點數(shù)據(jù)結(jié)構(gòu) typedef?struct?dLinkNode {void?*val;?//數(shù)據(jù)項(任意類型)struct?dLinkNode?*prev;??????struct?dLinkNode?*next; }node;

插入節(jié)點操作：

節(jié)點1與節(jié)點2之間插入新節(jié)點5，需要把節(jié)點1的pNext指向節(jié)點5，節(jié)點5的pHead指向節(jié)點1，節(jié)點5的pNext指向節(jié)點2，節(jié)點2的pHead指向節(jié)點5，如下圖所示：

刪除節(jié)點操作：

刪除節(jié)點2，把節(jié)點1的pNext指向節(jié)點3，把節(jié)點3的pHead指向節(jié)點1，同時釋放節(jié)點2的存儲空間即可。

四：鏈表與數(shù)組區(qū)別

1.鏈表存儲空間不連續(xù)，可以充分利用碎片空間，數(shù)組的存儲空間是連續(xù)的，內(nèi)存空間要求高，必須要有足夠連續(xù)的內(nèi)存空間。

2.鏈表的插入刪除元素簡單，無需對元素移動，但查詢元素會慢，數(shù)組對元素的插入刪除較復(fù)雜，同時使用時要預(yù)先指定長度，但數(shù)組的查詢會很快。

最后，為大家準(zhǔn)備一篇「Java最常見200+面試題全解析」，助力大家找到合適的工作，這份面試題包含的模塊有：

• Java、Jvm 最常見面試題解析；

• Spring、Spring MVC、MyBatis、Hibernate 面試題解析；

• MySQL、Redis 面試題解析；

• RabbitMQ、Kafka、Zookeeper 面試解析；

• 微服務(wù) Spring Boot、Spring Cloud 面試解析。

掃描下面二維碼付費閱讀

【End】

關(guān)注下方二維碼，訂閱更多精彩內(nèi)容。

轉(zhuǎn)發(fā)朋友圈，是對我最大的支持。

總結(jié)

以上是生活随笔為你收集整理的【数据结构与算法】通俗易懂说链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。