数据结构之双向链表
例如：现有双向链表TwoWayLinked中存储着1，2，3，4四个元素，那么集合对象中会有4个节点A、B、C、D，由上述结构可以知道，节点A中存储着元素1和节点B；节点B中存储着元素2和节点A和节点C，节点C中存储着元素3和节点B和节点D，节点D中存储着元素4和节点C。如果现在要在元素2和3中间插入一个元素5；过程如下：
1、创建节点E，E中存储元素5
2、将E中的上一个节点赋值为节点B
3、将B中的下一个节点修改为节点E
4、将E中的下一个节点赋值为节点C
5、将C中的上一个节点修改为节点E
从上述过程看，插入时没有节点位置移动的操作，所以效率比较高；删除的过程和插入过程相反
实例代码：
/**
* TwoWayLinked类
* 演示双向链表这一数据结构的实现
* @author 学霸联盟 - 赵灿
*/
public class TwoWayLinked {
// 用于存储链表的第一个节点
private Node first = null;
// 用于存储链表的最后一个节点
private Node last = null;
// 用于存储集合长度
private int size = 0;
//添加元素的方法
public void add(Object obj){
//创建节点对象
Node node = new Node();
//节点中存储添加的元素
node.element = obj;
//判断第一个节点是否为null
if (first == null) {
//第一个节点为说明是第一次添加元素
first = node;
//将第一个节点的前一个和后一个节点都设置成自己
first.pre = node;
first.next = node;
}
//判断最后一个节点是否为null
if(last == null){
/*
* 如果最后一个节点也为null时
* last和first存储的是同一个Node对象的地址
*/
last = node;
}else{
//如果最后一个节点不为null
//新创建的节点前一个节点应该是上一次的最后一个节点
node.pre = last;
//新创建的节点下一个节点存储自身
node.next = node;
//此时last中保存的还是上一次添加元素时的最后一个节点
//所以它的下一个节点应该设置为当前新建的节点
last.next = node;
//然后将last设置为当前新建的节点
last = node;
}
//添加元素，长度加1
size++;
}
/**
* 根据下标获取元素
*/
public Object get(int index) {
//首先判断传入的下标是否超出长度
if (index < size) {
/*
* 声明一个Node类型的变量tagNode，并设置为first
* 表示寻找的时候从第一个节点开始找
*/
Node tagNode = first;
for (int i = 0; i < index; i++) {
//获取下一个节点，等价于i+1
tagNode = tagNode.next;
}
//获取找到的节点中的元素
return tagNode.element;
}
//如果传入的下标大于或等于长度，返回null
return null;
}
/**
* 节点类（私有的成员内部类）
*
* @author 学霸联盟 - 赵灿
*/
private class Node {
// 自身类型的变量，用于存储前一个节点
Node pre;
// 自身类型的变量，用于存储后一个节点
Node next;
// Object类型的变量，用于存储元素
Object element;
}
}
/**
* TwoWayLinkedTest类
* 用于测试双向链表
* @author 学霸联盟 - 赵灿
*/
public class TwoWayLinkedTest {
public static void main(String[] args) {
//创建双线链表的对象
TwoWayLinked twl = new TwoWayLinked();
//向链表中添加值
twl.add(1);
twl.add(2);
twl.add(3);
twl.add(4);
//获取下标为2的值
Object element = twl.get(2);
//输出值
System.out.println(element);
}
}
运行结果：
3