public class DoubleLinkedLisrDemo { public static void main(String[] args) { // 测试 // 先创建节点 HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨"); HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟"); HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星"); HeroNode2 hero4 = new HeroNode2(4, "公孙胜", "入云龙"); // 创建双向链表 DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); doubleLinkedList.addByOrder(hero1); doubleLinkedList.addByOrder(hero4); doubleLinkedList.addByOrder(hero2); doubleLinkedList.addByOrder(hero3); doubleLinkedList.list(); } } /** * 双向链表 */ class DoubleLinkedList { // 先初始化头节点,头节点不要动,不存放具体的数据 public HeroNode2 head = new HeroNode2(0, "", ""); /** * 获取头节点 */ public HeroNode2 getHead() { return head; } /** * 修改节点数据(与单向链表一样) * * @param heroNode */ public void update(HeroNode2 heroNode) { if (head.next == null) { // 空链表 System.out.println("链表为空~"); return; } // 定义辅助变量,存储头节点 HeroNode2 temp = head; boolean flag = false; while (true) { if (temp.next == null) { //遍历结束 break; } if (temp.no == heroNode.no) { // 找到对应位置 flag = true; break; } temp = temp.next; } if (flag) { temp.name = heroNode.name; temp.nickname = heroNode.nickname; } else System.out.println("未找到需修改的数据~"); } /** * 删除双向链表的节点 * 说明:双向链表找到待删除的节点直接跨越即可,单向链表需要找到待删除节点的前一个节点 * * @param no */ public void delete(int no) { if (head.next == null) { System.out.println("链表为空~"); return; } HeroNode2 temp = head.next; boolean flag = false; // 标志是否找到待删除节点 while (true) { if (temp == null) // 找到了最后节点的下一个节点 break; if (temp.no == no) { // 找到待删除节点的前一个节点temp flag = true; break; } temp = temp.next; } if (flag) { temp.pre.next = temp.next; // 跨越待删除的数据,待删除的数据会被JVM回收 if (temp.next != null) { // 防止指针走到尾端后再next出现空指针异常 temp.next.pre = temp.pre; } } else System.out.println("待删除的节点不存在~"); } /** * 添加到双向链表的尾部 * * @param heroNode */ public void add(HeroNode2 heroNode) { // head不能动,需要一个辅助遍历temp HeroNode2 temp = head; while (temp.next != null) { temp = temp.next; } // 循环结束,temp到达尾部 temp.next = heroNode; // 尾端的next指向新增节点 heroNode.pre = temp; // 新增节点的pre指向尾端 } /** * 按照编号顺序插入 * * @param heroNode */ public void addByOrder(HeroNode2 heroNode) { // head不能动,需要一个辅助遍历temp HeroNode2 temp = head; boolean flag = false; // 标识添加的编号是否存在,默认为false while (true) { if (temp.next == null) { // 边界条件独立处理 break; } if (temp.next.no > heroNode.no) { // temp后面插入 break; } else if (temp.next.no == heroNode.no) { // 已经存在,无法加入 flag = true; break; } temp = temp.next; // 移动指针 } if (flag) { // 无法插入 System.out.println("无法插入~"); } else { heroNode.next = temp.next; // 先将当前节点接上去 heroNode.pre = temp; if (temp.next != null) { temp.next.pre = heroNode; // 双向连接链表 } temp.next = heroNode; } } /** * 显示链表 */ public void list() { if (head.next == null) { System.out.println("链表为空~"); return; } // 记录头节点 HeroNode2 temp = head.next; // 头结点指示,实际数据从head2.next开始 while (temp != null) { // 到达尾部 System.out.println(temp); // 输出数据 temp = temp.next; // 指针后移 } } } /** * 定义HeroNode2,每个HeroNode对象就是一个节点 */ class HeroNode2 { public int no; public String name; public String nickname; public HeroNode2 next; // 指向下一个节点(默认为null) public HeroNode2 pre; // 指向下一个节点(默认为null) /** * 构造方法 * * @param no 编号 * @param name 姓名 * @param nickname 昵称 */ public HeroNode2(int no, String name, String nickname) { this.no = no; this.name = name; this.nickname = nickname; } /** * 重写toString()方法为了显示 * * @return */ @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickname='" + nickname + '\'' + '}'; } }