双链表代码实现和讲解
- 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; } }
