线性表——双向链表

86 阅读 0 评论 57 点赞

我是靠谱客的博主和谐大侠，最近开发中收集的这篇文章主要介绍线性表——双向链表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

双向链表简介

双向链表是一种特殊的链表。

在单向链表中我们要查找下一个结点非常的方便，但是要查找上一个节点就困难了，双向链表克服了单链表的单向性这个缺点，

单链表和双向链表的区别

单链表：只能向一个方向遍历

双向链表：向两边都可以遍历。

双向链表的实现

为了找到节点和前驱，我们给节点增加一个指向其前驱的指针，如下图所示

既然单链表可以循环，那么双向链表也就可以循环，如下图所示即为双向循环链表

双向链表的基本操作

1.创建双向链表

创建双向链表和创建单链表大同小异，双向链表的结点有三个域，数据域、前驱和后继。

当链表为空时，头结点的前驱和后继都指向它自己，自己构成一个环。

当链表不为空时，除尾结点外，每个结点的前驱都指向它的前一个结点，后继均指向它的后一个结点，尾节点的后继指向头结点。

2.增加元素

把元素增加在链表最后。

① 创建一个新的节点

② 新结点的后继为头结点

③ 新结点的前驱为尾节点

④ 尾节点的后继为新结点

⑤ 头结点的前驱为新结点

⑥ 将尾指针移动到新结点上

把元素插在链表任意位置，如下图所示

① 创建新结点

② 遍历链表到达指定的位置 p

③ 新结点的后继等于 p 的后继

④ 新结点的后继（P的后继）的前驱等于新结点

⑤ 新结点的前驱等于 p

⑥ p 的后继等于新结点

3.删除元素

删除尾结点

① 尾节点的前驱的后继等于头结点

② 头结点的前驱等于尾节点的前驱

③ 尾指针向前移动一下

删除任意位置的元素

① 遍历链表到适当的位置 p (待删除的节点)

② p 的前驱的后继等于 p 的后继

③ p 的后继的前驱等于 p 的前驱

/**
* 结点类
*/
class Node2<T>{
/**
* 数据域
*/
T data ;
/**
* 前驱
*/
Node2<T> pre ;
/**
* 后继
*/
Node2<T> next ;
public Node2(){
this.data = null;
this.pre = null;
this.next = null;
}
public Node2(T data){
this.data = data;
this.pre = null;
this.next = null;
}
}
/**
* 链表
*/
class doubleCycle<T>{
/**
* 头结点
*/
Node2<T> head;
/**
* 尾指针
*/
Node2<T> last;
/**
* 双向循环链表的长度
*/
int size;
public doubleCycle(){
head = new Node2<T>();
last = head;
head.next = head;
head.pre = head;
size = 0;
}
/**
* 增加一个元素
* @param data
*/
public void add(T data){
Node2<T> node = new Node2<T>(data);
last.next = node;
node.pre = last;
node.next = head;
head.pre = node;
last = node;
size++;
}
/**
* 删除一个元素
* @param data
* @return
*/
public boolean delete(T data){
Node2<T> p = head.next;
while(p != head){
if(p.data == data){
if(p == last){//如果是最后一个元素被删除，则要移动尾指针。
last = p.pre;
}
p.next.pre = p.pre;
p.pre.next = p.next;
size--;
return true;
}
p = p.next;
}
return false;
}
public void show(){
Node2<T> p = head.next;
while(p != head){
System.out.print(p.data+" ");
p = p.next;
}
System.out.println();
}
public void show2(){
Node2<T> p = last;
while(p != head){
System.out.print(p.data+" ");
p = p.pre;
}
System.out.println();
}
}
public class demo5 {
public static void main(String[] args){
doubleCycle<Integer> link = new doubleCycle<Integer>();
link.add(84);	link.add(45);	link.add(75);
link.add(15);	link.add(11);	link.add(23);
link.add(29);	link.add(7);
link.show();	link.show2();
link.delete(45);
System.out.println("删除45");
link.show();	link.show2();	link.delete(11);
System.out.println("删除11");
link.show();	link.show2();	link.delete(7);
System.out.println("删除7");
link.show();	link.show2();
}
}

运行结果

84 45 75 15 11 23 29 7
7 29 23 11 15 75 45 84
删除45
84 75 15 11 23 29 7
7 29 23 11 15 75 84
删除11
84 75 15 23 29 7
7 29 23 15 75 84
删除7
84 75 15 23 29
29 23 15 75 84