![Featured image of post [Java] 双链表](https://cdn.jsdelivr.net/gh/oopooa/cdn/cover/horns-three-eyes-girl.webp)
什么是双链表
双链表也叫双向链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
单链表与双链表的区别
单链表
双链表
双链表结构
public class DoubleLinkedList<T> {
/**
* 头结点
*/
private Node head;
/**
* 尾结点
*/
private Node tail;
/**
* 链表元素个数
*/
private int size;
/**
* 结点
*/
class Node {
/**
* 结点数据
*/
private T t;
/**
* 上一个结点
*/
private Node prev;
/**
* 下一个结点
*/
private Node next;
Node() {}
Node(Node prev, T t, Node next) {
this.prev = prev;
this.t = t;
this.next = next;
}
@Override
public String toString() {
return "Node{" + t + '}';
}
}
}
可以看作是在单链表结构的基础上，增加一片指向前驱结点的地址存放空间。
因为双链表既能向后检索结点，也能向前检索，所以对于链表尾结点的记录还是很有必要的。
完整代码
/**
* @program: DoubleLinkedList
* @description: 自定义双链表
* @author: opoa
* @create: 2021-04-05 16:25
**/
public class DoubleLinkedList<T> {
/**
* 头结点
*/
private Node head;
/**
* 尾结点
*/
private Node tail;
/**
* 链表元素个数
*/
private int size;
/**
* 结点
*/
class Node {
/**
* 结点数据
*/
private T t;
/**
* 上一个结点
*/
private Node prev;
/**
* 下一个结点
*/
private Node next;
Node() {}
Node(Node prev, T t, Node next) {
this.prev = prev;
this.t = t;
this.next = next;
}
@Override
public String toString() {
return "Node{" + t + '}';
}
}
public DoubleLinkedList() {
this.head = null;
this.size = 0;
}
/**
* 根据下标获取结点
*
* @param index 下标参数
* @return 对应结点
*/
public Node getNode(int index) {
checkIndex(index);
Node curNode = this.head;
// 下标为 0 直接返回头结点
if (index == 0) {
return head;
}
for (int i = 0; i < index; i++) {
curNode = curNode.next;
}
return curNode;
}
/**
* 根据元素值返回对应结点
*
* @param t 要查找的元素值
* @return 对应结点
*/
public Node getNode(T t) {
// 从头结点开始
Node curNode = head;
// 当前结点不为空且传入结点数据不等于传入元素
while (null != curNode && curNode.t != t) {
curNode = curNode.next;
}
return curNode;
}
/**
* 新增一个结点
*
* @param t 要插入的元素值
*/
public void add(T t) {
// 如果头结点为空，则链表为空 新增结点既是头节点也是尾结点
if (null == head) {
this.head = new Node(null, t, null);
this.tail = head;
this.size ++;
return;
}
// 新增的结点 以之前的尾结点作为前结点
Node node = new Node(tail, t, null);
// 把当前结点的地址赋值给尾结点的 next
tail.next = node;
// 当前结点作为新的尾结点
this.tail = node;
this.size ++;
}
/**
* 在链表尾部插入一个结点
*
* @param t 要插入的元素
*/
private void insertLast(T t) {
// 记录之前的尾结点
final Node l = tail;
// 新增一个结点
Node node = new Node(l, t, null);
// 该结点作为新的尾结点
this.tail = node;
// 如果之前的尾结点为空
if (null == l) {
// 则新插入的结点是头结点
this.head = node;
} else {
// 不为空 则把当前结点的引用赋值给之前尾结点的 next
l.next = node;
}
size ++;
}
/**
* 在某个结点前插一个结点
*
* @param t 要插入的结点
* @param old 要插入结点的后驱结点
*/
private void insertBefore(T t, Node old) {
// 之前结点的前驱结点 也是即将插入结点的前驱结点
Node prev = old.prev;
// 新增一个结点
Node node = new Node(prev, t, old);
// 当前结点的引用赋值给旧结点的 prev
old.prev = node;
// 如果之前的前驱结点为空
if (null == prev) {
// 则新插入的结点是头结点
this.head = node;
} else {
// 不为空 则把当前结点的引用赋值给前驱结点的 next
prev.next = node;
}
size ++;
}
/**
* 在指定下标处插入一个结点
*
* @param t 要插入的元素
* @param index 要插入的下标
*/
public void insert(T t, int index) {
checkIndex(index);
// 判断是否新增尾结点
if (index == size) {
insertLast(t);
} else {
insertBefore(t, getNode(index));
}
}
/**
* 根据元素删除某个结点
*
* @param t 要删除的元素
* @return 删除的元素
*/
public T remove(T t) {
Node node = getNode(t);
if (null == node) {
throw new NoSuchElementException();
}
return unlink(node);
}
/**
* 根据下标删除某个结点
*
* @param index 要删除结点的下标
* @return 删除的元素
*/
public T remove(int index) {
checkIndex(index);
return unlink(getNode(index));
}
/**
* 删除某个结点
*
* @param node 要删除的结点
* @return 删除结点的数据
*/
private T unlink(Node node) {
// 保存原结点数据
T oldVal = node.t;
// 要删除结点的前驱结点
Node prev = node.prev;
// 要删除结点的后驱结点
Node next = node.next;
// 如果前驱结点为空
if (null == prev) {
// 表明要删除的结点是头结点
// 把后驱结点设置为头结点
head = next;
} else {
// 把后驱结点地址赋值给前驱结点的 next
prev.next = next;
// 把要删除结点的 prev 设置为空
node.prev = null;
}
// 如果后驱结点为空
if (null == next) {
// 表明要删除的结点是尾结点
// 把前驱结点设置为尾结点
tail = prev;
} else {
// 把前驱结点地址赋值给后驱结点的 prev
next.prev = prev;
// 把要删除结点的 next 设置为空
node.next = null;
}
// 把要删除结点的数据设置为 null 帮助 GC
node.t = null;
size --;
return oldVal;
}
/**
* 给指定下标结点设置数据
*
* @param t 要设置的元素
* @param index 要设置结点的下标
*/
public T set(int index, T t) {
checkIndex(index);
// 获取要设置的结点
Node old = getNode(index);
// 保存结点中旧的数据
T oldVal = old.t;
// 为结点数据赋值
old.t = t;
// 返回旧值
return oldVal;
}
/**
* 检查下标参数合法性
*
* @param index 要检查的下标参数
*/
private void checkIndex(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("非法下标参数");
}
}
/**
* 返回链表长度
*
* @return 链表长度
*/
public int length() {
return size;
}
/**
* 打印输出双链表
*
* @return 整个双链表
*/
@Override
public String toString() {
if (size == 0) {
return null;
}
Node curNode = head;
StringBuilder sb = new StringBuilder();
while (null != curNode) {
sb.append(curNode.t.toString())
.append(" -> ");
curNode = curNode.next;
}
sb.append("null");
return sb.toString();
}
}
参考资料
Java8 LinkedList 源码