LinkList(雙向鏈表實現)

来源:https://www.cnblogs.com/Mr-RanX/archive/2019/07/29/11267016.html
-Advertisement-
Play Games

LinkedList是用鏈表結構存儲數據的，比較適合數據的動態插入和刪除，隨機訪問和遍歷速度比較慢，還提供了List介面i中沒有定義的方法，專門用於操作表頭和表尾的元素，所以可以當作堆棧、隊列和雙向隊列來使用。LInkedList持有頭節點和尾節點的引用，有兩個構造器，一個是無參構造器，另一個是傳入 ...


LinkedList是用鏈表結構存儲數據的，比較適合數據的動態插入和刪除，隨機訪問和遍歷速度比較慢，還提供了List介面i中沒有定義的方法，專門用於操作表頭和表尾的元素，所以可以當作堆棧、隊列和雙向隊列來使用。LInkedList持有頭節點和尾節點的引用，有兩個構造器，一個是無參構造器，另一個是傳入外部集合構造器，它沒有像ArrayList一樣的初始大小的構造器。

  1 //集合元素個數
  2 
  3 transient int size = 0;
  4 
  5  
  6 
  7 //頭結點引用
  8 
  9 transient Node<E> first;
 10 
 11  
 12 
 13 //尾節點引用
 14 transient Node<E> last;
 15 
 16 //無參構造器
 17 public LinkedList() {} 
 18 
 19 //傳入外部集合的構造器
 20 public LinkedList(Collection<? extends E> c) {
 21     this();
 22     addAll(c);
 23 }
 24 
 25 //增(添加)
 26 public boolean add(E e) {
 27   
 28      //在鏈表尾部添加
 29     linkLast(e);
 30     return true;
 31 }
 32 
 33  
 34 //增(插入)
 35 public void add(int index, E element) {
 36 
 37     checkPositionIndex(index);
 38 
 39     if (index == size) {
 40         //在鏈表尾部添加
 41         linkLast(element);
 42     } else {
 43         //在鏈表中部插入
 44         linkBefore(element, node(index));
 45     }
 46 }
 47 
 48  
 49 
 50 //刪(給定下標)
 51 public E remove(int index) {
 52 
 53     //檢查下標是否合法
 54     checkElementIndex(index);
 55     return unlink(node(index));
 56 }
 57 
 58 //刪(給定元素)
 59 public boolean remove(Object o) {
 60     if (o == null) {
 61         for (Node<E> x = first; x != null; x = x.next) {
 62             if (x.item == null) {
 63                 unlink(x);
 64                 return true;
 65             }
 66         }
 67     } else {
 68         //遍歷鏈表
 69         for (Node<E> x = first; x != null; x = x.next) {
 70             if (o.equals(x.item)) {
 71                 //找到了就刪除
 72                 unlink(x);
 73                 return true;
 74             }
 75         }
 76     }
 77     return false;
 78 }
 79 
 80  
 81 
 82 //改
 83 public E set(int index, E element) {
 84 
 85     //檢查下標是否合法
 86     checkElementIndex(index);
 87 
 88     //獲取指定下標的結點引用
 89     Node<E> x = node(index);
 90 
 91     //獲取指定下標結點的值
 92 
 93     E oldVal = x.item;
 94 
 95     //將結點元素設置為新的值
 96 
 97     x.item = element;
 98 
 99     //返回之前的值
100 
101     return oldVal;
102 
103 }
104 
105 
106 //查
107 public E get(int index) {
108 
109     //檢查下標是否合法
110     checkElementIndex(index);
111 
112     //返回指定下標的結點的值
113     return node(index).item;
114 }

 

