数组和链表算是coder 最早入门的数据结构了，但是每一个知识点，不管看起来是多么的简单，其实背后还有很多是需要挖掘和记忆的，也就是是否已经在心中形成一个知识的图谱，因为每一个知识点都可以通过你的知识图谱到达另外一个知识点，如果没有办法达到的话，只能说明是你的知识网络图谱还不够深入。
数组的本质
从数组最本质的角度出发， 专业一点数组是线性表的一种，什么是线性表？站在硬件资源的，比如cpu角度看，就是我需要内存中读取一种数据（脑袋里可以想象一下cpu和memory 总线的数据传递，或者看我关于图谱的那一篇）,cpu 可以根据寻址公式随机访问取到内存块中的数据，同时还可以根据28原则，多取一些数据放入缓存，以平衡cpu计算和访问内存的速度差异，所以数组是硬件资源友好型的代表
数组的特性
说烂了的查找的时间复杂度是o（1） 的说法其实是错误的，也很好推理，想一下排序算法，或者二分查找就可以了，二分查找的时间复杂度都是o（logn），怎么数组的时间复杂度就是o（1）了呢？正确的说法是知道下标的情况下，随机访问的时间复杂度是o（1）
其次是比较低效的插入和删除，原因是插入和删除的时间复杂度都是o（n），因为在考虑不留下空白区域形成空白碎片的情况下，都会做一个时间复杂度为o（n）的移动的操作， 当然还有一些小技巧是可以优化这个，比如我要删除的时候，先不一个个删除，而是将要删除的元素标记起来，然后达到一定数量的时候再进行删除，（这也是gc中垃圾回收器的标记清除算法的原型），或者插入的时候，在没有需要保证数据强顺序性的原则下，直接进行交换操作即可。
数组的容器是怎么来的呢
因为数组中的查找和删除和插入以及扩容的操作其实都是一些让大家写都能写出一个八九不离十的代码来，所以为了不让java coder 每次重复造轮子，那就写个容器包来简化coder 的代码量，那大神写的和自己想象中的是不是一样的呢？看源码的方式就最简单了
ArrayList 研究一下
先来看一下人家怎么介绍的
/**
* Resizable-array implementation of the <tt>List</tt> interface. Implements
* all optional list operations, and permits all elements, including
* <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
* this class provides methods to manipulate the size of the array that is
* used internally to store the list. (This class is roughly equivalent to
* <tt>Vector</tt>, except that it is unsynchronized.)
这一段的重要信息我们知道了ArrayList 线程不安全，没有加锁操作，其余基本和vector 一致
*
* <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
* <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
* time. The <tt>add</tt> operation runs in <i>amortized constant time</i>,
* that is, adding n elements requires O(n) time. All of the other operations
* run in linear time (roughly speaking). The constant factor is low compared
* to that for the <tt>LinkedList</tt> implementation.
这一段的重要信息是时间复杂度的信息：size() isEmpty() get() set() iterator()
listIterator() 在常量的时间复杂度上，其实不用看源码就可以知道原因，可以维护一个全局的容量大小值size等方法解决，add 操作o（n），其余操作均在线性操作时间内，但是比LinkedList 花的时间少
* <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is
* the size of the array used to store the elements in the list. It is always
* at least as large as the list size. As elements are added to an ArrayList,
* its capacity grows automatically. The details of the growth policy are not
* specified beyond the fact that adding an element has constant amortized
* time cost.
*
* <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
* before adding a large number of elements using the <tt>ensureCapacity</tt>
* operation. This may reduce the amount of incremental reallocation.
*
* <p><strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access an <tt>ArrayList</tt> instance concurrently,
* and at least one of the threads modifies the list structurally, it
* <i>must</i> be synchronized externally. (A structural modification is
* any operation that adds or deletes one or more elements, or explicitly
* resizes the backing array; merely setting the value of an element is not
* a structural modification.) This is typically accomplished by
* synchronizing on some object that naturally encapsulates the list.
*
* If no such object exists, the list should be "wrapped" using the
* {@link Collections#synchronizedList Collections.synchronizedList}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the list:<pre>
* List list = Collections.synchronizedList(new ArrayList(...));</pre>
这一段的中心思想是由于数组不是线程安全的，尤其是在多线程的情况下对数组进行结构上的变化操作，比如添加和删除，人家专门提出来set a value 并不是一个结构化的修改，都需要外部形势的加锁保证线程安全，比如人家的温馨提示是用Collections.synchronizedList(new ArrayList(...)) 方式，内部的实现也就是用了管程的思想之实现-mutex 信号量的实现方式实现的线程安全
* <p><a name="fail-fast">
* The iterators returned by this class's {@link #iterator() iterator} and
* {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a>
* if the list is structurally modified at any time after the iterator is
* created, in any way except through the iterator's own
* {@link ListIterator#remove() remove} or
* {@link ListIterator#add(Object) add} methods, the iterator will throw a
* {@link ConcurrentModificationException}. Thus, in the face of
* concurrent modification, the iterator fails quickly and cleanly, rather
* than risking arbitrary, non-deterministic behavior at an undetermined
* time in the future.
*
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
* throw {@code ConcurrentModificationException} on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <i>the fail-fast behavior of iterators
* should be used only to detect bugs.</i>
*
这一段的思想是在说iterator 支持的快速失败，支持的原理也比较简单，通过一个主要的modcount ，
全局修改量和iterator 里面的expectCount 期待修改量这两者保证强一致性来快速失败，如果多个线程修改了，
但是expectCount 还没有变过来就会马上失败，但是这只是一种很轻的方式快速失败，并不能保证都能成功，
因为从线程安全角度分析，需要考虑三个因素，原子性，可见性和有序性，
首先可见性就不能满足所以不能把他就作为让arraylist 编程线程安全操作的保证
*/
关于arraylist 容器大部分的算法都在上面的解释中了，现在介绍一些需要潜意识就知道的值和操作
扩容的操作。
**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
扩容：其实也是比较简单的，newCapacity = oldCapacity + (oldCapacity >> 1); (oldCapacity >> 1) === oldCapacity / 2 =》 newCapacity = 1.5 * oldCapacity
然后人家还有最大最小的限制，看看这思考的完整性，多学习学习
传统数组和数组容器大比较
在业务开发中其实直接用容器就可以了，因为性能不会损耗到哪里去的同时还不用考虑数组越界的问题，但是如果是底层框架的开发，对性能极其苛刻就需要多用原始数组了，其次容器不支持基本类型的对象，那还是得用原始的最好，因为package还是需要一定性能的损耗的，最后还是具体场景需要具体的分析最优秀
链表的本质
对比上面的数组，链表解决一个什么问题呢？动态扩容相对与数组来说不是很友好，那么链表就不一样了，因为链表的结构是存当前节点的值和下一个节点的地址值，所以他可以无限扩容，因为数据存储的地方是随机的，关于设计链表的思想，可以扩散成四种数据结构，单向链表，单向循环，双向，双向循环链表，所以总结关于循环的特征，就在于解决的问题是不是属于有数据循环特征的情况看是否需要循环，也就是末尾地址的point是否需要指向head 的特征，对于双向和单向，就在于一个时空复杂度的权衡问题，是否需要时间换空间，或者空间换时间，也就是单向和双向的选择的区别
链表的特性
总结一下链表支持的随机访问时间复杂度是o(n) , 知道指针指向的节点，对其进行删除和插入的时间复杂度是o（n），但是删除和插入某个特定的节点，时间复杂度还是o（n），特别是在java容器中，linked 开头的容器基本上都有
* <p>All of the operations perform as could be expected for a doubly-link
* list. Operations that index into the list will traverse the list from
* the beginning or the end, whichever is closer to the specified index.
所以综合在时间的性能上略逊与数组，但是别忘了人家天然支持动态的扩容操作，当你不知道你的容器以后的数据具体的大小的时候，比起每次数组每次扩容的copy操作，链表就比较适合了
java中关于链表思想的容器
说得最多的就是LinkedList，学习前辈对链表如何下手的，有助于提升我们的思维逻辑, 其实简单的方法也可以塑造一些思维可靠性的逻辑，写出bugfree 的代码出来
java 容器中的linked 开头的容器链表基本上都是属于双向链表，在node 节点都是有pre和next pointer
先来看一些简单但是思维性很好的例子
/**
* Links e as first element.
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null) // 这个判断是鲁棒性的判断，如果插入时候是空的需要做判断
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) // 这个判断是鲁棒性的判断，如果插入时候是空的需要做判断
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) { // 注意这里index 是以0开始的
// assert isElementIndex(index);
if (index < (size >> 1)) { // 细节让性能更高效
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
前面的两个分别从头尾节点插入的思考了一下健全性的问题，后面一个node(index) 的就比较有意思多了，可以说是把双向链表的特征发挥到了极致，如果是我写，肯定还是一个o(n)的时间复杂度，但是大佬们利用双向链表把时间复杂度降低到了o(n/2)上，其次如何理解循环也是链表基本功，其实最简单的就是看循环结束的条件和初始化的值，分析一个倒着查找的把，也就是后面的else里面的语句，首先x的初始值就是last，其次循环结束的条件是i == index 的时候就不在执行循环中的查找前驱节点的语句，因为没有必要了，当前x就是index，已经找到了，所以这么理解循环，bugfree的代码就比较容易写出来了,由于java链表容器中没有办法做到真正意义上指针指向某个节点然后进行o（1）时间复杂度的add ，get（index）的操作，只能由index 和size的数据比较的方式尽可能做到减少时间复杂度
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
上面的indexof的方式可以看出linkedlist是允许有null 值的插入的
还有一些由于LinkedList implement Dequeue 的数据结构而有的poll offer peek 等操作，忘了可以看看代码，poll 其实就是相对于peek 在边界线值操作上做了具体的删除操作，offer其实就是对add 操作新一层封装，并且加了bool 的返回值
同时linkedlist listIter是属于fail-fast，因为有checkForComodification() 方法的存在，在Iterator 内会比较expectCount 和modCount 的值，这和数组的实现如出一辙，但是不能保证线程安全，原因可以从原子性和可见性可以分析到的
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
no volatile 的修饰，无法保证可见性，其次checkForComodification() 在cpu层面上并不是原子性的，同时也没有加锁保证互斥
链表和数组到底用哪个？
首先从硬件资源角度分析，数组cpu缓存友好，可以通过cpu预读操作达到一定的性能提升，但是注意场景，单线程情况下才不会出现数据的错误，并且对内存友好，通过寻址方式找到，在同一块区域内，内存碎片少，链表以上优点都没有，并且第二个可以成为缺点，由于存储地方的不确定性，可能会造成内存碎片，对于java ，可能会有gc 频繁的弊端，但是从功能性上分析，链表天然支持动态“无限”扩容，而数组不支持，有预先分配的大小，即便是java 封装的容器可以做到不考虑这些，也是有一层复制再扩容成1.5倍大小的额外时间复杂度的，所以如果是删除和插入非常频繁并且无法预估数据量大小的，可以选择链表，但是链表的方法时间复杂度综合与数组是没有它好的，数组的随机访问时间复杂度的绝对性优势压倒链表
但还是具体情况具体使用分析
思考，用数组和链表分别实现LRU 缓存淘汰算法
网友评论