|
前段时间刚刚学习了单向链表我写的关于学习单向链表的心得，单向链表其实比较简单，也是很常用的一种数据结构，单向链表相较于数组来说的话它的增加和删除都比较方便，但是单向链表在删除节点的时候吧总是得先获取要删除的节点的前一个节点，所以我们这里学习双向链表，使得在对链表进行增删改查时更加方便。
双向链表
可能大家一听到双向链表的时候还是会被它吓到，觉得这是一个很难的数据结构，其实双向链表就是在单向链表的基础上多增加了一个指针而已，这个指针指向当前节点的前一个节点，如下图  所以实现双向链表只要在单向链表的基础上进行修改即可，对于单向链表来说只要断开一条链子即可，而双向链表则需要断开两条，然后在相应的连接就可以实现了。
下面我们来用代码实现
创建节点，我们任然根据创建水浒英雄来创建相应的节点，与单项链表所不同的是我们需要节点中我们需要一个新的指针pre指向当前节点的前一个节点。
//创建链表节点
class HeroNode2{
//创建英雄的编号
int no;
//英雄的名字
String name;
//英雄的外号
String nickName;
//指向前一个节点
HeroNode2 next;
//指向后一个节点
HeroNode2 pre;
//创建构造器
public HeroNode2(int no, String name, String nickName) {
// TODO Auto-generated constructor stub
this.no = no;
this.name = name;
this.nickName = nickName;
}
//重写toString方法
@Override
public String toString() {
return "HeroNode2 [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
}
}
实现链表的添加，添加与单链表很像，只是需要将前后两个指针分别指向前一个节点和后一个节点。
class DoubleLinkedList{
//创建链表的头节点
HeroNode2 headHeroNode2 = new HeroNode2(0, "", "");
//返回头节点
public HeroNode2 getHeadHeroNode2() {
return headHeroNode2;
}
//添加链表节点
public void add(HeroNode2 heNode2) {
HeroNode2 tempNode2 = headHeroNode2;
while(true) {
if (tempNode2.next == null) {
break;
}
tempNode2 = tempNode2.next;
}
//当到达链表最后的时候将新的节点添加进来
tempNode2.next = heNode2;
heNode2.pre = tempNode2;
}
}
按顺序添加结点，也就是我创建节点时并没有按照顺序去创建节点，但是形成的链表确是一个有序的链表，也就是链表会自动按照一定的顺序去排序，我这里是按照从小到大的顺序排列的。
//按照编号顺序添加节点
public void insert(HeroNode2 node2) {
HeroNode2 tempHeroNode2 = headHeroNode2;
boolean flag = false;
while(true)
{
//找到链表的末尾都没有比他更大的编号，所以插入到链表的末尾即可
if (tempHeroNode2.next == null) {
break;
}
if (tempHeroNode2.next.no > node2.no) {
break;
}
else if (tempHeroNode2.no == node2.no) {
flag = true;
break;
}
tempHeroNode2 = tempHeroNode2.next;
}
if (flag) {
System.out.println("无法插入两个编号相同的节点！！！");
return;
}
else {
node2.next = tempHeroNode2.next;
/**需要去判断此时这个节点是不是要插在最后
* 如果是的话则表明已经到了链表的末尾，所以新插入的节点不会有后继节点了
* 也就是说此时的tempHeroNode2.next == null要插入的节点在它的后面比它要大
* 那么它的pre就应该指向它前面的节点，而不会去指向node2
*/
if (tempHeroNode2.next != null) {
tempHeroNode2.next.pre = node2;
}
tempHeroNode2.next = node2;
node2.pre = tempHeroNode2;
}
}
删除节点，删除节点与单链表有所不同，单链表必须找到要删除节点的前一个节点才可以，而双向链表则可以直接删除它自己本身
//删除节点
public void delNode(int no) {
if (headHeroNode2.next == null) {
System.out.println("链表为空！");
return;
}
//因为双向链表可以删除自身，所以直接从他本身开始就可以了
HeroNode2 tempNode2 = headHeroNode2.next;
boolean flag = false;
while(true)
{
//已经找到链表最后的节点的最后
if (tempNode2 == null) {
break;
}
if (tempNode2.no == no) {
flag = true;
break;
}
//如果没找到就继续向后找
tempNode2 = tempNode2.next;
}
if (flag) {
tempNode2.pre.next = tempNode2.next;
/*如果此时要删除的节点是最后一个节点，
那么该节点的就不会再有后继节点，所以该节点的next = null
那么这里就需要去判断，否则就会报空指针异常的错误*/
if (tempNode2.next != null) {
tempNode2.next.pre = tempNode2.pre;
}
}
else {
System.out.println("没有找到要删除的节点！");
return;
}
}
修改节点信息，与单向链表中的一样，遍历整个双向链表，如果找到和所要修改的节点相同的编号的话就把修改之后的值赋值给那个节点完成修改
//修改双向链表中的数据
public void modify(HeroNode2 newNode2) {
HeroNode2 tempNode2 = headHeroNode2;
boolean flag = false;
if (headHeroNode2.next == null) {
return;
}
while(true)
{
//如果遍历到末尾还没有找到的话说明没有这个节点
if (tempNode2.next == null) {
break;
}
if (tempNode2.no == newNode2.no) {
flag = true;
break;
}
tempNode2 = tempNode2.next;
}
if (flag) {
tempNode2.name = newNode2.name;
tempNode2.nickName = newNode2.nickName;
}
else {
System.out.println("对不起，并没有找到您要修改的节点");
}
}
遍历双向链表
//遍历链表节点
public void showList() {
if (headHeroNode2.next == null) {
System.out.println("这是一个空链表！");
return;
}
HeroNode2 tempNode2 = headHeroNode2.next;
while(true)
{
if (tempNode2 == null) {
break;
}
//不为空的时候直接打印节点信息
System.out.println(tempNode2);
tempNode2 = tempNode2.next;
}
}
测试代码
public class DoubleLinkedListDemo {
public static void main(String[] args) {
// TODO Auto-generated method stub
HeroNode2 heroNode1 = new HeroNode2(1, "宋江", "及时雨");
HeroNode2 heroNode2 = new HeroNode2(2, "卢俊义", "玉麒麟");
HeroNode2 heroNode3 = new HeroNode2(3, "吴用", "智多星");
HeroNode2 heroNode4 = new HeroNode2(4, "林冲", "豹子头");
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.insert(heroNode3);
doubleLinkedList.insert(heroNode2);
doubleLinkedList.insert(heroNode1);
doubleLinkedList.insert(heroNode4);
// doubleLinkedList.add(heroNode1);
// doubleLinkedList.add(heroNode2);
// doubleLinkedList.add(heroNode3);
// doubleLinkedList.add(heroNode4);
doubleLinkedList.showList();
System.out.println();
doubleLinkedList.delNode(2);
System.out.println("删除后的链表的情况是！！！");
doubleLinkedList.showList();
System.out.println("修改后的链表情况为！！！");
HeroNode2 newHeroNode2 = new HeroNode2(3, "无用", "没啥用");
doubleLinkedList.modify(newHeroNode2);
doubleLinkedList.showList();
}
}
总结：其实双向链表和单向链表相比改变并不是很大，也只是多了一个指向前一个节点的指针而已，变化最大的也就是自动按顺序添加节点和删除节点，需要将前面的和后面的节点都进行连接，在连接的同时需要注意的是要判断是不是在链表的末尾，如果是在末尾的话就要注意当前节点是没有后继节点的，也就是说它的next=null当然也不会有pre指针啦，所以要注意小心不要报出空指针异常哦。
|