LinkedList源代码深入剖析

• 除了类集接口之外，类集也是用 Comparator ， Iterator 和 ListIterator 接口。
• 简单地说， Comparator 接口定义了两个对象如何比较；Iterator 和 ListIterator 接口枚举类集中的对象。
• 为了在他们的使用中提供最大的灵活性，类集接口允许对一些方法进行选择。可选择的方法使得使用者可以更改类集中的内容。支持这些方法额类集被称为可修改的（modifiable）。不允许修改其内容的类集被称为不可修改的（unmodifiable）。如果对一个不可修改发类集使用这些方法，将引发一个 UnsupportedOperationException 异常。 所有内置的类集都是可修改的 。
• 调用 add()​​​ 方法可以将对象加入类集，注意 add() 带一个 Object 类的参数。因为 Object 是所有类的超类，所以任何类型的对象都可以被存储在一个类集中。然而原始类型 不行 。例如，一个类集不能直接存储类型 int ，char ， double 等的值。如果想存储这些对象，也可以使用原始类型包装器。

  可以调用 addAll()​​​ 方法将一个类集的全部内容增加到另一个类集中。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

• 可以通过调用 remove()​​​ 方法将一个对象删除。为了删除一组对象，可以调用 removeAll()​​​ 方法。调用 retainAll()​​​ 方法可以将除了一组指定的元素之外的所有元素删除。为了清空类集，可以调用 clear()​​​ 方法。
• 通过调用 contains()​​​ 方法可以确定一个类集中是否包含了一个指定的对象。
• 为了确定一个类集是否包含了另一个类集的全部元素，可以调用 contsinsAll()​​ 方法。
• 当一个类集是空的时候，可以通过调用 isEmpty()​​ 方法来予以确定。
• 调用 size()​​ 方法可以获得类集中当前元素的个数。
• ​toArray()​ 方法返回一个数组，这个数组包含了存储在调用类集中的元素。通过再类集合数组之间提供一条路径，可以充分利用这两者的优点。
• 一个更加重要的方法是 iterator()​ ，该方法对类集返回一个迭代程序。当使用一个类集框架时，迭代程序对于成功的编程来说是至关重要的。
• ​Collection​ ：集合层次中的根接口，JDK 没有提供这个接口的直接实现类。
• ​Set​ ：不能包含重复的元素。SortedSet​ 是一个按照升序排列元素的 Set​ 。
• ​List​ ：是一个有序的集合，可以包含重复的元素。提供了按照索引访问的方式。
• ​Map​ ：包含了 key-value 对。Map 不能包含重复的 key 。SortedMap​ 是一个按照升序排列 key 的 Map​ 。

​文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

• ​List​​​ 接口扩展了 Colection​​​ 并声明存储一系列元素的类集的特性。使用一个基于零的下表，元素可以通过他们在列表中的位置被插入和访问。一个列表可以包含重复元素。
• 除了由 Collection​​​ 定义的方法之外，List 还定义了一些它自己的方法。再次注意当类集不能被修改时，其中分几种方法引发 UnsupportedOperationException 异常。当一个对象与另一个不兼容，例如当企图将一个不兼容的对象加入一个类集当中时，将产生 ClassCastException 异常。
• 对于由 Collection​​​ 定义的 add()​​​ 和 addAll()​​​ 方法，List 增加了方法 add(int, Object)​​​ 和 addAll(int, Collection)​​​。这些方法在指定的下标处插入元素。由 Collection​​​ 定义的 add()​​​ 和 addAll()​​​ 方法的语义也被 List 改变了，以便他们 在列表的尾部增加元素 。
• 为了获得在指定位置存储的对象，可以用对象的下标调用 get()​ 方法，为了给元素赋值，可以调用 set()​ 方法，指定被改变对象的下表。调用 indexOf()​ 和 lastIndexOf()​ 可以得到一个对象的下标。
• 通过调用 subList()​ 方法，可以获得列表的一个指定了开始下标和结束下标的子列表。subList()​ 方法使得列表处理十分方便。

