什么是链表
链表是一种物理单元上非连续、非顺序的存储结构，这种结构中的元素逻辑顺序由指针进行确定。不同于数组需要先确定内存大小，链表可以充分利用内存空间。链表主要结构是一个数据对象，一个指针。数据对象保存用户数据，指针则是指向下一个节点，这样通过指针串联一个个数据节点形成一个链。

算法原理
节点包含数据对象和指针，数据对象保存用户数据，指针则指向下一个节点，下一个节点内部也包含同样的节点结构且指针指向下下个节点。

链表分类
根据功能和操作方式不同可以分为：
单向链表：每次从头部插入新的节点
双向链表：可以从头部、尾部插入新的节点
循环链表：最后一个节点的指针指向头节点

链表 VS 数组
1、存储结构链表不连续，数组连续
2、内存分配链表动态分配，数组静态分配
3、内存区域链表一般保存在堆区，数组一般情况下是保存在栈区
4、查询时间复杂度链表O(N)，数组根据下标索引时间复杂度为O(N)
5、插入删除时间复杂度链表找到节点直接操作为O(1),数组找到元素删除后需要移动保证顺序为O(N)

小试牛刀
本次我们仅模拟双向链表，其他类型链表大同小异
1、增加链表头部、尾部插入元素，并提供根据元素删除节点

/*** 双向链表模拟* @author senfel* @version 1.0* @date 2022/12/2 11:24*/
@Slf4j
@Data
public class LinkedList {/*** 链表长度*/private int size;/*** 链表头部*/private Node head;/*** 链表尾部*/private Node tail;/*** 节点*/@Dataprivate static class Node{/*** 数据*/private Object dataObj;/*** 下一个节点*/private Node next;public Node(Object dataObj, Node next) {this.dataObj = dataObj;this.next = next;}}public LinkedList() {this.size = 0;this.head = null;this.tail = null;}/*** 是否为空* @author senfel* @date 2022/12/2 11:39* @return java.lang.Boolean*/public Boolean isEmpty(){return this.size == 0;}/*** 头部插入* @param obj* @author senfel* @date 2022/12/2 11:40* @return void*/public void addFirst(Object obj){//创建节点Node node = new Node(obj, null);if(this.isEmpty()){this.tail = node;this.head = node;}else{//链表存在数据node.next = this.head;this.head = node;}this.size++;}/*** 尾部插入* @param obj* @author senfel* @date 2022/12/2 13:38* @return void*/public void addLast(Object obj){Node node = new Node(obj, null);if(this.isEmpty()){this.head = node;this.tail = node;}else{//链表存在数据this.tail.next = node;this.tail = node;}this.size++;}/*** 删除节点* @param obj* @author senfel* @date 2022/12/2 13:44* @return void*/public void remove(Object obj){if(this.isEmpty()){throw new RuntimeException("链表为空");}if(this.size == 1){this.head = null;this.tail = null;}else{//头部节点 获取需要删除的节点 及其上节点Node currentNode = this.head;Node currentHead = null;while (!currentNode.getDataObj().equals(obj)){currentHead = currentNode;currentNode = currentNode.next;}//删除节点if(Objects.isNull(currentHead)){//需要删除的节点就是头节点this.head = currentNode.next;}else{currentHead.next = currentNode.getNext();if(this.tail.getDataObj().equals(obj)){//删除的尾部节点this.tail = currentHead;}}}this.size--;}
}

2、提供测试插入删除方法

  /*** toString* @param list* @return*/public static String to(LinkedList list){if(Objects.isNull(list)){return null;}StringBuffer buffer = new StringBuffer();Node currentNode = list.getHead();int i = 1;buffer.append("链表层级为：\n"+i+"级节点元素为："+currentNode.getDataObj()+"\n");while (Objects.nonNull(currentNode.next)){i++;currentNode = currentNode.next;buffer.append(""+i+"级节点元素为："+currentNode.getDataObj()+"\n");}return buffer.toString();}public static void main(String[] args) {LinkedList linkedList = new LinkedList();//模拟头部进入2个元素,尾部进入3个元素for(int i=0;i<6;i++){if(i<3){linkedList.addFirst(i);}else{linkedList.addLast(i);}}log.error("\n模拟头部进入2个元素,尾部进入3个元素完成,当前链表{}", to(linkedList));linkedList.remove(2);log.error("\n模拟任意删除头0元素{}", to(linkedList));linkedList.remove(5);log.error("\n模拟任意删除尾部5元素{}", to(linkedList));linkedList.remove(3);log.error("\n模拟任意删除中部3元素{}", to(linkedList));}

3、查看测试结构并展示链表数据结构

模拟头部进入2个元素,尾部进入3个元素完成,当前链表链表层级为：
1级节点元素为：2
2级节点元素为：1
3级节点元素为：0
4级节点元素为：3
5级节点元素为：4
6级节点元素为：5

模拟任意删除头0元素链表层级为：
1级节点元素为：1
2级节点元素为：0
3级节点元素为：3
4级节点元素为：4
5级节点元素为：5

模拟任意删除尾部5元素链表层级为：
1级节点元素为：1
2级节点元素为：0
3级节点元素为：3
4级节点元素为：4

模拟任意删除中部3元素链表层级为：
1级节点元素为：1
2级节点元素为：0
3级节点元素为：4