LinkedList的添加元素的方法主要是調用LinkLast和LinkBefore兩個方法，LinkLast方法是在鏈表後面鏈接一個元素，LinkBefore方法是在鏈表中間插入一個元素。LinkedList的刪除方法通過調用unlink方法將某個元素從鏈表中移除。下麵是鏈表的插入和刪除操作的核心代碼。

 1 //鏈接到指定結點之前
 2 void linkBefore(E e, Node<E> succ) {
 3 
 4     //獲取給定結點的上一個結點引用
 5     final Node<E> pred = succ.prev;
 6 
 7     //創建新結點, 新結點的上一個結點引用指向給定結點的上一個結點
 8     //新結點的下一個結點的引用指向給定的結點
 9     final Node<E> newNode = new Node<>(pred, e, succ);
10 
11     //將給定結點的上一個結點引用指向新結點
12     succ.prev = newNode;
13 
14     //如果給定結點的上一個結點為空, 表明給定結點為頭結點
15     if (pred == null) {
16 
17         //將頭結點引用指向新結點
18         first = newNode;
19     } else {
20         //否則, 將給定結點的上一個結點的下一個結點引用指向新結點
21         pred.next = newNode;
22     }
23 
24     //集合元素個數加一
25     size++;
26 
27     //修改次數加一
28     modCount++;
29 
30 }
31 
32  
33 
34 //卸載指定結點
35 E unlink(Node<E> x) {
36 
37     //獲取給定結點的元素
38     final E element = x.item;
39 
40     //獲取給定結點的下一個結點的引用
41     final Node<E> next = x.next;
42 
43     //獲取給定結點的上一個結點的引用
44     final Node<E> prev = x.prev;
45 
46     //如果給定結點的上一個結點為空, 說明給定結點為頭結點
47     if (prev == null) {
48 
49         //將頭結點引用指向給定結點的下一個結點
50         first = next;
51     } else {
52         //將上一個結點的後繼結點引用指向給定結點的後繼結點
53         prev.next = next;
54         //將給定結點的上一個結點置空
55         x.prev = null;
56 
57     }
58 
59     //如果給定結點的下一個結點為空, 說明給定結點為尾結點
60     if (next == null) {
61 
62         //將尾結點引用指向給定結點的上一個結點
63         last = prev;
64     } else {
65 
66         //將下一個結點的前繼結點引用指向給定結點的前繼結點
67         next.prev = prev;
68         x.next = null;
69 
70     }
71 
72     //將給定結點的元素置空
73     x.item = null;
74 
75     //集合元素個數減一
76     size--;
77     //修改次數加一
78     modCount++;
79     return element;
80 
81 }
View Code

通過源碼的分析，對鏈表的插入和刪除的時間複雜度都是O(1)，而對鏈表的查找和修改操作都需要遍歷鏈表進行元素的定位，這兩個操作都是調用的node(int index) 方法定位元素，如下代碼演示根據下標來定位元素。

 1 //根據指定位置獲取結點
 2 Node<E> node(int index) {
 3     //如果下標在鏈表前半部分, 就從頭開始查起
 4     if (index < (size >> 1)) {
 5         Node<E> x = first;
 6         for (int i = 0; i < index; i++) {
 7             x = x.next;
 8         }
 9         return x;
10     } else {
11         //如果下標在鏈表後半部分, 就從尾開始查起
12         Node<E> x = last;
13         for (int i = size - 1; i > index; i--) {
14             x = x.prev;
15         }
16         return x;
17     }
18 }
View Code

通過下標定位時先判斷是在鏈表的上半部還是下半部

上半部：從頭開始找；

下半部：從尾開始找；

因此通過下標的查找和修改操作的時間複雜度是O(n/2)，通過對雙向鏈表的操作還可以實現單項隊列，雙向隊列和棧的功能。

單向隊列的操作的代碼：

 1 //獲取頭結點
 2 public E peek() {
 3     final Node<E> f = first;
 4     return (f == null) ? null : f.item;
 5 }
 6  
 7 //獲取頭結點
 8 public E element() {
 9     return getFirst();
10 }
11  
12 //彈出頭結點
13 public E poll() {
14     final Node<E> f = first;
15     return (f == null) ? null : unlinkFirst(f);
16 }
17  
18 //移除頭結點
19 public E remove() {
20     return removeFirst();
21 }
22  
23 //在隊列尾部添加結點
24 public boolean offer(E e) {
25     return add(e);
26 }
View Code

