双向链表
双向链表应用实例,双向链表的操作分析和实现
管理单向链表的缺点分析:
单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除 时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会).
分析了双向链表如何完成遍历，添加，修改和删除的思路
双向链表实现思路
分析 双向链表的遍历，添加，修改，删除的操作思路===》代码实现
遍历 方和 单链表一样，只是可以向前，也可以向后查找
添加 (默认添加到双向链表的最后)
(1) 先找到双向链表的最后这个节点
(2) temp.next = newHeroNode
newHeroNode.pre = temp;
修改 思路和 原来的单向链表一样. 4) 删除
(1) 因为是双向链表，因此，我们可以实现自我删除某个节点
(2) 直接找到要删除的这个节点，比如 temp
(3) temp.pre.next = temp.next
(4) temp.next.pre = temp.pre;
实现链表节点
/** * 双向链表要用的节点 * */ class ListNode { //排名 public int No; // 姓名 public String Name; //昵称 public String NickName; // 下一个节点 public ListNode next; //上一个节点 public ListNode pre; public ListNode(int hNo, String hName, String hNickName) { this.No = hNo; this.Name = hName; this.NickName = hNickName; } //方便输出语句输出 @Override public String toString() { return "HeroNode{" + "No=" + No + ", Name='" + Name + '\'' + ", NickName='" + NickName + '\'' + '}'; } }
双向链表实现
class DoubleLinkedList { //创建一个头结点 ListNode head = new ListNode(0, "", ""); public ListNode getHead() { return head; } public void setHead(ListNode head) { this.head = head; } //遍历链表 public void List() { if (head.next == null) { System.out.println("链表为空"); return; } //头节点不能动 这里我们用一个临时指针来记录 ListNode temp = head.next; while (true) { //遍历为空就代表找了最后一个节点 if (temp == null) { break; } //输出节点 System.out.println(temp); //后移一位 temp = temp.next; } } //加入双向链表 public void add(ListNode node) { //头节点不能动 这里我们用一个临时指针来记录 ListNode temp = head; //遍历链表 while (true) { //遍历为空就代表找了最后一个节点 //不为空就后移一位继续找 if (temp.next == null) { break; } //没有找到最后就后移 temp temp = temp.next; } //指向下一个节点 temp.next = node; //指向上一个节点 node.pre = temp; } //修改双向链表，和单向链表基本一致不需要过多的修改 //修改节点信息 public void updateNode(ListNode newlistnode) { if (head.next == null) { System.out.println("链表是空的"); } //这里是头节点不能修改，我用 temp 来指向头结点 ListNode temp = head.next; // 是否找到了no的标识 boolean flag = false; while (true) { //找到最后一个 if (temp == null) { break; } if (temp.No == newlistnode.No) { //如果等于 那么代表可以修改 flag = true; break; } temp = temp.next; } if (flag) { // true 修改信息 temp.NickName = newlistnode.NickName; temp.Name = newlistnode.Name; } else { System.out.printf("没有找到 %d 这个节点", newlistnode.No); } } /* * 双向链表删除 * 对于双向链表来说就不需要找到上一个节点来删除了， * 可以找到自己删除 * */ public void DeleteNode(int no) { if (head.next == null) { System.out.println("链表为空 不需要删除"); return; } ListNode temp = head.next; // 用来标注 是不是可以删除 boolean flag = false; while (true) { if (temp == null) { break; } if (temp.next.No == no) { flag = true; break; } temp = temp.next; } //根据flag 删除Node if (flag) { //找到的话就删除，这里我们只需要指向空 GC会回收 //temp.next = temp.next.next; 原先的单向链表删除现在在双向链表里就不好使了 /*将当前节点的上一个节点的下一个指向 指向当前节点的下一个节点 相当于向前指向的next 直接跨过当前的节点指向下一个节点*/ temp.pre.next = temp.next; /*将当前节点的下一个节点的上一个指向 指向当前节点的上一个节点，相当于向前的pre 直接快过当前的节点指向上一个 * 如果当前节点是最后一节点，就不执行后面这个将下一个节点的指向更改，不然会出现空指针 * */ if (temp.next != null) { temp.next.pre = temp.pre; } /*这两步 坐完相当于 此时的当前节点已经没有了指向 会被回收*/ } else { System.out.printf("要删除的 %d 没有找到", no); } } }
效果
总结
双向链表在之前的基础上：
对比单向链表 双向链表可以自己删除，
双线链表正反遍历更加的容易
