1 双向链表
1.1 双向链表介绍
相较单链表,双向链表除了data与next域,还多了一个pre域用于表示每个节点的前一个元素。这样做给双向链表带来了很多优势:
单向链表查找的方向只能是一个方向,而双向链表可以向前或者向后查找;
单链表如果想要实现删除操作,需要找到待删除节点的前一个节点。而双向链表可以实现自我删除。
双向链表结构示意图如下:
1.2 双向链表实现思路
与单链表实现类似,交集部分不再赘述,详情可参考文章:Java数据结构:单链表的实现与面试题汇总
遍历:
与单链表遍历方式一样,同时,双向链表可以支持向前和向后两种查找方式
添加:
添加到末尾
- 先找到双向链表最后一个节点
- cur.next = newNode;
- newNode.pre = cur;
按照no顺序添加
- 先判断该链表是否为空,如果为空则直接添加
- 如果不为空则继续处理
- 根据no遍历链表,找到合适的位置
- newNode.next = cur.next;
- cur.next = newNode;
- newNode.pre = cur;
修改操作与单链表实现步骤一致
删除操作:
- 双向链表可以实现自我删除
- 直接找到待删除的节点
- cur.pre.next = cur.next;
- cur.next.pre = cur.pre;
- 需要特别注意是否为最后一个元素,如果为最后一个元素,cur.next为null,此时使用cur.next.pre会出现空指针异常,所以,如果为最后一个元素,则该步骤可以省略,cur.next为null即可。
以删除红色的2号节点为例:
2 双向链表实现完整代码
2.1 节点类 Student.java
/** * @author 兴趣使然黄小黄 * @version 1.0 * 学生类节点 */ public class StudentNode { public String no; //学号 public String name; //姓名 public int age; //年龄 public StudentNode pre; //指向前一个节点 public StudentNode next; //指向下一个节点 //构造器 public StudentNode(String no, String name, int age ){ this.no = no; this.name = name; this.age = age; } //为了显示方便 @Override public String toString() { return "StudentNode{" + "no='" + no + ''' + ", name='" + name + ''' + ", age=" + age + '}'; } }
2.2 双向链表实现类 StudentDoubleLinkedList.java
/** * @author 兴趣使然黄小黄 * @version 1.0 * 学生双向链表的具体实现 */ public class StudentDoubleLinkedList { //定义头节点 private StudentNode head = new StudentNode("", "", 0); //获取头节点 public StudentNode getHead(){ return head; } //遍历双向链表的方法 public void showList(){ //判断链表是否为空 if (head.next == null){ System.out.println("当前链表为空"); return; } //遍历 使用辅助指针 StudentNode temp = head; while (temp != null){ //更新指针 temp = temp.next; if (temp.next == null){ System.out.print(temp); break; } System.out.print(temp + "--->"); } } //添加节点的方法 //添加到尾部 public void add(StudentNode newNode){ //先找到最后一个节点 StudentNode cur = head; while (true){ //到达最后退出循环 if (cur.next == null){ break; } //更新指针 cur = cur.next; } //添加操作 newNode.next = cur.next; //也可以省略,因为恒为null cur.next = newNode; newNode.pre = cur; } //添加节点的方法 //根据学号顺序添加 public void addByOrder(StudentNode newNode){ //如果当前链表为空,则直接添加 if (head.next == null){ head.next = newNode; newNode.pre = head; return; } //按照学号找到对应位置 StudentNode cur = head; boolean flag = false; //标识待添加的no是否存在 while (true){ if (cur.next == null){ //已经到达链表的尾部 break; } else if (Integer.parseInt(cur.next.no) == Integer.parseInt(newNode.no)){ //已经存在 flag = true; break; }else if (Integer.parseInt(cur.next.no) > Integer.parseInt(newNode.no)){ //位置找到 break; } cur = cur.next; } if (flag){ System.out.println("当前no已经存在,无法添加!"); }else { //添加操作 newNode.next = cur.next; cur.next = newNode; newNode.pre = cur; } } //根据no学号修改学生信息 public void update(StudentNode studentNode){ if (head.next == null){ System.out.println("当前链表为空, 无法修改"); return; } StudentNode temp = head.next; boolean flag = false; //表示是否找到节点 while (true){ if (temp == null){ break; } if (temp.no == studentNode.no){ flag = true; break; } temp = temp.next; } if (flag){ temp.name = studentNode.name; temp.age = studentNode.age; System.out.println("更新成功!"); }else { System.out.println("没有找到"); } } //从双向链表中删除节点 public void delete(String no){ //直接找到对应no的节点直接删除 StudentNode cur = head.next; boolean flag = false; //标记是否找到 while (true){ if (cur == null){ break; } if (cur.no.equals(no)){ flag = true; //找到了 break; } cur = cur.next; } if (flag){ //删除操作 //注意考虑最后一个节点后一个为空的情况 if (cur.next != null) { cur.next.pre = cur.pre; } cur.pre.next = cur.next; System.out.println("删除成功!"); }else { System.out.println( no + "节点不存在,无法删除!"); } } }
2.3 测试类 StudentDoubleLinkedListDemo.java
/** * @author 兴趣使然黄小黄 * @version 1.0 * 双向链表测试类 */ public class DoubleLinkedListDemo { public static void main(String[] args) { StudentDoubleLinkedList doubleLinkedList = new StudentDoubleLinkedList(); doubleLinkedList.addByOrder(new StudentNode("1", "黄小黄", 20)); doubleLinkedList.addByOrder(new StudentNode("3", "懒羊羊", 20)); doubleLinkedList.addByOrder(new StudentNode("2", "沸羊羊", 25)); doubleLinkedList.addByOrder(new StudentNode("4", "美羊羊", 15)); System.out.println("遍历:"); doubleLinkedList.showList(); //测试更新方法 System.out.println("n更新编号为4的信息后:"); doubleLinkedList.update(new StudentNode("4", "祢豆子", 14)); doubleLinkedList.showList(); //测试删除方法 System.out.println("n删除第一个和最后一个:"); doubleLinkedList.delete("1"); doubleLinkedList.delete("4"); doubleLinkedList.showList(); } }
2.4 结果
遍历:
StudentNode{no=’1′, name=’黄小黄’, age=20}—>StudentNode{no=’2′, name=’沸羊羊’, age=25}—>StudentNode{no=’3′, name=’懒羊羊’, age=20}—>StudentNode{no=’4′, name=’美羊羊’, age=15}
更新编号为4的信息后:
更新成功!
StudentNode{no=’1′, name=’黄小黄’, age=20}—>StudentNode{no=’2′, name=’沸羊羊’, age=25}—>StudentNode{no=’3′, name=’懒羊羊’, age=20}—>StudentNode{no=’4′, name=’祢豆子’, age=14}
删除第一个和最后一个:
删除成功!
删除成功!
StudentNode{no=’2′, name=’沸羊羊’, age=25}—>StudentNode{no=’3′, name=’懒羊羊’, age=20}
Process finished with exit code 0
3 双向链表小结
单向链表查找的方向只能为一个方向,双向链表解决了这个缺点,可以实现双向查找;
单链表进行删除操作必须找到待删除元素的前一个元素,才能完成删除操作。而双向链表就简单多了,只需要找到待删除的节点,进行自我删除;
本节介绍了双向链表的遍历、添加、按顺序添加、更新、删除方法的实现,可以尝试像单链表篇一样,尝试求有效节点数量,以及如何逆序输出双向链表加强练习!
以上就是Java数据结构之双向链表的实现的详细内容,更多关于Java数据结构双向链表的资料请关注IT俱乐部其它相关文章!