数据结构-链表
原创
链表结构
链表结构五花八门，今天我重点给你介绍三种最常见的链表结构，它们分别是：单链表、双向链表和循环链表。我们首先来看最简单、最常用的单链表。
单链表
我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址
NULL，表示这是链表上最后一个结点。
针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度是 O(1)。链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度。
循环链表
循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表。
从我画的图中可以看出来，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。那相比单链表，双向链表适合解决哪种问题呢？从结构上来看，双向链表可以支持
O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。
头结点即为第一个节点undefined 尾节点指向空地址
带哨兵的节点有利于简化代码，推荐使用
双向链表
循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表。
双向循环链表
了解了循环链表和双向链表，如果把这两种链表整合在一起就是一个新的版本：双向循环链表。
双向链表的示例【待添加】
必练操作
接口定义
package com.s1.array;public interface IList { void print(); // 往尾部添加 void add(Integer data); void addFirst(Integer data); void addLast(Integer data); // 指定位置添加元素（有效范围内） void add(int position, Integer data); // 往尾部删除 Object remove(); // 删除首元素 Object removeFirst(); // 删除尾元素 Object removeLast(); // 删除指定下标的元素 Object remove(int index); // 删除指定数据的元素 Object remove(Object obj); // 改1 ： 找到下标，然后更改 boolean updateByPosition(int position, Integer value); // 改2 ： 找到原数据，然后更改 boolean updateByData(Integer oldData, Integer newData); void clear(); }- 实现单链表【可选 循环链表、双向链表】，支持增删操作
- 单链表反转链
- 表中环的检测
- 两个有序的链表合并
- 删除链表倒数第 n 个结点
- 求链表的中间结点
思考题：基于链表的 LRU 算法
LRU 思路一
- 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
- 如果此数据没有在缓存链表中，又可以分为两种情况：undefined如果此时缓存未满，则将此结点直接插入到链表的头部；undefined如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
或者 思路二
/** * 如果不存在
* 队列未满则插入 tail
* 队列已满移除head并从插入 tail
* 如果存在 则从中取出并从插入 tail
*/ package com.s2.link;public class LRULinkedList extends LinkedList { private static final int DEFAULT_LENGTH = 10; private final int length; private int used = 0; public LRULinkedList() { this(DEFAULT_LENGTH); } public LRULinkedList(int length) { this.length = length; } protected boolean isFull () { return this.used == this.length; } @Override public void add(Integer data) { /** * 如果不存在
* 队列未满则插入 tail
* 队列已满移除head并从插入 tail
* 如果存在 则从中取出并从插入 tail
*/
Object removeNode = this.remove(data);
if (removeNode == null && this.isFull()) {
this.removeFirst();
}
this.addLast(data);
}
@Override public Object remove(Object obj) { Object removeObject = super.remove(obj); if (removeObject != null) { this.used--; } return removeObject; } @Override public Object removeFirst() { Object removeObject = super.removeFirst(); if (removeObject != null) { this.used--; } return removeObject; } @Override public void addLast(Integer data) { super.addLast(data); used++; }}思考题：判断是否为回文串
找到中间节点。根据奇偶个数。
如果是奇数个则中分开。
如果是偶数个，则认为中点有两个，继续分开。
然后分别拿到两端的 head 指针就行循环，如果遇到节点的数据不一致则认定不是回文串。若循环结束则认为该串是回文串。
代码片段
// 判断是否为回文 public boolean palindrome() { // 根据快慢指针找到中间节点, 但是不知道总结点个数是奇还是偶数 if (this.headNode == null) { return false; } if (this.headNode.next == null) { return true; } // 大于两个节点 Node slow = this.headNode; Node fast = this.headNode; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } // slow fast // 1 2 // 1 2 3 System.out.println("slow " + slow); System.out.println("fast " + fast); Node leftNode; Node rightNode; // 总奇数个， 一个重点 if (fast.next == null) { rightNode = slow.next; this.inverseLinkList(slow); leftNode = slow.next; } // 总偶数个数，两个中点 else { rightNode = slow.next; this.inverseLinkList(slow); leftNode = slow; } return this.TFResult(leftNode, rightNode); }我的代码
https://gitee.com/kaiLee/struct/tree/master/src/main/java/com/s2
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
