鏈表
陣列與鏈表
- 同為線性表存盤結構
- 陣列在一段連續的空間上，鏈表將分散的記憶體塊連接起來使用
單鏈表
SinglyLinkedList
結構
- 結點：存盤鏈表的每一個記憶體塊
- 后繼指標：每個結點除了存盤資料外，還要記錄下一個記憶體塊的地址
- 頭結點：第一個結點，記錄基址
- 尾結點：最后一個結點，指向 null
插入洗掉
-
與陣列相比，鏈表的插入洗掉不需要搬移資料，時間復雜度為 O(1)
-
插入：在結點 p 后插入 結點 x
x.next = p.next; p.next = x; -
洗掉：洗掉結點 p 后續第一個結點
if(p.next != null) { p.next=p.next.next; }
隨機訪問
- 鏈表的資料不是連續存盤的，無法使用類似于陣列的尋址方法進行隨機訪問，而是要從頭遍歷，直到找到相應結點
- LinkedList 內部使用雙向鏈表結構，用 get( ) 隨機訪問時，需要從頭部正向或反向遍歷，效率低下
雙向鏈表、回圈鏈表
DoublyLinkedList、CircularLinkedList
-
雙向鏈表：每個結點除了后繼指標外，還存盤了前驅指標 previous
-
回圈鏈表：尾部結點指向頭部結點，適合處理環形結構的資料
-
雙向回圈鏈表：結合了雙向鏈表和回圈鏈表的特點
-
雙向鏈表比單鏈表靈活，洗掉性能更高
洗掉給定指標指向的結點時，單鏈表需要遍歷找到該結點的前驅結點，雙鏈表可以直接獲取前驅結點
這是一種用空間換時間的設計思想
鏈表實作 LRU 快取
鏈表實作 最近最久未使用淘汰演算法
維護一個單鏈表，越靠近鏈表尾部的結點，是越早之前訪問的，當有新資料被訪問時，從頭遍歷單鏈表
- 如果資料在鏈表中，遍歷得到對應結點，洗掉該節點，再插入到頭部
- 如果資料不在鏈表中
- 鏈表未滿時，直接插頭部
- 鏈表已滿時，洗掉尾部結點，再插入頭部
手寫鏈表
public class SinglyList {
// 哨兵結點
ListNode head = new ListNode(0);
// 在 pre 結點后插入 add 結點
public void add(ListNode pre, ListNode add) {
add.next = pre.next;
pre.next = add;
}
// 洗掉 node 后第一個結點
public void remove(ListNode node) {
if (node.next != null) {
node.next = node.next.next;
}
}
public String toString() {
String str = "head->";
ListNode temp = head;
while (temp.next != null) {
str += temp.next + " ";
temp = temp.next;
}
return str;
}
}
public class ListNode {
ListNode next;
int value;
public ListNode(int value) {
this.value = https://www.cnblogs.com/pgjett/p/value;
}
@Override
public String toString() {
return value +"";
}
}
public class SinglyListTest {
public static void main(String[] args) {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
// 創建單鏈表加入結點
SinglyList list = new SinglyList();
list.add(list.head, node1);
list.add(node1, node2);
list.add(node2, node3);
list.add(node3, node4);
// 列印
System.out.println(list);
}
}
head->1 2 3 4
- 理解指標的含義：指向變數的記憶體地址
- 警惕指標丟失：插入節點時，注意操作順序
- 利用哨兵結點簡化編程
- 當鏈表中沒有結點時，插入操作不能簡單使用上文中的方法，當鏈表只有一個結點時，洗掉操作也需要特殊處理
- 引入哨兵結點，無論鏈表是否為空，head 指向哨兵結點， 插入洗掉操作可以統一代碼邏輯
- 把有哨兵的鏈表稱為帶頭鏈表
- 注意邊界條件處理：留意鏈表為空時、只有一個結點時、只有兩個結點時、處理頭尾結點時，能否正常作業
- 多練習常見的鏈表操作
單鏈表反轉
public static void reverse(SinglyList list) {
SinglyList result = new SinglyList();
ListNode temp = list.head;
while (temp.next != null) {
temp = temp.next;
result.add(result.head, new ListNode(temp.value));
}
System.out.println(result);
}
求中間結點
快慢指標法，結點數分奇偶兩種情況
public static void middle(SinglyList list) {
ListNode quick = list.head, slow = list.head;
boolean isEven = true;//結點是否為偶數個
while (quick.next != null) {
if (quick.next.next != null) quick = quick.next.next;//偶數
else {//奇數
quick = quick.next;
isEven = false;
}
slow = slow.next;
}
if (isEven) System.out.println(slow + "," + slow.next);
else System.out.println(slow);
}
洗掉倒數第 n 個結點
public static void delete(SinglyList list, int n) {
ListNode p = list.head;
int len = 0;
while (p.next != null) {
p = p.next;
len++;
}
p = list.head;
for (int i = 0; i < len - n; i++) {
p = p.next;
}
list.remove(p);
System.out.println(list);
}
環的檢測
快慢指標法，快慢指標重復則有環
也可以使用一個 Set 去裝結點，判斷是否重復
public static void circle(SinglyList list) {
ListNode quick = list.head, slow = list.head;
while (true) {
quick = quick.next.next;
if (quick == null) {
System.out.println("have no circle");
break;
}
slow = slow.next;
if (quick == slow) {
System.out.println("have circle");
break;
}
}
}
兩個有序鏈表合并
帶頭鏈表遍歷時需要注意起始結點
public static void merge(SinglyList l1, SinglyList l2) {
SinglyList result = new SinglyList();
ListNode tail = result.head;
ListNode head1 = l1.head;
ListNode head2 = l2.head;
while (head1.next != null || head2.next != null) {
if (head1.next != null && head2.next != null) {
if (head1.next.value < head2.next.value) {
head1 = head1.next;
result.add(tail, new ListNode(head1.value));
tail = tail.next;
} else {
head2 = head2.next;
result.add(tail, new ListNode(head2.value));
tail = tail.next;
}
}
if (head1.next == null && head2.next != null) {
head2 = head2.next;
result.add(tail, new ListNode(head2.value));
tail = tail.next;
}
if (head1.next != null && head2.next == null) {
head1 = head1.next;
result.add(tail, new ListNode(head1.value));
tail = tail.next;
}
}
System.out.println(result);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/90064.html
標籤：其他