• 集合接口定义了一个集合。它扩展了 Collection​ 并说明了不允许重复元素的类集的特性。因此，如果试图将重复元素加到集合中时，add() 方法将返回 false 。它本身并没有定义任何的附加方法。

• ​SortedSet​ 接口扩展了 Set​ 并说明了按照升序排列的集合的特性。当没有项包含在集合中时，其中的几种方法引发 NoSuchElementException 异常。当对象与调用集合中的元素不兼容时，引发 ClassCastException 异常。如果试图使用 null 对象，二集合不允许 null 时，引发 NullPointerException 异常。
• ​SortedSet​ 定义了几种方法，使得对集合的处理更加方便。调用 first()​ 方法，可以获得集合中的第一个对象。调用 last()​ 方法，可以获得集合中的最后一个元素。调用 subset()​ 方法，可以获得排序集合的一个指定了第一个和最后一个对象子集合。如果需要得到从集合的第一个元素开始的一个子集合。可以使用 headSet()​ 方法。如果需要获得集合尾部的一个子集合，可以使用 tailSet()​ 方法。

• 类集接口的标准类一些提供了完整的可使用的工具，另一些是抽象的，提供主框架工具，最为创建具体类集的起始点。

• ​ArrayList​​​ ：我们可以将其看做是能够自动增长容量的数组。
• 利用 ArrayList​​​ 的 toArray()​​​ 返回一个数组。
• ​Arrays.asList()​​​ 返回一个列表。
• 迭代器（Iterator）给我们提供了一种通用的方式来访问集合中的元素。
• ​ArrayList​ 继承自 AbstractList​ 并实现了 List​ 接口。

  ​ArrayList​ 支持可随需要增长的动态数组。在 Java 中，标准数组是定长的。在数组被创建后，它们不能被加长或者缩短，这意味着必须事先知道需要定义多大的数组。为了解决这个问题，类集框架定义了 ArrayList​ 。 本质上，ArrayList 是对象引用的一个变长数组 。也就是说，ArrayList​ 可以动态地增加或者减小其大小。ArrayList​ 以一个原始大小被创建，当超过了它的大小，类集自动增大。当对象被删除后，数组可以缩小。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

