为什么需要双向链表？
单链表的结点都只有一个指向下一个结点，单链表的数据元素无法直接访问其前驱元素，所以逆序访问单链表中元素极其耗时；思想有点类似使用空间复杂度换时间复杂度。
双向链表：在单链表的结点中增加一个指向其前驱的pre指针；该链表中第一个结点的前趋结点为NULL，最后一个结点的后继结点为NULL 。
双向链表具有单链表的所有操作：添加元素、插入元素、删除元素、遍历元素；
双向链表应用实例
使用带head头的双向链表实现 –水浒英雄排行榜
管理单向链表的缺点分析:
单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点(认真体会).示意图帮助理解删除示意图如下：
基本思路： 分析 双向链表的遍历，添加，修改，删除的操作思路===》代码实现
遍历 方和 单链表一样，只是可以向前，也可以向后查找添加 (默认添加到双向链表的最后) (1) 先找到双向链表的最后这个节点 (2) temp.next = newHeroNode (3) newHeroNode.pre = temp;修改 思路和 原来的单向链表一样.删除 (1) 因为是双向链表，因此，我们可以实现自我删除某个节点 (2) 直接找到要删除的这个节点，比如temp (3) temp.pre.next = temp.next (4) temp.next.pre = temp.pre;代码实现：
/** * 双向链表 * @author 骑着蜗牛追火箭 * */ public class DoubleLinkedListDemo { 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.add(hero1); doubleLinkedList.add(hero2); doubleLinkedList.add(hero3); doubleLinkedList.add(hero4); System.out.println("遍历双向链表"); doubleLinkedList.list(); //测试修改 HeroNode2 newHeroNode=new HeroNode2(4, "公孙胜", "入云龙"); doubleLinkedList.update(newHeroNode); System.out.println("修改后的双向链表"); doubleLinkedList.list(); //测试删除 doubleLinkedList.delete(3); System.out.println("删除后的双向链表"); doubleLinkedList.list(); //测试根据序号进行添加 HeroNode2 hero5=new HeroNode2(3, "吴用", "智多星"); doubleLinkedList.addByNo(hero5); System.out.println("根据编号进行添加后的链表"); doubleLinkedList.list(); } } //创建双向链表 class DoubleLinkedList{ //创建一个头结点,头结点中不存放任何的数据 HeroNode2 head=new HeroNode2(0, "", ""); //返回头结点 public HeroNode2 getHead() { return head; } //添加结点，直接向双向链表尾部添加 public void add(HeroNode2 newHeroNode) { //由于头结点不能动，所以我们定义一个临时变量temp指向它 HeroNode2 temp=head; //循环找到最后一个结点 while(true) { //判断temp的下一个结点是否为空，如果是空的话，我们就找到了最后一个结点，直接退出 if(temp.next==null) { break; } temp=temp.next;//将指针后移 } //找到最后一个结点之后，我们将数据添加到其后边 temp.next=newHeroNode; newHeroNode.pre=temp; } //添加英雄结点，根据编号顺序进行添加 public void addByNo(HeroNode2 node) { //因为头结点不能动，所以定义一个临时变量存放头结点 HeroNode2 temp=head; //定义一个flag，用于判断添加的编号是否存在 boolean flag=false; //循环遍历结点 while(true) { //遍历到最后一个结点，退出 if(temp.next==null) { break; }else if(temp.next.no>node.no) { //当下一个结点的no大于我们所要插入的结点编号， //这时候我们就可以将要插入的结点放在temp后 //找到该要插入的结点，退出 break; }else if(temp.next.no==node.no) {//如果编号相等，那就另flag==true flag=true; } //将指针后移 temp=temp.next; } //插入前我们需要判断链表中是否有该no if(flag==true) { System.out.printf("不能插入，链表中已经存在%d号英雄的信息",node.no); System.out.println(); }else { node.next=temp.next; temp.next=node; temp.next.pre=node; node.pre=temp; } } //根据结点的no修改结点信息，即no属性不能动（和单链表的修改基本一样） public void update(HeroNode2 newHeroNode) { //首先判断链表是否为空 if(head.next==null) { System.out.println("空链表！！！"); return ; } //定义一个flag，标志是否找到 boolean flag=false; //定义一个临时变量 HeroNode2 temp=head.next; while(true) { //判断是否到链表结尾 if(temp==null) { break; }else 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); System.out.println(); } } //删除指定no英雄结点信息 /** * 思路： * 1、不同于单链表的是我们可以找到要删除的结点， * 将要删除的结点的前一个结点指针指向要删除结点的下一个结点 * temp.pre.next=temp.next * 将要删除的结点的下一个结点指针指向要删除结点的前一个结点（当不是删除最后一个结点时） * temp.next.pre=temp.pre * 2、当删除最后一个节点时，temp.pre.next=temp.next没有毛病 * temp.pre.next=temp.next如何不加条件就会空指针异常 * 所以我们需要在其前边加上if(temp.next!=null) * * @param no */ public void delete(int no) { //定义一个临时变量 HeroNode2 temp=head.next; boolean flag=false;//是否找到要删除结点 while(true) { //判断是否到链表尾部 if(temp==null) { break; }else 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; } }else { System.out.printf("没有找到编号为%d的英雄信息",no); } } //遍历所有结点 public void list() { //用临时变量指向head的下一个结点 HeroNode2 temp=head.next; //循环遍历 while(true) { //先判断结点是否为空，为空直接退出 if(temp==null) { break; } //将结点打印出来 System.out.println(temp.toString()); //将结点指针后移 temp=temp.next; } } } //创建结点类 class HeroNode2{ int no; //英雄编号 String name; //英雄姓名 String nickname; //英雄昵称 HeroNode2 next; //指向下一个结点 HeroNode2 pre; //指向前一个结点 //创建构造器，初始化英雄结点 public HeroNode2(int no,String name,String nickname) { this.no=no; this.name=name; this.nickname=nickname; } //打印英雄结点信息 @Override public String toString() { return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; } }