线性表、数组、链表

线性表：线性表中存储的每个数据称为一个元素，各个元素及其索引是一一对应的关系。线性表有两种存储方式：顺序存储方式和链式存储方式。

数组(array)：数组就是线性表的顺序存储方式。数组的内存是连续分配的，并且是静态分配的，即在使用数组之前需要分配固定大小的空间。可以通过索引直接得到数组中的而元素，即获取数组中元素的时间复杂度为O(1)。插入和删除数组中元素的事件复杂度为O(n)。

链表(linked-list)：链表就是线性表的链式存储方式。链表的内存是不连续的，前一个元素存储地址的下一个地址中存储的不一定是下一个元素。链表通过一个指向下一个元素地址的引用将链表中的元素串起来。

链表和数组性能比较：

时间复杂度	数组	链表
插入、删除	O(n)	O(1)
随机访问	O(1)	O(n)

数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统没有足够的连续内存空间分配。如果声明的数组过小，出现不够用的情况，需要再申请一个更大的内存空间，把原数组拷贝进去。而链表没有大小限制，天然支持动态扩容。
比如Java的ArrayList容器支持动态扩容，但是动态扩容的原理是数组中没有空闲空间了，自动申请一个更大的数组，然后拷贝数据。

链表的缺点是消耗内存，每个结点都需要消耗额外的存储空间去存储指向下一个结点的指针，内存消耗会翻倍，同时如果频繁进行链表的插入和删除会导致频繁的内存申请和释放，容易造成内存碎片。

具体链表和数组的选择要给根据不同的项目进行选择。

链表

链表分为单链表和双链表、循环链表。
链表中数组插入和删除元素的时间复杂度为O(1)，查询元素的时间复杂度为O(n)。

单链表

单链表的每个节点中包含当前值和指向下一个节点的指针next。

单链表结构体定义：

struct node
{
    int value;
    struct node *next;
}Node;

双链表

双链表的每个节点中包含当前值、指向下一个节点的指针next和指向前一个节点的指针prev。

循环链表

循环链表是所有节点构成一个循环

双向循环链表

双链表构成一个循环

LRU缓存淘汰算法

设计lru算法的思路，不管用什么数据结构，都要考虑的几个问题。
1、如何表示最近访问的数据和最早访问的数据
2、如何查找是否缓存了
3、数据有缓存，如何处理
4、数据没有缓存，如何处理
1.缓存未满
2.缓存已满

链表实现LRU缓存淘汰算法

缓存淘汰算法常见的有三种：先进先出策略FIFO(First In First Out)，最少使用测试LFU(Least Frequently Used)，最近最少使用策略LRU(Least Recently Used)。

链表实现LRU缓存淘汰算法的思路：
维持一个单链表，每来一个访问数据，我们从链表头开始顺序遍历链表：

如果此数据之前已经被缓存在链表中，遍历得到这个数据对应的结点，并将其从原来的位置删除，然后在插入到链表的头部。
如果此数据没有在缓存链表中，分为两种情况：

如果缓存未满，将此结点直接插入到链表的头部；
如果缓存已满，将链尾结点删除，将新的数据结点插入到链表的头部。

缓存访问的时间复杂度是O(n)。因为每次都要遍历一次链表。

数组实现LRU缓存淘汰算法

方式一：首位置保存最新访问数据，末尾位置优先清理
当访问的数据未存在于缓存的数组中时，直接将数据插入数组第一个元素位置，此时数组所有元素需要向后移动1个位置，时间复杂度为O(n)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉末尾的数据，时间复杂度为O(1)。
方式二：首位置优先清理，末尾位置保存最新访问数据
当访问的数据未存在于缓存的数组中时，直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入当前数组最后一个元素的位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉数组首位置的元素，且剩余数组元素需整体前移一位，时间复杂度为O(n)。（优化：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。）

正确写出链表代码

理解指针与引用：
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
警惕指针丢失和内存泄漏：
插入和删除结点时一定要思考好当前结点的指向，删除结点时要手动释放内存空间。
利用哨兵简化实现难度：
链表的第一个结点和最后一个结点比较特殊，每次插入和删除都需要单独考虑第一个结点和最后一个结点，我们可以引入哨兵结点，不管链表是不是空，head指针都会一直指向这个哨兵结点。这种有哨兵结点的链表叫带头链表，相反，没有哨兵结点的链表叫作不带头链表。
留意边界条件处理：
链表代码的边界条件一般包括以下几点：

链表为空时代码是否能正常工作？
链表只有一个结点时代码是否能正常工作？
链表包含两个结点时代码是否能正常工作？
代码处理头结点和尾结点是否能正常工作？

链表实现

链表一定要手动写一遍代码，写完后整个理解会清晰不少，而且会踩一遍链表的坑，踩完后基本也就不会犯错了。
使用c结构体实现单链表的代码

LeetCode链表相关题目：

二进制链表转整数（容易）
单链表反转（容易）
判断一个链表是否有环（容易）
判断两个链表是否相交（容易）
两两交换链表中的结点（中等）
[两个有序链表合并（容易）]
返回倒数第k个结点（容易）
删除链表倒数第k个结点（容易）：基于返回倒数第k个结点，找到倒数第k个结点自然也就可以删除倒数第k个结点
求链表的中间节点（容易）
判断是否是回文链表（容易）：
思路1是先使用快慢指针找到链表的中心结点，然后把前半段链表逆序或者把后半段链表逆序，然后前后半段链表进行依次比较即可。或者直接把整个链表逆序，这样代码简单但是时间复杂度稍微高一点点
思路2将链表的值依次存到栈中，然后弹出做对比即可。
还有一种使用递归的思路。使用递归同时保存正向遍历结果和反向遍历结果。非常巧妙。

# python代码
def isPalindrome(self, head: ListNode) -> bool:

    self.front_pointer = head

    def recursively_check(current_node=head):
        if current_node is not None:
            if not recursively_check(current_node.next):
                return False
            if self.front_pointer.val != current_node.val:
                return False
            self.front_pointer = self.front_pointer.next
        return True

    return recursively_check()

心得

链表的题大部分都可以用快慢指针的方法来解决，比如判断是否有环，求中间结点，求倒数第k个结点等，把这类题多写几道。

参考文献
1.参考文章1

数据结构之链表（linked-list）