本文源碼：GitHub·點這里 || GitEE·點這里

一、鏈表簡介

1、鏈表概念

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列節點組成，節點可以在運行時動態生成，節點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。

2、基礎特點

內存存儲

邏輯結構

特點描述

• 物理存儲上是無序且不連續的；
• 鏈表是由多個節點以鏈式結構組成；
• 邏輯層面上看形成一個有序的鏈路結構；

鏈表結構解決數組存儲需要預先知道元素個數的缺陷，可以充分利用內存空間，實現靈活的內存動態管理。

二、單向鏈表

1、基礎描述

單向鏈表是鏈表的一種，其特點是鏈表的鏈接方向是單向的，鏈表的遍歷要從頭部開始順序讀取；結點構成，head指針指向第一個成為表頭結點，終止于最后一個指向NULL的指針。

2、基礎操作

添加數據

• 初始化head節點，作為鏈表的頭；
• 修改當前末尾節點的next指針；
• 新添加的節點房子在鏈表末尾；

刪除數據

遍歷找到要刪除的節點，把刪除節點前個節點的指針指向該刪除節點的下個節點；

三、雙向鏈表

1、概念描述

雙向鏈表也叫雙鏈表，是鏈表的一種，鏈表的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅，從雙向鏈表中的任意一個結點開始，都可以很快速地訪問它的前驅結點和后繼結點，鏈表結構的使用多數都是構造雙向循環鏈表。

2、基礎操作

添加數據

• 遍歷找到鏈表的最后一個節點；
• 修改當前末尾節點的next指針；
• 新添加的節點房子在鏈表末尾；
• 添加最新尾節點的prev指針；

刪除數據

• 雙向鏈表，基于要刪除節點操作即可；
• 操作上圖中要刪除的Node2節點；
• Node2.prev.next = Node2.next;
• Node2.next.prev = Node2.prev;

通過上述流程的操作，就把鏈表中一個節點刪除，剩下節點再度連接成鏈式結構。

3、源碼分析

在Java的API中，LinkedList是典型的雙向鏈表結構，下面基于LinkedList源碼看雙向鏈表的操作。

基礎案例

public class M01_Linked {public static void main(String[] args) {List<User> userList = new LinkedList<>() ;User removeUser = new User(200,"Second") ;// 添加元素userList.add(new User(100,"First")) ;userList.add(removeUser) ;userList.add(new User(300,"Third")) ;System.out.println("初始化："+userList);// 修改元素userList.get(0).setUserName("Zero");System.out.println("修改后："+userList);// 刪除元素userList.remove(removeUser) ;System.out.println("刪除后："+userList);} } class User {private Integer userId ;private String userName ;public User(Integer userId, String userName) {this.userId = userId;this.userName = userName;}@Overridepublic String toString() {return "User{" +"userId=" + userId +", userName='" + userName + '\'' +'}';}// 省略Get和Set方法 }

節點描述

節點三個核心描述：數據，next指針，prev指針。

private static class Node<E> {E item; // 數據Node<E> next; // 下個指針Node<E> prev; // 上個指針Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;} }

首位節點處理

基于LinkedList源碼，首尾節點方式，針對上圖雙鏈表的首位指針特點，這里源碼很好理解。

public class LinkedList {transient Node<E> first;transient Node<E> last;// 處理首節點private void linkFirst(E e) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);first = newNode;if (f == null)last = newNode;elsef.prev = newNode;}// 處理尾節點void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;} }

添加節點

添加節點的方法直接調用linkLast方法，把新節點放到鏈表的尾部即可。

public boolean add(E e) {linkLast(e);return true; }

刪除節點

第一步：遍歷對比，找到要刪除的節點；

public boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false; }

第二步：移除節點，重新搭建鏈表結構，并且把當前鏈表的數據置為null，并返回被移除的節點；

E unlink(Node<E> x) {final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;return element; }

如上就是對Java中LinkedList雙鏈表源碼的部分結構分析，這種代碼看多了，總感覺自己寫的代碼不是Java。

四、環形鏈表

在單鏈表中，將終端結點的指針域NULL改為指向表頭結點或開始結點，這樣就形成了環形鏈表：

環形鏈表鏈表的一種結構，特點是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環。

五、源代碼地址

GitHub·地址 https://github.com/cicadasmile/model-arithmetic-parent GitEE·地址 https://gitee.com/cicadasmile/model-arithmetic-parent

推薦閱讀：算法與數據結構

文章標題

結構與算法：稀疏數組和二維數組轉換

結構與算法：隊列和棧結構

算法應用：RSA算法，加密解密，簽名驗簽流程詳解

算法應用：遞歸算法，處理樹形結構下的業務數據

總結

以上是生活随笔為你收集整理的结构与算法(03)：单向链表和双向链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。