• ​ArrayList​ 有如下的构造函数文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  • ​ArrayList()​
  • ArrayList(Collection c)​
  • ArrayList(int capacity​
  • 第一个构造函数建立一个空的数组列表。
  • 第二个构造函数建立一个数组列表，该数组列表由类集 c​ 中的元素初始化。
  • 第三个构造函数建立一个数组列表，该数组有指定的初始容量（capacity）。容量是用于存储元素的基本数组的大小。当元素被追加到数组列表上时，容量会自动增加。
• 尽管当对象被存储在 ArrayList()​​ 对象中时，其容量会自动增加。仍然可以通过 ensureCapacity()​​ 方法来人工地增加 ArrayList​​ 的容量。

  如果事先知道将在当前能够容纳的类集中存储许多项时，可能会这么做。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  在开始时，一次性增加它的容量，可以避免后面的再分配。因为再分配比较花时间，避免不必要的处理可以改善性能。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

• ​ensureCapacity()​ 方法如下文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  • ​void ensureCapacity(int cap)​ ，这里，cap 是新的容量
• 相反的，如果想要减小在 ArrayList​ 对象之下的数组的大小，以便它有真正正好容纳当前项的大小，可以调用 trimToSize()​ 方法。该方法如下：

  ​void trimToSize()​文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

• ​LinkedList​ 类继承自 AbstractSequentialList​ 并实现了 List​ 接口。他提供了一个 链表 数据结构。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  它具有两个狗在函数，说明如下：文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  • LinkedList()​
  • LinkedList(Collection c)​
  • 第一个构造函数建立一个空的链表
  • 第二个构造函数建立一个链表，该链表由类集 c 中的元素初始化。
• 除了它继承的方法之外，LinkedList​ 类本身还定义了一些有用的方法，这些方法主要用于操作和访问列表。

  使用 addFirst()​ 方法可以在列表头增加元素；使用 addLast()​ 可以在列表的尾部增加元素。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  它们的形式如下：文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  • void addFirst(Object obj)​
  • void addLast(Object obj)​
  • 这里，obj 是被增加的项
• 调用 getFirst()​ 方法可以获得第一个元素。调用 getLast()​ 可以获得最后一个元素。

  它们的形式如下：文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  • Object getFirst()​
  • Object getLast()​
• 为了删除第一个元素，可以使用 removeFirst()​​ 方法；为了删除最后一个元素，可以调用 removeLast()​​ 方法。

  他们的形式如下：文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  • ​Object removeFirst()​​​
  • ​Object removeLast()​​​
  • 示例 1

  import java.util.LinkedList;
  
  public class LinkedListTest1 {
  
      public static void main(String[] args) {
          LinkedList list = new LinkedList();
  
          list.add("F");
          list.add("B");
          list.add("D");
          list.add("E");
          list.add("C");
  
          list.addLast("Z");
          list.addFirst("A");
  
          list.add(1, "A2");
  
          System.out.println("最初的集合：" + list);
  
          list.remove("F");
          list.remove(2);
  
          System.out.println("变化之后的集合：" + list);
  
          Object value = list.get(2);
          list.set(2, (String)value + "changed");
  
          System.out.println("最后的集合：" + list);
  
      }
  }
  

  因为 LinkedList​​ 实现 List​​ 接口，调用 add(Object)​​ 将项目追加到列表的尾部，如同 addLast()​​ 方法所做的那样。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  使用 add()​​ 方法的 add(int, Object)​​ 形式，插入项目到指定的位置，例如上面例子的 add(1, "A2")​​文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  注意如何通过调用 get()​​ 和 set()​​ 方法而使得 LinkedList​​ 中的第三个元素发生了改变。为了获得一个元素的当前值，通过 get()​​ 方法传递存储元素的下标值。为了对这个下标位置赋一个新值，通过 set()​​ 传递对应的下标和新值。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  • 运行结果

  最初的集合：[A, A2, F, B, D, E, C, Z]
  变化之后的集合：[A, A2, D, E, C, Z]
  最后的集合：[A, A2, Dchanged, E, C, Z]
  

• ​LinkedList​ ​是采用双向循环列表实现的。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html
• 利用 LinkedList 实现栈(stack)、队列 (queue)、双向队列(double-ended queue )。

• 一般将数据结构分为两大类：线性结构 和 非线性结构 。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  线性数据结构有 线性表、栈、队列、串、数组和文件；非线性数据结构有 树和图。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

• 线性表的数据结构是 n 个数据元素的有限序列：文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  $\left( {{{\rm{a}}_1},{a_2} \cdots {a_n}} \right)$文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

• n 为线性表的长度（$n \ge 0$）, n=0 的表称为空表。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

• 数据元素呈线性关系。必存在唯一的一个称为 “第一个” 的数据元素；必须在唯一的一个称为 “最后一个” 的元素；除第一个元素外，每个元素都有唯一的一个先驱元素，除最后一个元素外，每个元素都有且只有一个后继元素。
• 所有数据元素在同一个线性表中必须是相同的数据类型。

• 线性表按照其存储结构可以分为 顺序表 和 链表 。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  用顺序存储结构存储的线性表称为 顺序表 。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  用链式存储结构存储的线性表称为 链表 。文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

• 将线性表中的数据元素依次存储在某个区域中，所形成的表称为 顺序表 。一维数组就是用顺序方式存储的线性表。

• 单向链表文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  ​文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  插入 ​文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  删除​文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  ​文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

• 循环链表文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  ​文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

• 双向循环链表文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

  ​文章源自浅海拾贝-https://blog.terwergreen.com/linkedlist-source-code-in-depth-analysis-z2jmwit.html

• 栈（Stack）也是一种特殊的线性表，是一种后进先出（LIFO）的结构。
• 栈是限定仅在表尾进行插入和删除运算的线性表，表尾成为栈顶（top），表头成为栈底（bottom）。
• 栈的物理存储可以用顺序存储结构，也可以用链式存储结构。