链表与数组的区别
-
底层的存储结构上
数组需要一块连续的内存区域来存储，如果剩余的连续内存没有达到数组的大小的话，那就不能够存储。
链表不需要一块连续的内存区域，它通过“指针”来将一组零散的内存块串联起来使用。
数组与链表的区别.jpg
单链表
我们知道链表通过“指针”来将不连续的内存空间连接起来，这每一块内存空间就叫做链表的“结点”，而每个结点除了要存储相应的数据之外，还要存储下一个结点的地址，这样才能保证结点相连接起来。我们把这个存储下一个结点的地址的指针叫做后继指针next。
单链表.jpg
如图所示，单链表中有两个特殊的结点。
- 头结点：记录链表的基地址。
- 尾节点：next指向null。
单链表的插入删除操作
单链表插入删除.jpg
如图所示，插入和删除操作只需要对后继指针进行操作即可，其时间与空间复杂度为
但是带来插入删除便利的同时，其随机访问却比数组要麻烦很多，因为每个节点只保存了下一个节点的地址，所以我们只能一个一个节点的依次遍历，其时间复杂度为
循环链表
循环链表和单链表的唯一区别就在于尾节点。单链表的尾节点是指向null的。而循环链表的尾节点是指向头节点。
循环链表.jpg
其与单链表的优点在于从链尾到链头比较方便。
双向链表
顾名思义，双向链表就是既可以从前往后查询，也可以从后往前查询。因此每个节点就要多维护一个指针来保存pre。
双向链表.jpg
如图所示，双向链表支持以的方式来找到前驱节点。在一些情况下，双向链表的插入删除操作要比单链表更加简单：
- 当我们要删除某个节点的前驱节点的时候，如果用单链表就只能重新遍历，然后找到
next等于目标结点的节点，然后删除。但是如果我们使用双向链表，那么只需要使用pre就能够得到前驱节点。 - 当我们使用的是有序链表，然后按值查询的时候，如果我们记住了上一次查询的值的大小，然后与这次查询的值进行对比，大的话则向前查询，小的话，则向后查询，这样就能够节省很多查询的时间。
但是因为双向链表比单链表多保存了一个指向前驱结点的指针，在data不大的情况下，多占用的内存空间就很可观了，这也是双向链表的缺点。
链表VS数组性能
- 首先说说数组的优点，因为数组是在内存中连续的存储的，所以可以借用CPU的缓存机制来预读数组的数据，使其效率更好。
- 因为数组是支持按照下标随机访问的，可以以
的时间复杂度来获取data。而链表则需要
。
- 然后说说数组的缺点，因为数组是不支持动态插入删除的，每次插入删除都需要将剩下的数组移动一次，时间复杂度为
如何实现LRU缓存
回到标题，如何实现LRU缓存呢。因为LRU的特性是最近最少使用的数据被删除，可想而知，这种插入删除较多的情况不能够使用数组来实现。
我们可以维护一个有序单链表来实现LRU算法，链表以使用时间为其顺序，链表头是最近最少使用的节点，删除也是从链表头开始删除。
当我们新增一个节点的时候，也相当于这个节点被使用，所以将其放到链表尾部，如果这个使用缓存已满，从头部删除一个节点。当我们使用某一个节点的时候，也将其转移到链表的尾部。
因为链表的增删都是，所以该有序单链表的时间复杂度为
。
思考题
如何使用单链表实现回文字符串判断？
public class palindrome {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode prev = null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
ListNode next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
//注意次数回文length为单复数都考虑进去了，如果为单数，则fast！=null，
// 此时slow为回文中间的数据，需要再使用其next
if (fast != null) {
slow = slow.next;
}
while (slow != null) {
assert prev != null;
if (slow.val.equals(prev.val) ) {
return false;
}
slow = slow.next;
prev = prev.next;
}
return true;
}
}
class ListNode {
String val;
ListNode next;
ListNode(String val) {
this.val = val;
}
}
其中需要注意的点
- 在进行节点的
data数据判断的时候，不能使用==，应该使用equals函数。 - 需要对回文为单复数长度两种情况进行考虑，单数情况下，当fast到达末尾的时候，
slow处于回文正中间，此时应该向后挪一位。复数情况下，最后fast == null，此时slow处于回后半段的第一位，不需要挪动。
