Java 數據結構與算法系列精講之環形鏈表
概述
從今天開始, 小白我將帶大傢開啟 Java 數據結構 & 算法的新篇章.
鏈表
鏈表 (Linked List) 是一種遞歸的動態數據結構. 鏈表以線性表的形式, 在每一個節點存放下一個節點的指針. 鏈表解決瞭數組需要先知道數據大小的缺點, 增加瞭節點的指針域, 空間開銷較大.
鏈表包括三類:
- 單向鏈表
- 雙向鏈表
- 循環鏈表
環形鏈表
環形鏈表 (Circular Linked List) 將單鏈表最後一個節點指向頭節點, 即為環形鏈表. 如圖:
環形鏈表實現
Node 類
// Node類 private class Node<E> { public E e; // 元素 private Node next; // 下一個節點 // 構造 public Node(E e) { this.e = e; this.next = null; } @Override public String toString() { return e.toString(); } }
insert 方法
// 插入數據 public void insert(E e) { // 創建節點 Node node = new Node(e); if (size == 0) { head = node; head.next = head; tail = head; } else { tail.next = node; node.next = tail; tail = node; } size ++; }
remove 方法
// 刪除元素 public void remove(int index) { // 檢查索引是否越界 if (index < 0 || index > size) { throw new RuntimeException("Invalid Index"); } // 獲取index前一個節點 Node prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } // 刪除數據 Node retNode = prev.next; prev.next = retNode.next; size --; }
main
// main public static void main(String[] args) { // 創建循環鏈表 CircularLinkedList<Integer> circularLinkedList = new CircularLinkedList<>(); // 插入 for (int i = 0; i < 5; i++) { circularLinkedList.insert(i); System.out.println(circularLinkedList); } // 刪除 for (int i = 0; i < 2; i++) { circularLinkedList.remove(0); System.out.println(circularLinkedList); } }
輸出結果:
0
0->1
0->1->2
0->1->2->3
0->1->2->3->4
0->2->3->4
0->3->4
完整代碼
public class CircularLinkedList<E> { // Node類 private class Node<E> { public E e; // 元素 private Node next; // 下一個節點 // 構造 public Node(E e) { this.e = e; this.next = null; } @Override public String toString() { return e.toString(); } } // 頭節點和尾節點 private Node head = null; private Node tail = null; private int size; // 鏈表大小 // 構造函數 public CircularLinkedList() { head = new Node(null); size = 0; } // 插入數據 public void insert(E e) { // 創建節點 Node node = new Node(e); if (size == 0) { head = node; head.next = head; tail = head; } else { tail.next = node; node.next = tail; tail = node; } size ++; } // 刪除元素 public void remove(int index) { // 檢查索引是否越界 if (index < 0 || index > size) { throw new RuntimeException("Invalid Index"); } // 獲取index前一個節點 Node prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } // 刪除數據 Node retNode = prev.next; prev.next = retNode.next; size --; } // 鏈表是否為空 public boolean isEmpty() { return size == 0; } @Override public String toString() { StringBuilder builder = new StringBuilder(); Node cur = head; while (cur != tail) { builder.append(cur + "->"); cur = cur.next; } builder.append(cur); return builder.toString(); } // main public static void main(String[] args) { // 創建循環鏈表 CircularLinkedList<Integer> circularLinkedList = new CircularLinkedList<>(); // 插入 for (int i = 0; i < 5; i++) { circularLinkedList.insert(i); System.out.println(circularLinkedList); } // 刪除 for (int i = 0; i < 2; i++) { circularLinkedList.remove(0); System.out.println(circularLinkedList); } } }
到此這篇關於Java 數據結構與算法系列精講之環形鏈表的文章就介紹到這瞭,更多相關Java 環形鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!