雙鏈表程式碼實現和講解
- 2019 年 10 月 3 日
- 筆記
1、什麼是鏈表
請移步看我前一篇https://www.cnblogs.com/han200113/p/11549338.html
2、雙鏈表和單鏈表有什麼不同？
- 雙鏈表相比單鏈表的date域(節點內容)和next(指向下一個節點)多了一個pre(指向前一個節點)
- 單鏈表只能向後或向後查找，而雙鏈表由於有節點pre，可實現向前和向後查找
- 單鏈表的刪除需要藉助前一個節點，雙鏈表可改變自身前後節點的指向實現自我刪除（詳情看程式碼部分）
3、程式碼實現講解
3.1 添加操作
循環遍歷到鏈表最後和單鏈表一樣，之後的添加操作除了將當前節點添加到最後，還要把當前節點的pre指向前一個節點，這樣才能實現前進後退
temp.next=personNode;//將當前節點添加到最後一位 personNode.pre=temp;
//添加操作 public void add(PersonNode personNode){ //head節點不能動，需要一個節點進行輔助遍歷 PersonNode temp=head; while (true){ if (temp.next==null){ //遍歷鏈表到結尾，跳出循環執行添加操作 break; } temp=temp.next; //輔助節點後移 } temp.next=personNode;//將當前節點添加到最後一位 personNode.pre=temp; }
3.2 順序添加
順序添加我用的單鏈表的順序添加方式也可以，
pnode.pre=temp;
這句添加與否不影響，希望大神指點
//順序添加 public void addBySort(PersonNode pnode){ //先頂一個指示 PersonNode temp=head; boolean flag=false; while (true){ if (temp.next==null){ //System.out.println("add遍歷已經結束"); break; } if (pnode.no<temp.next.no){ break; } else if (pnode.no==temp.next.no){ flag=true; break; } temp=temp.next; } if (flag){ System.out.println("節點已經存在"); }else { pnode.next=temp.next; temp.next=pnode; pnode.pre=temp; } }
3.3 修改操作
和單鏈表一樣，這裡不再說了，不理解的可以看下我前一篇單鏈表的隨筆
//修改 public void UpdateNode(PersonNode personNode){ if (head.next==null){ System.out.println("別修改了，這是空鏈表"); return; } PersonNode temp=head.next; boolean flag=false; while (true){ if (temp==null){ break; } if (temp.no==personNode.no){ flag=true; break; } temp=temp.next; } if (flag){ temp.no=personNode.no; temp.name=personNode.name; }else{ System.out.println("沒找到，不改了"); } }
3.4 刪除 (重點)
先看一下單鏈表怎麼刪除的，這裡用前一個節點直接指向下下個節點，孤立它，它就被記憶體回收了
temp.next=temp.next.next;
我們這裡怎麼實現的自我刪除呢？
temp.pre.next=temp.next;//將要刪除節點的前節點的next指向該節點的下一個節點 temp.next.pre=temp.pre;//將要刪除節點的下一個節點的pre指向該節點的前一個
還需要注意，如果刪除的是最後一個：
如果還用上面的會出現空指針異常，為什麼？
temp已經是最後一個，temp.next不就是空嗎，那temp.next.pre是什麼，空的前一個？
所以這裡加了個判斷條件if條件
//刪除 public void removeNode(int num){ PersonNode temp=head.next;//如果不用next，每次temp定位就是前一個節點 boolean flag=false; while (true){ if (temp==null){//遍歷結束 break; } if (temp.no==num){ flag=true; break; } temp=temp.next; } if (flag){ temp.pre.next=temp.next; if (temp.next!=null){ temp.next.pre=temp.pre; } }else{ System.out.println("抱歉，沒有找到"); } }
3.5 列表
和單鏈表一樣，不在多說
//列表 public void list(){ if (head.next==null){ System.out.println("還找列表？這是個空的"); return; } PersonNode temp=head.next; while (true){ if (temp==null){ System.out.println("好的您已經遍歷完了"); break; } System.out.println(temp); temp=temp.next; } }
