链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。
按照面向对象的思想，我们可以设计一个类，来描述结点这个事物，用一个属性描述这个结点存储的元素，用来另外一个属性描述这个结点的下一个结点。
API设计
public class Node<T> { //存储元素 public T item; //指向下一个结点 public Node next; public Node(T item, Node next) { this.item = item; this.next = next; } }
生成链表：
public static void main(String[] args) throws Exception { //构建结点 Node<Integer> first = new Node<Integer>(11, null); Node<Integer> second = new Node<Integer>(13, null); Node<Integer> third = new Node<Integer>(12, null); Node<Integer> fourth = new Node<Integer>(8, null); Node<Integer> fifth = new Node<Integer>(9, null); //生成链表 first.next = second; second.next = third; third.next = fourth; fourth.next = fifth; }
单向链表
代码实现
单向链表API设计
import java.util.Iterator; public class LinkList<T> implements Iterable<T>{ //记录头结点 private Node head; //记录链表的长度 private int N; //结点类 private class Node { //存储数据 T item; //下一个结点 Node next; public Node(T item, Node next) { this.item = item; this.next = next; } } public LinkList() { //初始化头结点、 this.head = new Node(null,null); //初始化元素个数 this.N=0; } //清空链表 public void clear() { head.next=null; this.N=0; } //获取链表的长度 public int length() { return N; } //判断链表是否为空 public boolean isEmpty() { return N==0; } //获取指定位置i出的元素 public T get(int i) { //通过循环,从头结点开始往后找，依次找i次，就可以找到对应的元素 Node n = head.next; for(int index=0;index<i;index++){ n=n.next; } return n.item; } //向链表中添加元素t public void insert(T t) { //找到当前最后一个结点 Node n = head; while(n.next!=null){ n=n.next; } //创建新结点，保存元素t Node newNode = new Node(t, null); //让当前最后一个结点指向新结点 n.next=newNode; //元素的个数+1 N++; } //向指定位置i出，添加元素t public void insert(int i, T t) { //找到i位置前一个结点 Node pre = head; for(int index=0;index<=i-1;index++){ pre=pre.next; } //找到i位置的结点 Node curr = pre.next; //创建新结点，并且新结点需要指向原来i位置的结点 Node newNode = new Node(t, curr); //原来i位置的前一个节点指向新结点即可 pre.next=newNode; //元素的个数+1 N++; } //删除指定位置i处的元素，并返回被删除的元素 public T remove(int i) { //找到i位置的前一个节点 Node pre = head; for(int index=0;index<=i-1;i++){ pre=pre.next; } //要找到i位置的结点 Node curr = pre.next; //找到i位置的下一个结点 Node nextNode = curr.next; //前一个结点指向下一个结点 pre.next=nextNode; //元素个数-1 N--; return curr.item; } //查找元素t在链表中第一次出现的位置 public int indexOf(T t) { //从头结点开始，依次找到每一个结点，取出item，和t比较，如果相同，就找到了 Node n = head; for(int i=0;n.next!=null;i++){ n=n.next; if (n.item.equals(t)){ return i; } } return -1; } @Override public Iterator<T> iterator() { return new LIterator(); } private class LIterator implements Iterator{ private Node n; public LIterator(){ this.n=head; } @Override public boolean hasNext() { return n.next!=null; } @Override public Object next() { n = n.next; return n.item; } } }
删除的复杂度
- 等值删除，删除结点中值等于某个给定值的结点
为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，时间复杂度为O(n)
- 删除给定指针指向的结点
对于第二种情况，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。复杂度仍然为O(n)
- 删除指定索引位置的结点
需要从头遍历到指定索引，获取对于的结点对象的前驱和后继结点
复杂度仍然为O(n)
双向链表
优缺点
占用额外内存
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。那相比单链表，双向链表适合解决哪种问题呢？
获得前驱结点方便
从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。
代码实现
按照面向对象的思想，我们需要设计一个类，来描述结点这个事物。由于结点是属于链表的，所以我们把结点类作为链表类的一个内部类来实现
结点API设计
双向链表API设计
import java.util.Iterator; public class TowWayLinkList<T> implements Iterable<T> { //首结点 private Node head; //最后一个结点 private Node last; //链表的长度 private int N; //结点类 private class Node{ public Node(T item, Node pre, Node next) { this.item = item; this.pre = pre; this.next = next; } //存储数据 public T item; //指向上一个结点 public Node pre; //指向下一个结点 public Node next; } public TowWayLinkList() { //初始化头结点和尾结点 this.head = new Node(null,null,null); this.last=null; //初始化元素个数 this.N=0; } //清空链表 public void clear(){ this.head.next=null; this.head.pre=null; this.head.item=null; this.last=null; this.N=0; } //获取链表长度 public int length(){ return N; } //判断链表是否为空 public boolean isEmpty(){ return N==0; } //获取第一个元素 public T getFirst(){ if (isEmpty()){ return null; } return head.next.item; } //获取最后一个元素 public T getLast(){ if (isEmpty()){ return null; } return last.item; } //插入元素t public void insert(T t){ if (isEmpty()){ //如果链表为空： //创建新的结点 Node newNode = new Node(t,head, null); //让新结点称为尾结点 last=newNode; //让头结点指向尾结点 head.next=last; }else { //如果链表不为空 Node oldLast = last; //创建新的结点 Node newNode = new Node(t, oldLast, null); //让当前的尾结点指向新结点 oldLast.next=newNode; //让新结点称为尾结点 last = newNode; } //元素个数+1 N++; } //向指定位置i处插入元素t public void insert(int i,T t){ //找到i位置的前一个结点 Node pre = head; for(int index=0;index<i;index++){ pre=pre.next; } //找到i位置的结点 Node curr = pre.next; //创建新结点 Node newNode = new Node(t, pre, curr); //让i位置的前一个结点的下一个结点变为新结点 pre.next=newNode; //让i位置的前一个结点变为新结点 curr.pre=newNode; //元素个数+1 N++; } //获取指定位置i处的元素 public T get(int i){ Node n = head.next; for(int index=0;index<i;index++){ n=n.next; } return n.item; } //找到元素t在链表中第一次出现的位置 public int indexOf(T t){ Node n = head; for(int i=0;n.next!=null;i++){ n=n.next; if (n.next.equals(t)){ return i; } } return -1; } //删除位置i处的元素，并返回该元素 public T remove(int i){ //找到i位置的前一个结点 Node pre = head; for(int index=0;index<i;index++){ pre=pre.next; } //找到i位置的结点 Node curr = pre.next; //找到i位置的下一个结点 Node nextNode= curr.next; //让i位置的前一个结点的下一个结点变为i位置的下一个结点 pre.next=nextNode; //让i位置的下一个结点的上一个结点变为i位置的前一个结点 nextNode.pre=pre; //元素的个数-1 N--; return curr.item; } @Override public Iterator<T> iterator() { return new TIterator(); } private class TIterator implements Iterator{ private Node n; public TIterator(){ this.n=head; } @Override public boolean hasNext() { return n.next!=null; } @Override public Object next() { n=n.next; return n.item; } } }
双向链表和单向链表的对比
- 删除
已知要删除的结点，但是删除某个结点 q 需要知道其前驱结点，单向链表需要从头开始遍历，双向链表可以通过prev直接获取
- 新增
在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度
- 按值查询
对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
空间换时间的思想
双向链表尽管比较费内存，但还是比单链表的应用更加广泛的原因
LinkedHashMap
数组和链表的对比
- 数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
- 数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。
- 如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。
链表的应用
链表反转
需求：
原链表中数据为：
1->2->3>4反转后链表中数据为：
4->3->2->1递归
使用递归可以完成反转，递归反转其实就是从原链表的第一个存数据的结点开始，依次递归调用反转每一个结点，直到把最后一个结点反转完毕，整个链表就反转完毕。
反转API设计：
public void reverse()：对整个链表反转
public Node reverse(Node curr)：反转链表中的某个结点curr,并把反转后的curr结点返回//用来反转整个链表 public void reverse(){ //判断当前链表是否为空链表，如果是空链表，则结束运行，如果不是，则调用重载的reverse方法完成反转 if (isEmpty()){ return; } reverse(head.next); } //反转指定的结点curr，并把反转后的结点返回 public Node reverse(Node curr){ if (curr.next==null){ head.next=curr; return curr; } //递归的反转当前结点curr的下一个结点；返回值就是链表反转后，当前结点的上一个结点 Node pre = reverse(curr.next); //让返回的结点的下一个结点变为当前结点curr； pre.next=curr; //把当前结点的下一个结点变为null curr.next=null; return curr; } //结点类 private class Node { //存储数据 T item; //下一个结点 Node next; public Node(T item, Node next) { this.item = item; this.next = next; } }
迭代
迭代的本质是循环，在元素规模较大的情况下，使用递归很可能会超过编程语言的默认栈深，导致栈溢出
算法思路描述：
- 先用指针temp存储第二个元素的地址
temp =node.next
- 指针prev=null ，指针curr=node curr.next = prev(反转)
- prev指针向后移动，curr指针向后移动 prev =curr；curr=temp；
/** * 迭代 * 从第一个元素开始遍历，设置一个指针curr = 元素1 prev =null 临时变量next存储元素2， * 改变元素1指向prev * prev指向 元素1 ，curr指向next * * @param list: * @return void * @author wangjie * @date 2023/1/31 22:33 * @since 1.0.0 */ static void reverseByIteration(LinkList list) { Node prev = null; Node curr = list.head.next; Node next = null; while (curr != null) { next = curr.next; curr.next = prev; prev = curr; curr = next; } //头指针指向最后一个元素 list.head.next = prev; }
快慢指针
快慢指针指的是定义两个指针，这两个指针的移动速度一块一慢，以此来制造出自己想要的差值，这个差值可以让我们找到链表上相应的结点。一般情况下，快指针的移动步长为慢指针的两倍
中间值问题
利用快慢指针，我们把一个链表看成一个跑道，假设a的速度是b的两倍，那么当a跑完全程后，b刚好跑一半，以此来达到找到中间节点的目的。
如下图，最开始，slow与fast指针都指向链表第一个节点，然后slow每次移动一个指针，fast每次移动两个指针。
public class FastSlowTest { public static void main(String[] args) throws Exception { //创建结点 Node<String> first = new Node<String>("aa", null); Node<String> second = new Node<String>("bb", null); Node<String> third = new Node<String>("cc", null); Node<String> fourth = new Node<String>("dd", null); Node<String> fifth = new Node<String>("ee", null); Node<String> six = new Node<String>("ff", null); Node<String> seven = new Node<String>("gg", null); //完成结点之间的指向 first.next = second; second.next = third; third.next = fourth; fourth.next = fifth; fifth.next = six; six.next = seven; //查找中间值 String mid = getMid(first); System.out.println("中间值为："+mid); } /** * @param first 链表的首结点 * @return 链表的中间结点的值 */ public static String getMid(Node<String> first) { //定义两个指针 Node<String> fast = first; Node<String> slow = first; //使用两个指针遍历链表，当快指针指向的结点没有下一个结点了，就可以结束了，结束之后，慢指针指向的结点就是中间值 while(fast!=null &&fast.next!=null){ //变化fast的值和slow的值 fast = fast.next.next; slow=slow.next; } return slow.item; } //结点类 private static class Node<T> { //存储数据 T item; //下一个结点 Node next; public Node(T item, Node next) { this.item = item; this.next = next; } } }
单向链表是否有环问题
使用快慢指针的思想，还是把链表比作一条跑道，链表中有环，那么这条跑道就是一条圆环跑道，在一条圆环跑道中，两个人有速度差，那么迟早两个人会相遇，只要相遇那么就说明有环
public class CircleListCheckTest { public static void main(String[] args) throws Exception { //创建结点 Node<String> first = new Node<String>("aa", null); Node<String> second = new Node<String>("bb", null); Node<String> third = new Node<String>("cc", null); Node<String> fourth = new Node<String>("dd", null); Node<String> fifth = new Node<String>("ee", null); Node<String> six = new Node<String>("ff", null); Node<String> seven = new Node<String>("gg", null); //完成结点之间的指向 first.next = second; second.next = third; third.next = fourth; fourth.next = fifth; fifth.next = six; six.next = seven; // //产生环 // seven.next = third; //判断链表是否有环 boolean circle = isCircle(first); System.out.println("first链表中是否有环："+circle); } /** * 判断链表中是否有环 * @param first 链表首结点 * @return ture为有环，false为无环 */ public static boolean isCircle(Node<String> first) { //定义快慢指针 Node<String> fast = first; Node<String> slow = first; //遍历链表，如果快慢指针指向了同一个结点，那么证明有环 while(fast!=null && fast.next!=null){ //变换fast和slow fast = fast.next.next; slow = slow.next; if (fast.equals(slow)){ return true; } } return false; } //结点类 private static class Node<T> { //存储数据 T item; //下一个结点 Node next; public Node(T item, Node next) { this.item = item; this.next = next; } } }
有环链表入口问题
当快慢指针相遇时，我们可以判断到链表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样为1，则慢指针与“新”指针相遇的地方就是环的入口。证明这一结论牵涉到数论的知识，这里略，只讲实现。
public class CircleListInTest { public static void main(String[] args) throws Exception { Node<String> first = new Node<String>("aa", null); Node<String> second = new Node<String>("bb", null); Node<String> third = new Node<String>("cc", null); Node<String> fourth = new Node<String>("dd", null); Node<String> fifth = new Node<String>("ee", null); Node<String> six = new Node<String>("ff", null); Node<String> seven = new Node<String>("gg", null); //完成结点之间的指向 first.next = second; second.next = third; third.next = fourth; fourth.next = fifth; fifth.next = six; six.next = seven; //产生环 seven.next = third; //查找环的入口结点 Node<String> entrance = getEntrance(first); System.out.println("first链表中环的入口结点元素为："+entrance.item); } /** * 查找有环链表中环的入口结点 * @param first 链表首结点 * @return 环的入口结点 */ public static Node getEntrance(Node<String> first) { //定义快慢指针 Node<String> fast = first; Node<String> slow = first; Node<String> temp = null; //遍历链表，先找到环(快慢指针相遇),准备一个临时指针，指向链表的首结点，继续遍历，直到慢指针和临时指针相遇，那么相遇时所指向的结点就是环的入口 while(fast!=null && fast.next!=null){ //变换快慢指针 fast = fast.next.next; slow = slow.next; //判断快慢指针是否相遇 if (fast.equals(slow)){ temp = first; continue; } //让临时结点变换 if (temp!=null){ temp = temp.next; //判断临时指针是否和慢指针相遇 if (temp.equals(slow)){ break; } } } return temp; } //结点类 private static class Node<T> { //存储数据 T item; //下一个结点 Node next; public Node(T item, Node next) { this.item = item; this.next = next; } } }
循环链表
循环链表，顾名思义，链表整体要形成一个圆环状。在单向链表中，最后一个节点的指针为null，不指向任何结点，因为没有下一个元素了。要实现循环链表，我们只需要让单向链表的最后一个节点的指针指向头结点即可。
public class Test { public static void main(String[] args) throws Exception { //构建结点 Node<Integer> first = new Node<Integer>(1, null); Node<Integer> second = new Node<Integer>(2, null); Node<Integer> third = new Node<Integer>(3, null); Node<Integer> fourth = new Node<Integer>(4, null); Node<Integer> fifth = new Node<Integer>(5, null); Node<Integer> six = new Node<Integer>(6, null); Node<Integer> seven = new Node<Integer>(7, null); //构建单链表 first.next = second; second.next = third; third.next = fourth; fourth.next = fifth; fifth.next = six; six.next = seven; //构建循环链表,让最后一个结点指向第一个结点 seven.next = first; } }
约瑟夫问题
问题描述：
传说有这样一个故事，在罗马人占领乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，第一个人从1开始报数，依次往后，如果有人报数到3，那么这个人就必须自杀，然后再由他的下一个人重新从1开始报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，从而逃过了这场死亡游戏 。
问题转换
41个人坐一圈，第一个人编号为1，第二个人编号为2，第n个人编号为n。
1.编号为1的人开始从1报数，依次向后，报数为3的那个人退出圈；
2.自退出那个人开始的下一个人再次从1开始报数，以此类推；
3.求出最后退出的那个人的编号。
解题思路：
- 构建含有41个结点的单向循环链表，分别存储1~41的值，分别代表这41个人；
- 使用计数器count，记录当前报数的值；
- 遍历链表，每循环一次，count++
- 判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0；
public class JosephTest { public static void main(String[] args) { //解决约瑟夫问题 //1.构建循环链表，包含41个结点，分别存储1~41之间的值 //用来就首结点 Node<Integer> first = null; //用来记录前一个结点 Node<Integer> pre = null; for(int i = 1;i<=41;i++){ //如果是第一个结点 if (i==1){ first = new Node<>(i,null); pre = first; continue; } //如果不是第一个结点 Node<Integer> newNode = new Node<>(i, null); pre.next=newNode; pre=newNode; //如果是最后一个结点，那么需要让最后一个结点的下一个结点变为first,变为循环链表了 if (i==41){ pre.next=first; } } //2.需要count计数器，模拟报数 int count=0; //3.遍历循环链表 //记录每次遍历拿到的结点，默认从首结点开始 Node<Integer> n = first; //记录当前结点的上一个结点 Node<Integer> before = null; while(n!=n.next){ //模拟报数 count++; //判断当前报数是不是为3 if (count==3){ //如果是3，则把当前结点删除调用，打印当前结点，重置count=0，让当前结点n后移 before.next=n.next; System.out.print(n.item+","); count=0; n=n.next; }else{ //如果不是3，让before变为当前结点，让当前结点后移； before=n; n=n.next; } } //打印最后一个元素 System.out.println(n.item); } //结点类 private static class Node<T> { //存储数据 T item; //下一个结点 Node next; public Node(T item, Node next) { this.item = item; this.next = next; } } }
LRU缓存淘汰策略
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。