算法基础课二：数组和链表

数组结构

1. 线性表结构，每个元素，最多只有前和后两个方向，是连续内存空间存储，要求相同的数据类型；
2. 数组，支持根据下标随机访问，时间复杂度为 O(1)，内部是根据 ( 内存首地址 + 下标 * 数据类型所占空间 )，定位到内存地址；
3. 插入，修改，删除操作，

插入和删除操作：
		空间复杂度 O(1) 
		最好时间复杂度 O(1) 队尾插入或删除
		最坏时间复杂度 O(n) 队头插入或删除，因为涉及数组元素的整体复制
		平均时间复杂度 O(n)，(1+2+...+n)*(1/n) 即为 O(n) 
	修改操作：
		空间复杂度 O(1) 
		时间复杂度 O(1)，数组下标随机访问，修改值即可
           

1. 如果对数组元素的顺序，没有要求，向第 k 个位置插入元素，可以先将第 k 个位置的元素，移到数组末尾，然后给数组第 k 个位置，赋新值，那么时间复杂度就是 O( 1 )；
2. 删除操作，如果有多次删除操作，可以考虑，前几次删除，只标记元素被删除，并不真正删除，和执行数据搬移，等到累积几次删除后，才真正完成删除，进行数据搬移，这样提高操作效率，和 JVM 中的标记清除的垃圾回收类似；
3. 在 java 中，不允许数组越界访问，访问不存在的数组下标，回抛出异常，下面示例，i = 3 时，会抛出异常；

psvm(...){    
		int i = 0;    
		int arr[3] = {0};    
		for(; i<=3; i++){        
			arr[i] = 0;        
			printf("hello world\n");    
		}    
	}
           

1. java 中的 ArrayList，将数组操作的细节封装起来，如插入，删除数据时，搬移其他数据等，另外，支持动态扩容，每次扩容 1.5 倍；

链表结构

1. 链表，通过指针，将一组零散的内存块串联在一起，每个内存块，称为链表的结点，包含存储数据 data，和下一个节点的指向 next，即下一个节点的地址；
2. 链表的插入和删除操作，只需改变前后节点的指针，时间复杂度是 O ( 1 )，随机访问，需要遍历，时间复杂度是 O ( n )；
3. 双向链表比单链表，插入和删除操作效率更高，可以向前或向后查找，空间换取时间；
4. 链表算法，需要考虑链表为空，链表只有一个节点，只有两个节点，对头，尾节点操作等边界条件检查；

数组和链表

1. 数组的插入和删除，都涉及数据搬移，效率低，而下标随机访问效率特别高，链表与之正好相反，所以链表适合频繁插入和删除的场景，数组适合频繁随机访问的场景；
2. 并且数组是连续存储，对 cpu 缓存更友好，链表则不然；
3. 数组扩容不友好，链表天然支撑扩容；

算法操作

1. 链表实现 LRU 缓存淘汰，将最近最少使用的缓存淘汰；

缓存访问，首先链表查找：
		如果不存在，将缓存节点，存放在链表头部，如果链表满了，删除尾节点
		如果存在，命中缓存，先将缓存节点从该位置删除，新放入到链表头部，保证链表头部是最近使用的数据
		链表尾部，就是最近最少使用的数据，所以，缓存满了，删除尾节点，就是删除最近最少使用
	时间复杂度是 o(n),查找是必须步骤
	缓存淘汰策略
		先进先出策略 FIFO（First In，First Out）
		最少使用策略 LFU（Least Frequently Used）
		最近最少使用策略 LRU（Least Recently Used）
           

1. 实现回文字符串的检查

1. 单链表反转

通过两个节点指针，遍历链表，首先 A = null , B = head，然后 temp = B, B = B.next，temp.next = A, A = temp,
	直到 B = null 截止 
           

1. 链表中环的检测

通过快慢指针，快指针一次走两步，慢指针一次走一步，如果有环，两个指针必定相遇，
	如果没有环，两者不会相遇，且都会执行到null
           

1. 两个有序的链表合并

通过两个指针，分别指向两个链表头，比较大小，将较小的节点，放入一个新链表中，然后累积该指针，然后继续比较大小，
		直到一个指针走到链表尾，然后复制指针没走完的链表，到新链表尾部，新链表即为合并的有序链表
           

1. 删除链表倒数第 n 个结点

倒数第 n 个节点，即距离最后一个节点有 n 个节点，如此使用两个指针，一个指向链表头，一个指向第 n 个节点，两个指针	
		每次走一步，直到第二个指针走到链表尾，那么第一个指针就是指向，倒数第 n 个节点
           

1. 求链表的中间结点

同样使用两个指针，都从链表头开始，一个每次走一步，一个每次走两步，这样当走两步的指针，走到链表尾部，
		此时第一个指针就刚好是链表中间节点
           

1. 具体代码实现，查看 …