Java中的鏈表結(jié)構(gòu)是指，將一組數(shù)據(jù)按照指定規(guī)則連接起來的數(shù)據(jù)結(jié)構(gòu)。它由多個(gè)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素和一個(gè)指向下一個(gè)節(jié)點(diǎn)的引用。在Java中，這種數(shù)據(jù)結(jié)構(gòu)被封裝成了一個(gè)鏈表類，常見的有單向鏈表、雙向鏈表和循環(huán)鏈表等。
一、單向鏈表
單向鏈表是最簡單的一種鏈表結(jié)構(gòu)，節(jié)點(diǎn)只包含一個(gè)數(shù)據(jù)元素和一個(gè)指向下一個(gè)節(jié)點(diǎn)的引用。它的優(yōu)點(diǎn)是刪除和插入節(jié)點(diǎn)非常方便，但是定位元素較為困難。
-
鏈表的節(jié)點(diǎn)定義
public class Node { // 節(jié)點(diǎn)的數(shù)據(jù)元素 private int data; // 指向下一個(gè)節(jié)點(diǎn)的引用 private Node next; // 構(gòu)造函數(shù) public Node(int data) { this.data = data; this.next = null; } // 獲得數(shù)據(jù)元素 public int getData() { return data; } // 設(shè)置數(shù)據(jù)元素 public void setData(int data) { this.data = data; } // 獲得下一個(gè)節(jié)點(diǎn)的引用 public Node getNext() { return next; } // 設(shè)置下一個(gè)節(jié)點(diǎn)的引用 public void setNext(Node next) { this.next = next; } } -
鏈表的操作方法
-
添加節(jié)點(diǎn)：向鏈表的末尾添加一個(gè)新節(jié)點(diǎn)
public void addNode(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; } else { Node currentNode = head; while (currentNode.getNext() != null) { currentNode = currentNode.getNext(); } currentNode.setNext(newNode); } size++; } -
刪除節(jié)點(diǎn)：刪除鏈表中指定元素的節(jié)點(diǎn)
public boolean removeNode(int data) { if (head == null) { return false; } if (head.getData() == data) { head = head.getNext(); size--; return true; } Node currentNode = head; while (currentNode.getNext() != null) { if (currentNode.getNext().getData() == data) { currentNode.setNext(currentNode.getNext().getNext()); size--; return true; } currentNode = currentNode.getNext(); } return false; } -
查找節(jié)點(diǎn)：根據(jù)元素值查找節(jié)點(diǎn)
public Node findNode(int data) { if (head == null) { return null; } Node currentNode = head; while (currentNode != null) { if (currentNode.getData() == data) { return currentNode; } currentNode = currentNode.getNext(); } return null; }
-
二、雙向鏈表
雙向鏈表是在單向鏈表基礎(chǔ)上增加了一個(gè)指向前一個(gè)節(jié)點(diǎn)的引用，這樣可以方便地實(shí)現(xiàn)反向遍歷和插入、刪除操作。但是相應(yīng)地，它需要占用更多的存儲(chǔ)空間。
-
鏈表的節(jié)點(diǎn)定義
public class Node { // 節(jié)點(diǎn)的數(shù)據(jù)元素 private int data; // 指向下一個(gè)節(jié)點(diǎn)的引用 private Node next; // 指向前一個(gè)節(jié)點(diǎn)的引用 private Node prev; // 構(gòu)造函數(shù) public Node(int data) { this.data = data; this.next = null; this.prev = null; } // 獲得數(shù)據(jù)元素 public int getData() { return data; } // 設(shè)置數(shù)據(jù)元素 public void setData(int data) { this.data = data; } // 獲得下一個(gè)節(jié)點(diǎn)的引用 public Node getNext() { return next; } // 設(shè)置下一個(gè)節(jié)點(diǎn)的引用 public void setNext(Node next) { this.next = next; } // 獲得前一個(gè)節(jié)點(diǎn)的引用 public Node getPrev() { return prev; } // 設(shè)置前一個(gè)節(jié)點(diǎn)的引用 public void setPrev(Node prev) { this.prev = prev; } } -
鏈表的操作方法
-
添加節(jié)點(diǎn)：向鏈表的末尾添加一個(gè)新節(jié)點(diǎn)
public void addNode(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; } else { Node currentNode = head; while (currentNode.getNext() != null) { currentNode = currentNode.getNext(); } currentNode.setNext(newNode); newNode.setPrev(currentNode); } size++; } -
刪除節(jié)點(diǎn)：刪除鏈表中指定元素的節(jié)點(diǎn)
public boolean removeNode(int data) { if (head == null) { return false; } if (head.getData() == data) { head = head.getNext(); if (head != null) { head.setPrev(null); } size--; return true; } Node currentNode = head; while (currentNode != null) { if (currentNode.getData() == data) { currentNode.getPrev().setNext(currentNode.getNext()); if (currentNode.getNext() != null) { currentNode.getNext().setPrev(currentNode.getPrev()); } size--; return true; } currentNode = currentNode.getNext(); } return false; } -
查找節(jié)點(diǎn)：根據(jù)元素值查找節(jié)點(diǎn)
public Node findNode(int data) { if (head == null) { return null; } Node currentNode = head; while (currentNode != null) { if (currentNode.getData() == data) { return currentNode; } currentNode = currentNode.getNext(); } return null; }
-
三、循環(huán)鏈表
循環(huán)鏈表是一種特殊的鏈表結(jié)構(gòu)，它的最后一個(gè)節(jié)點(diǎn)的指針不是指向null，而是指向第一個(gè)節(jié)點(diǎn)，形成一個(gè)環(huán)狀結(jié)構(gòu)。這樣在循環(huán)遍歷時(shí)可以省去邊界判斷，但是插入和刪除操作需要特殊考慮。
-
鏈表的節(jié)點(diǎn)定義
public class Node { // 節(jié)點(diǎn)的數(shù)據(jù)元素 private int data; // 指向下一個(gè)節(jié)點(diǎn)的引用 private Node next; // 構(gòu)造函數(shù) public Node(int data) { this.data = data; this.next = null; } // 獲得數(shù)據(jù)元素 public int getData() { return data; } // 設(shè)置數(shù)據(jù)元素 public void setData(int data) { this.data = data; } // 獲得下一個(gè)節(jié)點(diǎn)的引用 public Node getNext() { return next; } // 設(shè)置下一個(gè)節(jié)點(diǎn)的引用 public void setNext(Node next) { this.next = next; } } -
鏈表的操作方法
-
添加節(jié)點(diǎn)：向鏈表的末尾添加一個(gè)新節(jié)點(diǎn)
public void addNode(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; head.setNext(head); } else { Node currentNode = head; while (currentNode.getNext() != head) { currentNode = currentNode.getNext(); } currentNode.setNext(newNode); newNode.setNext(head); } size++; } -
刪除節(jié)點(diǎn)：刪除鏈表中指定元素的節(jié)點(diǎn)
public boolean removeNode(int data) { if (head == null) { return false; } if (head.getData() == data) { Node currentNode = head; while (currentNode.getNext() != head) { currentNode = currentNode.getNext(); } head = head.getNext(); currentNode.setNext(head); size--; return true; } Node currentNode = head; while (currentNode.getNext() != head) { if (currentNode.getNext().getData() == data) { currentNode.setNext(currentNode.getNext().getNext()); size--; return true; } currentNode = currentNode.getNext(); } return false; } -
查找節(jié)點(diǎn)：根據(jù)元素值查找節(jié)點(diǎn)
public Node findNode(int data) { if (head == null) { return null; } Node currentNode = head; while (currentNode.getNext() != head) { if (currentNode.getData() == data) { return currentNode; } currentNode = currentNode.getNext(); } if (currentNode.getData() == data) { return currentNode; } return null; }
-
四、鏈表的時(shí)間復(fù)雜度分析
鏈表結(jié)構(gòu)相比于數(shù)組具有更靈活的插入和刪除操作，但是它也存在一些缺點(diǎn)。在訪問隨機(jī)元素時(shí)，需要從頭開始遍歷整個(gè)鏈表，時(shí)間復(fù)雜度為O(N)；而在數(shù)組中可以通過索引直接訪問元素，時(shí)間復(fù)雜度為O(1)。下面給出單向鏈表、雙向鏈表和循環(huán)鏈表的常見操作的時(shí)間復(fù)雜度：
| 操作 | 單向鏈表 | 雙向鏈表 | 循環(huán)鏈表 |
|---|---|---|---|
| 訪問元素 | O(N) | O(N) | O(N) |
| 插入元素 | O(1) | O(1) | O(1) |
| 刪除元素 | O(N) | O(N) | O(N) |
五、鏈表的應(yīng)用舉例
鏈表結(jié)構(gòu)常見于計(jì)算機(jī)科學(xué)領(lǐng)域中的各種數(shù)據(jù)結(jié)構(gòu)與算法，例如棧、隊(duì)列、哈希表和圖等。下面以一個(gè)簡單的應(yīng)用場景為例，說明鏈表的應(yīng)用。
-
題目描述
給定一個(gè)鏈表，判斷它是否為回文鏈表。回文鏈表是指正序和倒序讀取的結(jié)果相同的鏈表。
-
解題思路
可以使用快慢指針將鏈表分成兩半，然后將后半部分反轉(zhuǎn)，最后比較前半部分和反轉(zhuǎn)后的后半部分是否相同。
-
代碼實(shí)現(xiàn)
public boolean isPalindrome(Node head) { if (head == null || head.getNext() == null) { return true; } Node slow = head, fast = head; while (fast.getNext() != null && fast.getNext().getNext() != null) { slow = slow.getNext(); fast = fast.getNext().getNext(); } Node secondHalf = reverseList(slow.getNext()); Node currentNode = head; while (secondHalf != null) { if (currentNode.getData() != secondHalf.getData()) { return false; } currentNode = currentNode.getNext(); secondHalf = secondHalf.getNext(); } return true; } private Node reverseList(Node head) { if (head == null || head.getNext() == null) { return head; } Node prev = null, current = head; while (current != null) { Node next = current.getNext(); current.setNext(prev); prev = current; current = next; } return prev; }
六、使用場景
使用場景，常見的應(yīng)用包括：
- 實(shí)現(xiàn)棧和隊(duì)列：鏈表作為?；蜿?duì)列的底層數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)入棧、出棧、入隊(duì)、出隊(duì)等操作時(shí)具有高效性和靈活性。
- 實(shí)現(xiàn)哈希表：在哈希表中，每個(gè)關(guān)鍵字會(huì)被映射到一個(gè)桶中，而這個(gè)桶則是一個(gè)鏈表，其中存放相同關(guān)鍵字的元素。
- 作為緩存的數(shù)據(jù)結(jié)構(gòu)：在緩存中，經(jīng)常需要在數(shù)據(jù)集中插入、刪除、移動(dòng)元素。鏈表結(jié)構(gòu)提供了一種高效的方式來操作這些數(shù)據(jù)。
- 瀏覽器歷史記錄和撤銷功能：瀏覽器歷史記錄和撤銷功能等需要保留一系列操作或狀態(tài)的應(yīng)用場景都可以使用鏈表來實(shí)現(xiàn)。
- 實(shí)現(xiàn)圖論算法：在圖論中，使用鏈表結(jié)構(gòu)可以方便地表示鄰接表，保存每個(gè)節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)。
- 數(shù)據(jù)庫管理系統(tǒng)：在數(shù)據(jù)庫管理系統(tǒng)中，可以使用鏈表來優(yōu)化查詢操作的效率。
