数据结构之双向链表详细（java版）
前言
链表是一种线性表，常见的线性表还有栈、队列，本篇主要是分析双向链表的数据结构，以及如何使用java自己实现一个双向链表。在分析双向链表前，有必要先看看单向链表的数据结构图，方便对比双向链表数据结构。
1、单向链表
百度百科：单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点。 删除操作后：
2、双向链表
百度百科：双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 删除操作后：
3、手写实现
public class CoolList<T> { //节点个数 public int size; //头节点 private SummerNode<T> first; //尾节点 private SummerNode<T> last; //定义节点类型 private static class SummerNode<T> { //节点元素 T t; //前一个节点地址 SummerNode<T> pre; //后一个节点地址 SummerNode<T> next; SummerNode(SummerNode<T> pre,T t,SummerNode<T> next){ this.t = t; this.pre = pre; this.next = next; } } /** * 更新指定位置的元素 * @param index 位置 * @param t 元素 * @return 返回旧值 */ public T replace(int index,T t){ //检查节点是否存在 checkExistNode(index); //获取指定位置节点 SummerNode<T> exist = node(index); T oldValue = exist.t; //替换新值 exist.t = t; return oldValue; } /** * 在指定位置之前插入元素 * @param index * @param t * @return 成功返回true */ public boolean beforeIndexInsert(int index,T t){ //检查节点是否存在 checkExistNode(index); //获取节点 SummerNode<T> node = node(index); //前一个节点 SummerNode<T> pre = node.pre; //插入的节点在pre节点和node节点之间 final SummerNode<T> newNode = new SummerNode<>(pre, t, node); node.pre = newNode; if(pre == null){ //如果插入的位置是第一个节点前 first = newNode; } else { pre.next = newNode; } //元素+1 size++; return true; } //在末尾插入 public boolean lastInsert(T t){ final SummerNode<T> l = last; final SummerNode<T> newNode = new SummerNode<>(l, t, null); last = newNode; if(l == null){ //如果是首次插入元素，设置为第一个节点 first = newNode; } else { l.next = newNode; } size++; return true; } private void checkExistNode(int index){ if(index < 0 || index > size){ throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size+";"); } } /** * 获取指定位置节点元素 * @param index * @return */ public T get(int index){ checkExistNode(index); return node(index).t; } /** * 获取指定位置的节点 * @param index * @return */ SummerNode<T> node(int index){ //二分法查找，小于size/2，则顺序查找 if(index < (size >> 1)){ SummerNode<T> x = first; for(int i=0; i<index; i++){ x = x.next; } return x; } else { SummerNode<T> x = last; //倒序查找 for (int i = size-1; i > index; i--){ x = x.pre; } return x; } } /** * 移除指定位置的节点 * @param index * @return */ public T remove(int index){ //查找节点是否存在 checkExistNode(index); //删除节点 return unlink(node(index)); } /** * 移除指定元素的节点 * @param t * @return */ public boolean remove(T t){ //为空 if(t == null){ for(SummerNode<T> x=first; x!=null; x=x.next){ //查出为空的元素，再删除 if(x.t == null){ unlink(x); return true; } } } else { //不为空，查出不为空的元素，然后删除 for(SummerNode<T> x=first; x!=null; x=x.next){ if(t.equals(x.t)){ unlink(x); return true; } } } return false; } /** * 删除节点 * @param node * @return */ private T unlink(SummerNode<T> node){ final T type = node.t; //删除节点的前一个节点 final SummerNode<T> pre = node.pre; //删除节点的后一个节点 final SummerNode<T> next = node.next; //头结点 if(pre == null){ first = next; } else { pre.next = next; node.pre = null; } //尾结点 if(next == null){ last = pre; } else { next.pre = pre; node.next = null; } node.t = null; size--; return type; } } 复制代码测试代码：
public class CoolListTest { public static void main(String[] args) { CoolList<String> coolList = new CoolList<>(); //增加 coolList.lastInsert("cool"); coolList.lastInsert("moon"); coolList.lastInsert("单向链表"); coolList.lastInsert("的"); coolList.lastInsert("单向链表"); //删除 coolList.remove(2); //修改 coolList.replace(coolList.size - 1,"双向链表"); //插入 coolList.beforeIndexInsert(1,"summer"); StringBuffer sb = new StringBuffer(); for (int i=0; i<coolList.size; i++){ //查找 sb.append(coolList.get(i)).append(" "); } System.out.println(sb); } } 复制代码控制台输出：
cool summer moon 的 双向链表
作者：夏夜凉月
链接：https://juejin.cn/post/7027750954711662605