用于记录一下学习链表部分时个人觉得应该记下来的东西以及自己的一些感悟。
总体感悟
断断续续把cs61b的链表部分看完了，这门课其实主要是带你边写代码边把数据结构给实现，所以这里其实忽略了一个学之前我们需要注意的点：这门课怎么学？数据结构部分的课程与学习逻辑是怎样的？
我的感悟是：“数据结构”本身是一个抽象的概念，是人们设计出来用于存储数据的一种抽象结构，而这种抽象结构可以通过代码来实现。所以我们学习时，认知的顺序应该是：首先明白数据结构的特点，然后再学习如何用代码进行实现。
链表是什么？
链表是一种由节点前后之间连接而成的线性非连续数据结构。
线性意味着链表的节点并不是两两连接的，而是一个接一个，有某种意义上的前后顺序。
这里引出一个问题：节点间是怎么连接的？（这个问题也能解释为什么链表是线性的和有先后顺序的）
首先要了解一段历史，链表的提出是为了解决向“数组”这种连续型数据结构中间存放数据时的局限性发明的。传统的数组（Array）存在一个很大的问题：如果要在数组中间插入或删除一个元素，需要移动后面所有的元素，这在内存资源有限的早期计算机上效率非常低。因此链表被发明。
链表为了解决这一问题，采用的是非连续性的内存结构，一个链表由若干个节点构成。每个节点间同时保存前一个或者后一个或者前后节点的内存地址以及数据内容。而节点间就通过自身对上一个或者下一个或者两端的节点地址形成了相互连接，具有前后位置的非连续型（也就是每个节点的内存地址并不是连续的）链状数据结构。
至此，我们明白了以下的重点：
链表由若干节点组成。每个节点存储两样东西：相邻节点的内存地址和数据内容。
在对链表进行遍历时，通过访问每个节点存储的内存地址来对链表进行遍历。
以及另外，每种数据结构都离不开增删改查这四种操作，一个最基本的链表应该满足这四种方法。
几种常见的链表分类
按存储地址分类
- 单向链表 节点只保存指向下一个节点的地址
- 双向链表 节点保存指向下一个和上一个节点的地址
按首尾分
- 条状链表 在结构上有明确的开头(head)和结尾(tail)，head的prev指向null，tail的next指向null
- 环状链表 在结构上，开头和结尾是同一个节点，head的prev指向tail，tail的next指向head
具体实现时的两种链表
- LinkedList:用类(结构体)完全实现链表的结构(存储内容和地址)
- ArrayList:用数组模拟链表的结构(这种链表并没有解决上述的数组存储局限问题，但是我看cs61b没提)
环状链表二三事
本人在完成proj1的ArrayDeque时，使用的是环状的ArrayList，这里来回顾一下总体的设计思路。
- 为什么要选用环状的结构？
传统的数组在队头进行操作（addFirst, removeFirst）时，需要移动后续所有元素，导致时间复杂度为 O(N)，效率低下。我们的设计的根本目标，就是将所有队头和队尾操作的时间复杂度都优化到均摊 O(1)。
- “环状”体现在哪？
所谓“环状”，指的是Deque的head和tail并不与Array的某个特定的index绑定，而是动态发生变化的。从逻辑上，当你向一个index = 0 的位置已经有了item的Array进行addFirst时，新添加的item会被放在Array的末尾位置，模拟出了逻辑上的环状结构。
- 如何实现？
通过2.中的操作，我们实现了逻辑上的环状结构，但是为了保持链表中item的正确顺序，我们需要正确地维护head和tail，让他们实时指向链表item序列的头和尾。
为了实现这一点，需要引入两个用来指示head和tail的变量，变量类型为int，通过计算出正确的index来标示head和tail。
我们在这里选用闭区间型head和tail，也就是说head和tail指向第一个item和最后一个item的index，而不是下一个addFirst和addLast时新的item应该被放入的index，这样做有利于我们的遍历操作。
为了保持head和tail时刻指向正确的index，我们需要在每次addFirst，addLast以及removeFirst和removeLast操作后对head和tail进行更新。
公式(head和tail的更新公式)：
- add方法里的更新
head = (head - 1 + array.length) % array.length;tail = (tail + 1) % array.length;- remove方法里的更新
head = (head + 1) % array.length;tail = (tail - 1 + array.length) % array.length;- 难点
()方法的实现
当数组存放满后，需要新建一个容量为原来两倍的新数组，并把原先的元素放进去并重新设定head和tail。创建数组和设定head和tail并不难，难点在于如何以正确的顺序遍历原先的环状Deque。arraycopy方法是按照array的index从小到大遍历的，所以需要分析环状的Deque结构的顺序遍历如何转化成array的遍历。
两种情况：“断开”与“不断开”
“断开”的意思指的是，array的0号位置和size - 1号位置把环状结构切开了，这种情况下head跑到了tail的后边(head > tail)
“断开”的情况下： 需要进行两次复制。 第一次复制：从head到size - 1 第二次复制：从tail到0
“不断开”的情况： 这种情况下，index = 0的位置就是head，可以直接使用arraycopy顺序复制。
最后将head设置为0，tail设置为size - 1即可。
- 一个小点点，优雅的T get(int index):
核心逻辑：物理地址 = (head + 逻辑偏移) % 数组长度 代码实现：
return array[(head + index) % array.length];总结：ArrayDeque 是一个基于环形数组和指针移动的高效实现。它通过size 变量解决了空满判断问题， 通过两次 arraycopy 实现了无循环的 resize，并通过一个优雅的数学公式提供了高效的 get 方法， 最终使得整个数据结构健壮、高效且易于扩展。(Gemini如此夸赞我道)