1. LinkedList class-SPL

1.1 LinkedList vs. Vector

在SPL中，LinkedList类提供了与SPL中的Vector一样的方法。Vector的一些常用方法LinkedList都有。

Linked List ：由节点组成，每个节点都存储了一个值和一个指向下一个节点的next指针。在内部，这个链表只知道head node（有时是tail node），但是可以重复通过next指针去不断地前进。

# include "list.h" // SPL

LinkedList<int> list;
for (int i = 1; i <= 8; i++) {
	list.add(10*i);
}

既然LinkedList与Vector提供了几乎一样的方法，那为什么还要设计LinkedList呢，有Vector不是够了吗？

原因在于，这两种collection的内部，是用不同的方法构建与实现的：

• Vector对象的内部是由array构建的，这意味着一大块连续的内存，即在物理上是连续的。
• 由于LinkedList中的对象是用指针（Pointer）连接在一起的，所以他们在物理上的位置不必是连续的。

1.2 LinkedList Insert

在LinkedList中执行插入操作时，我们必须遍历LinkedList来确认该insert操作的位置，不能像vector那样可以直接指定位置进行插入。二者插入操作的时间复杂度可以总结如下：

• vector中的插入：找到目标位置是O(1)，移动元素O(N)。
• LinkedList中的插入：找到目标位置是O(N)，移动元素是O(1)。

此外，对于Remove，get等等的方法，二者调用的函数名称也一致，根据不同情况选择适合的collection。（如：要进行的操作大多是在头部进行的，那么肯定选择LinkedList，因为在头部进行增删操作时，LinkedList的时间复杂度是O(1)）

但是在大多数的场景下，vector比LinkedList更加的常用。

2. Abstract data types（ADTs）

2.1 Concepts

abstract data type(ADT):一个关于数据集合及其可执行操作的规范说明。.

• 描述了一个集合可以做什么，而不是它如何做到的。
• 对于同一个ADT，大多数编程语言都会有多种代码实现。如我们可以说向量（Vector）和链表（Linked List）都实现了被称为“列表”（list）的抽象数据类型（ADT）的操作。
• 其他一些抽象数据类型的例子包括：栈（stack）、队列（queue）、集合（set）、映射（map）、图（graph）。

我们并不总是知道一个给定集合在内部是如何实现的，而且我们也不需要知道。

• 我们只需要理解这个集合的概念以及它能够执行哪些操作即可。

只是一个很简短的介绍，在未来的课程中，我们会有机会深入的了解ADT与LinkedList的。