前言:前面介绍了循环链表,虽然循环链表可以解决单链表每次遍历只能从头结点开始,但是对于查询某一节点的上一节点,还是颇为复杂繁琐,所以可以在结点中加入前一个节点的引用,即双向链表
双向链表:在链表中,每一个节点都有对上一个节点和下一个节点的引用或指针,即从一个节点出发可以有两条路可选择。
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针或引用,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
特性:
1、创建节点类Node,其中有三个属性pre、object、next,pre为上一个节点的引用,也叫作前驱节点,object存储数据,next为下一个节点的引用,也叫作后继节点:
public class BothwayLoopChain<T> {
//头结点直接引用
private Node<T> head;
//链长度
private Integer size;
//初始化
BothwayLoopChain() {
head = new Node<T>();
head.setNext(null);
size = 0;
}
class Node<T> {
private Node<T> pre;
private Object object;
private Node<T> next;
public Node<T> getPre() {
return pre;
}
public void setPre(Node<T> pre) {
this.pre = pre;
}
public Object getObject() {
return object;
}
public void setObject(Object object) {
this.object = object;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}
}
2、获取位置的结点:
public T get(Integer index) throws Exception {
return (T) getNode(index).getObject();
}
private Node<T> getNode(Integer index) throws Exception {
if (index > size || index < 0) {
throw new Exception("index outof length");
}
Node<T> p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p;
}
3、插入节点:
//在尾节点后插入节点
public void add(T t) throws Exception {
this.add(t,size);
}
//在index位置后插入一个节点
public void add(T t, Integer index) throws Exception {
//创建新节点
Node<T> p = new Node<>();
p.setObject(t);
//获取该位置的节点
Node<T> s = getNode(index);
p.setPre(s);
if (s.getNext() != null) {
//将本节点的next节点放入新节点的next节点
p.setNext(s.getNext());
s.getNext().setPre(p);
} else {
p.setNext(null);
}
size++;
}
4、移除节点:
//移除节点并返回
public Node<T> remove(Integer index) throws Exception {
//获取该位置的节点
Node<T> s = getNode(index);
//获取该位置节点的下一个节点
Node<T> next = s.getNext();
//将本节点的pre节点的next节点设置为next
s.getPre().setNext(next);
next.setPre(s.getPre());
return s;
}
至此,双向链表的基本实现已完成,其实它就是用空间换时间来提高性能的;
之前了解了单链表的循环结构即单向循环链表,举一反三,双向链表也有循环结构,即双向循环链表;
在双向链表的基础上进行改造:
除了插入方法,其他方法可保持不变:
//在index位置后插入一个节点
public void add(T t, Integer index) throws Exception {
//创建新节点
Node<T> p = new Node<>();
p.setObject(t);
//获取该位置的节点
Node<T> s = getNode(index);
p.setPre(s);
//将本节点的next节点放入新节点的next节点
p.setNext(s.getNext());
s.getNext().setPre(p);
size++;
}
本系列参考书籍:
《写给大家看的算法书》
《图灵程序设计丛书 算法 第4版》