java数据结构之双向链表

前言

在前几个章节中，介绍了单向链表及其用法，但是单向链表只能够向某一个特定的方向进行操作，我们大家思考一下，如果将这里的链表进行双向操作那会变成什么样的呢？

1 双向链表的简述

在阐述双向链表之前，先阐述一下单向链表的结构。
单向链表中的节点，分为data域和next域，一个用来存储数据，另一个用来指向下一个节点。说到这，大家是不是对双向链表节点的构造有了一些思路了呢？我是不是可以将这里的节点，再给他加上一个节点，用来指向上一个节点，此时，链表的节点既能够指向上一个节点也能够变成下一个节点。

2 双向链表功能实现

2.1 思路分析

将节点加工成一个双向的，其它的代码结构和单向链表的代码结构类似。

2.2 代码功能实现

其以下代码需要特别注意的点：遍历链表时需要有一个临时的指针 temp，在写while循环时一定要特别注意出口

以下代码主要是实现链表功能的curd功能

package com.haiyi.linkedlist;public class DoubleLinkedListDemo {public static void main(String[] args) {// 创建节点HeroNode2 heroNode1 = new HeroNode2(1, "宋江", "及时雨");HeroNode2 heroNode2 = new HeroNode2(2, "卢俊义", "玉麒麟");HeroNode2 heroNode3 = new HeroNode2(3, "吴用", "智多星");HeroNode2 heroNode4 = new HeroNode2(4, "林冲", "豹子头");// 创建链表DoubleLinkedList linkedList = new DoubleLinkedList();linkedList.add(heroNode1);linkedList.add(heroNode2);linkedList.add(heroNode3);linkedList.add(heroNode4);HeroNode2 newHeroNode2 = new HeroNode2(4, "林冲----", "豹子头-----");linkedList.update(newHeroNode2);linkedList.del(1);linkedList.list();}}class DoubleLinkedList {private HeroNode2 head = new HeroNode2(0, null, null);public HeroNode2 getHead() {return head;}// 在双向链表的末尾添加节点public void add(HeroNode2 node) {// 对链表进行遍历HeroNode2 temp = head;while (true) {if (temp.next == null) {break;}temp = temp.next;}// 添加temp.next = node;node.pre = temp;}// 删除节点public void del(int no) {if (head.next == null) {System.out.println("链表为空");return;}boolean flag = false;HeroNode2 temp = head;while (true) {if (temp == null) {break;}if (temp.no == no) {flag = true;break;}temp = temp.next;}if (flag) {temp.pre.next = temp.next;if (temp.next != null) {temp.next.pre = temp.pre;}}}// 修改节点的数据public void update(HeroNode2 newHeroNode) {if (head.next == null) {System.out.println("链表为空");return;}// 默认不可以进行修改数据boolean flag = false;HeroNode2 temp = head;while (true) {if (temp == null) {break;}if (temp.no == newHeroNode.no) {flag = true;break;}temp = temp.next;}if (flag) {temp.name = newHeroNode.name;temp.nickName = newHeroNode.nickName;} else {System.out.printf("该英雄的编号 %d 不存在", newHeroNode.no);}}// 显示链表所有数据public void list() {// 判断链表是否为空if (head.next == null) {System.out.println("链表为空");}HeroNode2 temp = head.next;while (temp != null) {System.out.println(temp);temp = temp.next;}}
}class HeroNode2 {public int no;public String name;public String nickName;public HeroNode2 next;public HeroNode2 pre;public HeroNode2(int no, String name, String nickName) {super();this.no = no;this.name = name;this.nickName = nickName;}@Overridepublic String toString() {return "HeroNode2 [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";}
}

2.3 测试结果