鏈表
一、鏈表(Linked List)介紹
鏈表是有序的列表，但是它在內存中式存儲如下
1) 鏈表是以節點的方式來存儲,是鏈式存儲
2) 每個節點包含 data 域， next 域：指向下一個節點.
3) 如圖：發現鏈表的各個節點不一定是連續存儲.
4) 鏈表分帶頭節點的鏈表和沒有頭節點的鏈表，根據實際的需求來確定
二、單鏈表
使用帶head頭的單向鏈表實現
源碼: 單鏈表
1，思路
準備 1)首先定義node節點對象 2)採用SingleLinkedList進行管理 3)在SingleLinkedList中定義head節點為new Node(-1,"","") 遍歷 1)定義臨時節點temp=head.next 2)while(temp!= null){temp=temp.next}遍歷並在其中打印temp 新增 1)定義一個臨時節點temp記錄到最後的位置 2)while(temp.next != null){temp=temp.next}移動指針 3)設置temp.next=node(新增的節點) 刪除 1)定義臨時節點temp=head，定義boolean flag為標識是否尋找到需要刪除的節點 2)while(temp.next != null){temp=temp.next}移動指針，判斷temp.next.no=no(輸入的節點id)為刪除節點的前一個節點並修改flag為刪除 3)判定 flag標識是否找到刪除節點，如果找到就執行temp.next=temp.next.next 修改 1)定義臨時節點temp=head，定義boolean flag為標識是否尋找到需要修改的節點 2)while(temp.next != null){temp=temp.next}移動指針，判斷temp.next.no==node.no(node為需要修改的節點)並修改flag為修改 3)判定 flag標識是否找到修改節點，如果找到就執行node.next=temp.next.next;temp.next=node
2，代碼實現
/** * 添加節點 */ public void add(Node node) { Node temp = head; while (true) { if (temp.next == null) { break; } temp = temp.next; } temp.next = node; } /** * 刪除節點 */ public void del(int no) { //臨時節點為需要刪除節點的前一個節點 Node temp = head; boolean flag = true; //標識是否已經尋找完畢 while (true) { //如果已經遍歷完畢 if (temp.next == null) { flag = false; break; } //找到需要刪除節點的上一個節點 if (temp.next.no == no) { break; } temp = temp.next; } if (!flag) { System.out.println("找不到需要刪除的節點!!!"); return; } //刪除對應的節點 temp.next = temp.next.next; } /** * 修改節點 */ public void update(Node node) { //臨時節點為需要修改節點的前一個節點 Node temp = head; //判斷是否在鏈表中找到對應的節點 boolean flag = true; while (true) { //沒有找到對應的節點 if (temp.next == null) { flag = false; break; } //找到對應的節點 if (temp.next.no == node.no) { break; } //後移 temp = temp.next; } if (!flag) { System.out.println("找不到需要修改的節點!!!"); return; } //修改 node.next = temp.next.next; temp.next = node; } /** * 遍歷單鏈表 */ public void list(){ //第一個節點 Node temp = head.next; while (true) { if (temp == null) { break; } System.out.println(temp); temp = temp.next; } }
View Code
3，單鏈表擴展(面試題)
思路
查找單鏈表中的倒數第k個節點 1)獲取鏈表的長度(新方法)，採用臨時變量count=0，定義臨時變量temp=head.next;while(temp!=null){count++;temp=temp.next}，將最終的count返回 2)使用num=length-k(倒數第k個)，定義temp=head.next，flag=true 3)while(temp!= null){temp=temp.next}，將num--，當num==0時則break並且修改flag為找到對應節點 4)判斷flag如果為找到狀態，則直接返回當前的temp 反轉單鏈表(改變鏈表結構) 1)定義一個新的頭節點reverse，定義指針cur=head.next，定義臨時節點temp=null 2)while(cur!=null){cur=cur.next}指針後移，指針後移之前先賦值temp=cur，然後將temp插入到reverse頭節點和reverse.next節點之間 3)最後將原頭節點的下一個節點指向新頭節點的下一個節點，head.next = reverse.next 反向遍歷(不改變鏈表結構) 1)定義棧Stack，定義臨時節點temp=head.next 2)while(temp!=null){temp=temp.next}遍歷，並將每個temp都push到棧 3)遍歷棧，pop棧中的元素
代碼
/** * 反向遍歷 */ public void reversePrint() { //定義棧作為保存 Stack<Node> nodes = new Stack<>(); Node temp = head; while (true) { if (temp.next == null) { break; } nodes.push(temp.next); temp = temp.next; } while (!nodes.empty()) { System.out.println(nodes.pop()); } } /** * 反轉（改變結構） */ public void reverse(){ //定義一個新的頭節點 Node reverse = new Node(-1,"",""); //指針 Node cur = head.next; //臨時變量為當前節點 Node temp = null; while (true) { if (cur == null) { break; } //當前值為指針指向的值 temp = cur; //指針後移 cur = cur.next; //當前節點為 頭節點的下一個接待你 temp.next = reverse.next; //頭節點的下一個節點為當前接待你 reverse.next = temp; } //將原始頭節點下一個節點指向 新頭節點的下一個節點 head.next = reverse.next; } /** * 查找單鏈表中的倒數第 k 個節點 */ public static Node getByNum(Node head,int num){ int k = getLength(head) - num; if (k < 0) { return new Node(-1,"k大於長度","-1"); } Node temp = head.next; //判斷是否找不到 boolean flag = false; while (true) { if (temp == null) { break; } if (k == 0) { flag = true; break; } k--; temp = temp.next; } if (!flag) { //越界了，k為負數 return new Node(-1,"k為負數","-1"); } return temp; } /** * 求單鏈表中有效節點的個數 */ public static int getLength(Node head){ int count = 0; Node temp = head.next; while (true) { if (temp == null) { break; } count++; temp = temp.next; } return count; }
View Code
三、雙向鏈表
源碼：雙向鏈表
1，思路
準備 1)首先定義node節點對象，存在next和pre兩個屬性 2)採用DoubleLinkedList進行管理 3)在DoubleLinkedList中定義head節點為new Node(-1,"","") 遍歷 1)定義臨時節點temp=head.next 2)while(temp!= null){temp=temp.next}遍歷並在其中打印temp 新增 1)定義一個臨時節點temp記錄到最後的位置 2)while(temp.next != null){temp=temp.next}移動指針 3)設置temp.next=node(新增的節點)，node.pre=temp(雙向關聯) 刪除(自我刪除) 1)定義臨時節點temp=head.next(需要被刪除的節點)，定義boolean flag為標識是否尋找到需要刪除的節點 2)while(temp!= null){temp=temp.next}移動指針，判斷temp.no=no(輸入的節點id)為刪除節點，temp.pre.next=temp.next，如果temp.next不為空則temp.next.pre=temp.pre，並修改flag為刪除 3)判定 flag標識是否找到刪除節點 修改 1)定義臨時節點temp=head.next，定義boolean flag為標識是否尋找到需要修改的節點 2)while(temp!= null){temp=temp.next}移動指針，判斷temp.no==node.no(node為需要修改的節點)，修改temp的屬性(或者修改next，pre指向)，並修改flag為修改,break 3)判定 flag標識是否找到修改節點，沒找到給出提示
2，代碼
private DoubleNode head = new DoubleNode(-1, "", ""); /** * 刪除節點 */ public void delete(int no) { if (no <= 0) { System.out.println("刪除節點的no不規範!!!"); return; } DoubleNode temp = head.next; boolean flag = false; while (temp != null) { if (temp.no == no) { temp.pre.next = temp.next; if (temp.next != null) { temp.next.pre = temp.pre; } flag = true; } temp = temp.next; } if (!flag) { System.out.println("需要被刪除的節點不存在"); } } /** * 修改節點 */ public void update(DoubleNode node) { if (node == null || node.no <= 0) { System.out.println("被修改的節點不規範!!!"); return; } DoubleNode temp = head.next; boolean flag = false; while (temp != null) { if (temp.no == node.no) { temp.name = node.name; temp.nickname = node.nickname; /*node.next = temp.next; node.pre = temp.pre; temp.pre.next = node; if (temp.next != null) { temp.next.pre = node; }*/ flag = true; } temp = temp.next; } if (!flag) { System.out.println("找不到節點!!!"); } } /** * 添加節點 */ public void add(DoubleNode node) { DoubleNode temp = head; while (true) { if (temp.next == null) { break; } temp = temp.next; } temp.next = node; node.pre = temp; } /** * 遍歷節點 */ public void list() { DoubleNode temp = head.next; while (true) { if (temp == null) { break; } System.out.println(temp); temp = temp.next; } }
View Code
四、環形鏈表(約瑟夫問題)
源碼:環形鏈表
1，應用場景
Josephu 問題為： 設編號為 1， 2， … n 的 n 個人圍坐一圈， 約定編號為 k（1<=k<=n） 的人從 1 開始報數， 數到 m 的那個人出列， 它的下一位又從 1 開始報數， 數到 m 的那個人又出列， 依次類推， 直到所有人出列為止， 由此產生一個出隊編號的序列。
2，創建環形鏈表
思路
準備 1)提前創建CircleNode對象為定義的節點 2)定義CircleLinkedList為環形鏈表的管理類 3)在CircleLinkedList中定義CircleNode first = null，定義鏈表的第一個節點 添加 1)判定first==null，如果為空則是第一次添加，那麼first=node，並且node.next=first 2)如果first節點不為空，定義temp=first節點，while(temp.next!=first){temp=temp.next}遍歷後移至first節點的前一個節點。 3)將node節點加到temp節點後first節點前，temp.next=node並且node.next=first 遍歷 1)定義temp=first，先打印first節點 2)while(temp.next!=first){temp=temp.next}打印temp.next
代碼
/** * 遍歷 */ public void show() { if (first == null) { System.out.println("當前鏈表為空鏈表!!!"); return; } CircleNode temp = first; System.out.printf("當前編號為%d\n", first.no); while (temp.next != first) { System.out.printf("當前編號為%d\n", temp.next.no); temp = temp.next; } } /** * 初始化環形隊列 */ public void init(int num) { if (num < 1) { System.out.println("初始化環形鏈表小於1，失敗!!!"); return; } for (int i = 1; i <= num; i++) { CircleNode circleNode = new CircleNode(i); add(circleNode); } } /** * 添加node */ public void add(CircleNode node) { if (node == null) { System.out.println("需要添加的節點不存在!!!"); return; } if (first == null) { first = node; node.next = first; } CircleNode temp = first; while (true) { if (temp.next == first) { break; } temp = temp.next; } temp.next = node; node.next = first; }
View Code
3，出圈
思路
1)獲取環形鏈表的總長度 2)定義出圈的方法需要接收step步長和start開始位置 3)定義cur=first需要出圈的節點，定義pre=first出圈的前一個節點while(pre.next!=first){pre=pre.next} 4)for循環start次，同時移動cur=cur.next和pre=pre.next 5)while(cur.next!=cur){...cur=cur.next}移動cur指針。在while循環中增加for循環step-1次，每次將pre和cur都後移，那麼移動完成之後設置pre.next=cur.next這樣就會去除cur 6)留存的就是最後的cur
代碼
/** * 出圈 * * @param step 步長 * @param start 開始的位置 */ public void out(int step, int start) { int length = getLength(); if (length < 1 || step < 1 || start > length) { System.out.println("參數不合規!"); return; } //定義需要出圈的節點 CircleNode cur = first; //需要出圈節點的前一個節點 CircleNode pre = first; while (pre.next != first) { pre = pre.next; } //開始的位置 for (int i = 0; i < start; i++) { pre = pre.next; cur = cur.next; } while (cur.next != cur) { for (int i = 0; i < step-1; i++) { pre = pre.next; cur = cur.next; } System.out.printf("出圈編號為:%d\n",cur.no); pre.next = cur.next; cur = cur.next; } System.out.printf("出圈編號為:%d\n",cur.no); } /** * 獲取環形鏈表的長度 */ public int getLength() { if (first == null) { return 0; } int count = 1; CircleNode temp = first; while (temp.next != first) { count++; temp = temp.next; } return count; }
View Code
