在Java中,鏈表是一種非常基礎的數據結構。在鏈表中,每個節點都包含了一個值和指向下一個節點的指針。根據節點之間的指針關系,鏈表可以被分為單向鏈表和雙向鏈表。
單向鏈表
在單向鏈表中,每個節點只包含了一個指向下一個節點的指針。這意味著從鏈表的頭節點開始遍歷時,只能訪問到鏈表中的下一個節點。鏈表的尾節點的指針指向null,表示鏈表的結束。
class Node { int val; Node next; public Node(int val) { this.val = val; } } class LinkedList { Node head; public void add(int val) { Node newNode = new Node(val); if (head == null) { head = newNode; } else { Node temp = head; while (temp.next != null) { temp = temp.next; } temp.next = newNode; } } } LinkedList list = new LinkedList(); list.add(1); list.add(2); list.add(3);
雙向鏈表
與單向鏈表不同,雙向鏈表中的每個節點同時包含了指向上一個節點和下一個節點的指針。這使得雙向鏈表可以從鏈表的頭節點和尾節點開始遍歷,并且可以在O(1)時間內獲取到節點的前驅和后繼節點。
class Node { int val; Node prev; Node next; public Node(int val) { this.val = val; } } class LinkedList { Node head; Node tail; public void add(int val) { Node newNode = new Node(val); if (head == null) { head = tail = newNode; } else { tail.next = newNode; newNode.prev = tail; tail = newNode; } } } LinkedList list = new LinkedList(); list.add(1); list.add(2); list.add(3);
總結:單向鏈表和雙向鏈表都是非常常用的鏈表數據結構,在Java編程中應用廣泛。尤其是雙向鏈表因為能夠實現O(1)時間的節點前后指針的訪問,被廣泛應用于實現LRU Cache等需要高效查找最近操作的數據結構。
下一篇vue添加模塊打包