雙向隊列的操作：

 1 //在頭部添加
 2 public boolean offerFirst(E e) {
 3     addFirst(e);
 4     return true;
 5 }
 6  
 7 //在尾部添加
 8 public boolean offerLast(E e) {
 9     addLast(e);
10     return true;
11 }
12  
13 //獲取頭結點
14 public E peekFirst() {
15     final Node<E> f = first;
16     return (f == null) ? null : f.item;
17  }
18  
19 //獲取尾結點
20 public E peekLast() {
21     final Node<E> l = last;
22     return (l == null) ? null : l.item;
23 }
View Code

棧操作：

1 //入棧
2 public void push(E e) {
3     addFirst(e);
4 }
5  
6 //出棧
7 public E pop() {
8     return removeFirst();
9 }
View Code

對LindedList，有：

1. LinkedList是基於雙向鏈表實現的，不論是增刪改查方法還是隊列和棧的實現，都可通過操作結點實現

2. LinkedList無需提前指定容量，因為基於鏈表操作，集合的容量隨著元素的加入自動增加

3. LinkedList刪除元素後集合占用的記憶體自動縮小，無需像ArrayList一樣調用trimToSize()方法

4. LinkedList的所有方法沒有進行同步，因此它也不是線程安全的，應該避免在多線程環境下使用

5. 以上分析基於JDK1.7，其他版本會有些出入，因此不能一概而論

以上內容部分借鑒於：https://blog.csdn.net/iteen/article/details/83109717


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 消費端如何保證消息隊列MQ的有序消費
    消息無序產生的原因 消息隊列，既然是隊列就能保證消息在進入隊列，以及出隊列的時候保證消息的有序性，顯然這是在消息的生產端(Producer)，但是往往在生產環境中有多個消息的消費端(Consumer)，儘管消費端在拉取消息時是有序的，但各個消息由於網路等方面原因無法保證在各個消費端中處理時有序。 場 ...
  • Java學習第五天
    1.二維數組 定義：一維數組中的一維數組；數組中的元素，還是數組。 //二維數組初始化 int[][] b=new int[行號(高維下標)][列號(低維下標)]; int[][] b={{1,2,3},{4,5,6}}; //二維數組遍歷 2.在類中定義的變數：成員變數 在類中定義的方法：成員方法 ...
  • Java中的靜態導入
    Java從1.5開始，增加了靜態導入的語法，靜態導入使用 語句，分為兩種： 1. 導入指定類的某個 靜態 成員變數、方法。 2. 導入指定類的全部的 靜態 成員變數、方法。 下麵是代碼演示： 可以看到，使用 可以省略寫包名；而使用 ，則連類名都可以省略。 ...
  • 脈脈的一道網紅Java面試題
    題目如下： 題面看著很簡單，但小心有坑。 Java中方法的參數傳遞機制是值傳遞，所以不能簡單的在 方法中使用 、`b 20`，可以參考。。。。。。 示例答案一：使用System.exit()終止虛擬機 示例答案二：重寫列印流的println方法 ...
  • CSV文件導入資料庫和導出資料庫
    實例一： <?php $filename = 'test'; //導出文件 header("Content-type: application/vnd.ms-excel; charset=utf-8"); Header("Content-Disposition: attachment; filena ...
  • [Spring cloud 一步步實現廣告系統] 7. 中期總結回顧
    在前面的過程中，我們創建了4個project： "服務發現" 我們使用Eureka 作為服務發現組件，學習了 ,`Eureka Client`的使用。 Eureka Server 1. 加依賴 2. 加註解 3. 改配置 使用Sprint Boot 項目三部曲，我們可以快速添加一個新組件，並正常使用 ...
  • 【Python基礎】15_Python中的變數-進階
    1.引用的概念 2.可變類型和不可變類型 3.哈希 ...
  • 038.[轉] JVM啟動過程與類載入
    From: https://blog.csdn.net/luanlouis/article/details/40043991 Step 1.根據JVM記憶體配置要求，為JVM申請特定大小的記憶體空間 JVM啟動時按照其配置要求，申請一塊記憶體，並根據JVM規範和實現將記憶體劃分為幾個區域。 所有的類的定義信 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類