======ArrayLists, LinkedLists, Stacks and Queues======
//Gtx CS1332x I Notes//
----
====Introduction====
===Value/Reference Equality===
* Reference Equality: 查看两个对象是否为同一个对象（处于同一片内存区域），使用 ''=='' 检测
* Value Equality：按照用于自定义的规则来判断两者是否等价。使用自定义的，重写自 ''Object'' 类的 ''equals()'' 方法来判断。
==等价对象的的区别==
上面两种比较的主要应用发生在 Primitives type 与 Object type 之间。
* primitive type：没有值和引用相等的区别，因此都用 ''=='' 来判断：
int one1 = 1;
int one2 = 1;
int two1 = 2;
one1 == one2; // => true
one1 == two1; // => false
String literals：String literal 会以常量的方式存储在 String pool 中。通过赋值创建的 String Literal 也没有值和引用等价的区分：
String literal = "This is a string.";
literal == "This is a string."; // => true
但如果以对象的方式创建 String Literal (或者说是以 String Literal 为初始值创建对象)，那么值等价和引用等价是会区分开的。
//ref equality
String object = new String("This is a string.");
object == "This is a string.";
//value equality
object.equals("This is a string."); // => true
==Null Checking==
* Object 是否为 ''null'' 使用 ''=='' 来确定（null & 非 null 对象均可使用）
String nullObject = null;
nullObject == null; // => true
* 如果对象为 ''null''，调用 ''equal()'' 会导致 //NPE //（NullPointerException ）异常
* 非 ''null'' 对象可以调用 ''equal()'' 与 null / null 对象比较
String normalObject = "normal";
normalObject.equals(null); // => false
nullObject.equals(normalObject); // causes NullPointerException
==Wrapper Objects==
* 某些场景需要使用 primtive type 对应的对象。这类对象被称为 //Wrapper Objects//
* Java 会通过 autoBoxing / unboxing 自动进行转换
Wrapper Objects的比较 与 String Literal 类似，也分值等价和引用等价两种情况：
* Literal 的比较是值的比较
Integer primitive = 1;
Integer object = new Integer(1);
primitive == 1; // => true
object == 1; // => true
* Object 的比较是引用的比较
primitive == object; // => false
primitive.equals(object); // => true
object.equals(primitive); // => true
===Pass by Value/Reference===
* Pass By Value：传递的是值，更改 parameter 不影响 argument
* Pass By Reference：传递的是引用，更改 parameter 影响 argument
* Java 是 passing by value language.
* 传递 Object 的时候，实际上是值传递；但传递的是 Object 所在地址的拷贝。因此可以通过该拷贝去更改原有 Object 的内容，这就是所谓 Java 中的 Pass by referenece with object。
===Generics===
==ClassCastException==
指在运行期，对象类型与生命类型不匹配。解决方式：使用带 type parameter 的特化版本：
public class Container {
private T t;
public void set(T t) {
this.t = t;
}
public T get() {
return t;
}
}
特化版本会在编译器确定类型是否匹配。
==Generics Syntax==
* Declaring Generic Classes
//def
class ArrayList { ... }
//declar
ArrayList listOne = new ArrayList<>();
==Generic Arrays==
//declar
T[] backingArray = (T[]) new Object[10];
==Multiple Type Parameters==
class HashMap { ... }
HashMap map = new HashMap<>();
==Generic Classes as Type Parameters==
ArrayList> nodeList = new ArrayList<>();
===Iterable and Comparable===
Docs:[[https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html|Iterable]] | Docs:[[https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html|Iterator]]
==Iterable interface==
Java 提供了 //Iterable// 接口；任何实现该接口的类都可以使用 for-each loop。使用需要导入 ''java.util.iterator''\\ \\
实现上：
* 需要重写 ''iterator()'' 方法，该方法会返回一个 iterator 对象。
//Iterator// 也可以单独使用。需要重写的方法：
* 需要重写 ''next()'' 方法：返回当前 iterator 指向的对象，然后将 iterator 移动至下一个对象
* 需要重写 ''hasNext()'' 方法：当 iterator 指向的对象值不为 ''null'' 时，返回 ''true''
* 可选重写 ''remove()'' 方法：移除 ''next()'' 返回的对象
两种简单的示例如下：
* 显式的使用 //Iterator//：
import java.util.Iterator;
public class BookList implements Iterator {
//override
public void next() {}
public boolean hasNext() {}
public static void main(String[] args) {
//usage suppose bookList is an object with type BookList
while(bookList.hasNext())
{
System.out.println(BookList.next());
}
}
}
* 使用 //Iterable//：
public class BookList implements Iterable {
//In this case, Iterator function needs to be override
public Iterator Iterator() {....}
public static void main(String[] args) {
}
for(Book book : bookList) {
System.out.println(book);
}
}
可见 //Iterable// 是基于 //Iterator// 实现的。
==Comparable and Comparator==
* 两者都是独立实现的，并不互相依赖
* ''Comparable'' 允许直接将自身与目标进行比较（使用 ''comareTo'' 方法，单参数）
* 允许实现类基于返回值定义 //Nature Ordering//（**升序**）
//public int compareTo(T y) ;
x.compareTo(y);
* ''Comparator'' 并不比较自身与目标，而是比较两个参数（使用 ''compare()'' 方法，双参数）
* 允许实现类基于返回值定义 //Ordering//。这个顺序可以是基于任何值自定义的，与 //Nature Ordering// 有区别：
* 比如基于学生的年龄进行降序排列
* 比如基于学生专业的第一个字母进行基于 alphabet 的顺序排列
public int compare(T x, T y);
comp.compare(x, y);
两者的返回值意义相同：
* 负数：x < y
* 0：x = y
* 正数：x > y
实现上：
* ''Comparable'' 的实现需要实现 ''Comparable'' 接口，并重写 ''compareTo'' 方法
* ''Comparable'' 已经包含在 ''java.uitl'' 中，因此不需要任何导入
public class HDTV implements Comparable{
....
public int compareTo(HDTV tv) {
....
}
}
* ''Comparator'' 的实现需要导入 ''java.uitl.Comarator''
* ''Comparator'' 需要实现的接口是 ''Comparator''，需要重写 ''compare()''，接收的是两个参数
class SizeComparator implements Comparator {
public int compare(HDTV tv1, HDTV tv2) {
//....
}
}
* 进行对象比较的时候使用 ''compareTo''，而不是关系运算符
* ''compareTo()'' 的返回值通常是正 / 负 / 零，而不是 [-1,0,1]
===Big-O Concepts===
* 算法&数据结构的效率通过时间和空间两个方面进行衡量
* 衡量是独立的，与平台无关。
* 衡量只研究输入规模变更时，算法的变化
==High Level Description==
算法在高级层面上通过如下的基础操作（//primitive instruactions//）进行衡量：
* 赋值
* 算术运算
* 比较两个实体
* 函数的调用、函数的返回
* 访问、引用数据结构
这些基础操作的共同点是，都能在**常数时间**内完成。因此，统计他们的总次数，就能直观的反应算法的复杂度。
==以函数的形式来衡量效率==
* $f(n)$ 代表了在输入大小为 $n$ 时，**基础操作的总数**
* 三种要考虑的情况：
* worst case （本课主要的讨论点）
* best case
* Avergae case
==Big-O notation & Common Complexities==
// //
{{ :cs:dsa:courses:gtx_1332x:i_lists:complecity.jpg |}}
Big-O 在本课中代表 tightest upperbound。
==其他符号==
* $o(f(n))$：long-term performance is **significantly** upperbounded by f(n)。主要强调的是算法复杂度增长的很慢。
* $\Omega(f(n))$：$f(n)$ 被当做了衡量解决一个问题的难度；也就是告诉我们，解决该问题付出什么样的成本是合理的。
* $\Theta(f(n))$：$f(n)$ 同时作为 upperbound 和 lowerbound。不是所有的算法都有该复杂度，因为该复杂度需要算法足够稳定。
===Conventions===
* 常量因子会被省略：比如 $O(5n)$ = $O(n)$
* 非 domiate 的项会被省略：比如 $O(n^2+100n-3) = O(n^2)$
* $log(n)$ 的 base 通常是 $2$
常数因子 & low order term 在很多特定的条件下是需要考虑的（比如限定了输入次数的场景）。
====ArrayLists and Recursion====
===Arrays===
* 在内存中连续存储
* 通过 index 访问元素，访问的复杂度是 $O(1)$
* 内存是静态分配的，如果超出了需要申请新的，更大的连续空间，然后将元素全部拷贝过去。拷贝的复杂度是 $O(n)$
为什么访问 array 元素的复杂度是 $O(1)$？
* 存储空间是连续的
* Array 会存储其内存入口地址（首元素 ，index 0）
* Array 的长度是确定的
因此，只需要三次次算术运算 (new_address = start_address+i * data_size) 即可获取当前访问元素的地址；所以复杂度为 $O(1)$
==Abstract Data Types(ADT)==
* 抽象数据类型（//ADT//）是一种描述数据类型的模型，通过其行为和操作定义。在 Java 中，//ADT// 与 Interface 类似（有定义，但没有具体的实现）。
* //ADT// 避免了在讨论需求的时候过多的陷入细节
* 不涉及算法的具体实现和效率（数据结构才做这些讨论）
* 数据处理的具体实现被称为数据结构
===ArrayLists===
* Generic type（只支持 object 类型）；使用时需要指定对象类型（可以被视作是 array 的 wrapper）
* 基于 Array 实现的 List，会自动 ''resize''，空间增长会申请全新的空间，并将旧元素拷贝过来
* 数据是连续存储的，初始大小为 ''10''
* 定义于 ''java.util''
==ArrayLIst 的定义==
ArrayList list = new ArrayList<>();
==Size 和 Capacity==
* Size 指 ArrayList 中**已经**存在的元素数量
* Capacity 指 ArrayList 中可以存放的元素**上限**
==一些要求==
* 存储是连续性的（中间有 ''null'' 是不行的）
* zero-aligned（必须存在首元素）
==Add to the Back==
* $O(1)$
* 如果要求 resize，则是 $O(n)$
由于 resize 不是经常发生的，因此 add to the back 的复杂度可以按照 //amortized analysis// 进行分析；也就是将 resize 的 $O(n)$ 视作多次 $O(1)$ 的操作。因此，可以说 add to the back 的效率为 $\texttt{amortized}(O(1))$ 。
==Adding elsewhere==
* $O(n)$：需要移动元素的同时保证已有元素内容不被覆盖。
==RemoveAtIndex==
* remove from the back: $O(1)$
* remove from elsewhere $O(n)$
===Amortized Analysis===
//Amortized Analysis// 是一种关注于**平均**计算成本的分析方法。通常的方法是以操作为单位来衡量计算成本，但有的时候某些高成本的操作出现的几率并不是很大，因此这种情况下使用此类操作来作为 worst case 讨论该算法的意义并不是很大。
\\ \\
以之前的 addToTheBack 为例，通常操作的复杂度为 $O(1)$，而 resize 时的复杂度为 $O(n)$；由于 resize 并不是很常见，那么以 $O(n)$ 来衡量 addTOTheBack 的复杂度显然不太精确。这种情况下，我们可以采用 //Amortized Analysis// 的方法来进行分析
* 首先需要分析 worst case 的情况分哪几种：\\
* 如果没有 resize，每次 addToTheBack 只有两次操作：添加元素和增加 size 的计数。 那么 addToTheBack 的复杂度为: $$\texttt{Amortized Cost} = \frac{\texttt{Total cost of all operations}}{\texttt{times of operations}} = \frac{2n}{n} = 2 = O(1).$$
* 如果发生了 resize：如果存在 $n$ 个元素，那么 resize 之后的 capacity 是 $2n$，那么对于每个元素来说，包含了 4次操作：
* resize 有两次操作：访问元素，将元素拷贝到新的 arrayList
* addToTheBack 有两次操作：添加元素，size 计数加一
* 因此对于 $n$ 次操作，其 //Amortized Cost// 的计算方式为：$$\begin{align*} \texttt{Amortized Cost} &= \frac{\texttt{Total cost of all operations}}{\texttt{times of operations}} \\ &= \frac{\texttt{Resize Cost} + \texttt{Normal Operation Cost}}{n} \\ &= \frac{2n + 2n}{n} = 4 = O(1). \end{align*}$$
以上两种复杂度都可以用于描述 addToTheBack 。如果需要强调该算法是基于 //Amortized Analysis// ，通常使用 $O(1)^*$ 来标注。
==Soft v. Hard Removals==
* Soft Removals: 被删除的数据会被保留在数据结构中
* Hard Removals：被删除的数据会被完全移除出数据结构，并在必要的时候手动设置 ''null'' 作为代替
除非特别必要，本课程中均为 hard removeal。
===Recursion===
函数调用自身的方式被称为 Recursion。
==三大要素==
* Base Case：必须至少有一个，作为递归终结的条件。
* Recursive Case：用于调用自身。当递归调用发生的时候，当前层的递归会暂停，知道调用返回结果以后才会继续运行。
* Progress to Base Case：所有的递归调用必须都往终结条件方向前景。
==基本结构==
if (baseCase) {
//termination
}
else {
// recursive call logic
}
==SubProblem==
递归的一大重点就是将问题分解为子问题。一些策略：
* 先写出 base case, 再写出其他的递归方法
* 避免 base case 重复
* 将程序清晰的分解为不同的 case
==最大公约数问题(The greatest common denominator problem)==
使用递归形式的**辗转相除法**（//Euclidean algorithm//）：
* Base case: 余数 ''x mod y== 0''
* Recursive case: ''gcd(x,y) = gcd(y, x mod y)''
====LinkedLists====
* 链表（//LinkedLists// ）由一系列的节点（//Node//）组成。数据存放在节点中。
* 链表中，前后节点通过指针链接。
* 链表不需要连续的存储空间。
===链表的成员===
==必要的指针==
* ''head''：指向链表的头元素
* ''current''：在遍历中，指向当前元素
* （可选）''tail''：指向链表的尾部元素
==计数器==
* ''size''：记录链表的长度
* 添加元素的时候 ''size'' 加一
* 删除元素的时候 ''size'' 减一
==Node class==
* 成员：数据 ''T data''，指向下个节点的指针 ''Node next''
* 方法：构造函数
===链表的遍历===
链表的遍历基于 ''head'' 和 ''current''：
* 起始条件（位置）为 ''current = head''
* 结束条件（位置）为 ''current == null''
* 循环条件：当当前节点的下一个节点不为空时，将下一个节点作为当前节点。
while (current != null) {
current = current.next;
}
===链表的方法===
==AddingToFront==
**//算法步骤：//**
- 创建需要插入的节点
- 将创建的节点的 ''next'' 指向 ''head'' 指向的内容
- 将 ''head'' 原有的指向变更为被创建的节点
**//边界条件：//** \\
无。
{{ :cs:dsa:courses:gtx_1332x:i_lists:link_list_addtofront.svg?300 |}}
public void addingToFront(T data)
{
Node newNode = new Node<>(data);
newNode.next = head;
head = newNode;
}
==AddingToBack==
**//算法步骤：//**
- 判断 list 是否为空。如果为空，直接创建节点
- 否则，遍历到 List 的最后一个元素（''while(current.next != null)''）
- 循环结束后，创建节点，并将最后一个元素的 ''next'' 指向新创建的节点
**//边界条件：//**
* 链表为空的时候不需要遍历，直接将 ''head'' 指向新创建的节点即可。
{{ :cs:dsa:courses:gtx_1332x:i_lists:linked_list_addtoback.svg?350 |}}
public void addingToBack(T data)
{
if(head == null) {
head = new Node (data);
}
else {
Node current = head;
while(current.next != null) {
current = current.next;
}
current.next = new Node (data);
}
}
注意循环条件是 ''while(current.next ！= null)'' 而不是 ''while(current == null)''：
* 前者保证的是 ''current'' 在循环**之后**还是有效的，可以被操作的节点。循环完毕后，''current'' 指向尾节点。
* 后者保证的是 ''current'' 在循环**中**是有效的，可以被操作的节点。循环完毕后，''current'' 不指向任何有效的节点。
因为 //addingToBack()// 的添加元素实现要求 ''current'' 在循环后有效，因此使用 ''current.next'' 作为判定条件。
==RemoveingFromFront==
**//算法步骤：//**
- 如果链表为空，返回 ''null''
- 将 ''head'' 重新指向第二个节点即可
**//边界条件：//**
* 链表为空，返回 ''null''
{{ :cs:dsa:courses:gtx_1332x:i_lists:linked_list_removingfromfront.svg?300 |}}
public void removingFromFront()
{
if(head == null) {
return;
}
else {
head = head.next;
}
}
返回 ''null'' 使用 ''return;'' 语句
==RemoveingFromBack==
**//算法步骤：//**
- 如果链表为空，返回 ''null''
- 如果链表只有一个节点，删除节点后 ''head = null''
- 否则，遍历链表到**倒数第二个节点**
- 将倒数第二个节点的 ''next'' 指向设置为 ''null''
**//边界条件：//**
* 链表为空，返回 ''null''
* 链表只有一个节点，删除节点后 ''head = null''
{{ :cs:dsa:courses:gtx_1332x:i_lists:linked_list_remove_from_back.svg?300 |}}
public void removingFromBack()
{
if(head == null) {
return;
}
else if (head.next == null) {
head = null;
}
else {
Node current = head;
while(current.next.next != null) {
current = current.next;
}
current.next = null;
}
}
''while(current.next.next != null)'' 确保循环结束后，''current'' 指向倒数第二个节点。因为删除最后一个节点需要对倒数第二个节点进行操作。
===Optimization==
==Tail reference==
* ''tail'' 指针指向链表中最后一个节点。维护该指针可以在使用 //addingToBack()// 的时候避免重复遍历链表（$O(n)$ to $O(1)$）
* ''tail'' 指针对 //removeFromBack()// 没有任何优化。该方法需要访问倒数第二个节点，而不是最后一个节点。
* ''tail'' 指针使用的边界条件：
* 当链表为空时：''head'' 和 ''tail'' 都应该为 ''null''
* 当链表只有一个节点时：''head'' 和 ''tail'' 都指向该节点。如果试图删掉该节点，那么 ''head'' 和 ''tail'' 都应该为 ''null''
===LinkedLists in Code===
==Iterable in LinkedLists==
* 需要一个实现 ''Iterable'' 的类
* 需要一个实现 ''Iterator'' 的类，用于支持 ''Iterable'' 中的 ''Iterator()'' 方法的重写
* 在实现 ''Iterator'' 的时候需要重写：
* ''next()''
* ''hasNext()''
结构如下：
{{ :cs:dsa:courses:gtx_1332x:i_lists:linke_list_iterable.svg?200 |}}
{{ :cs:dsa:courses:gtx_1332x:i_lists:iterlinkedlist.java |Demo Code}}
==Recursion in LinkedLists==
//**问题描述**：//\\ \\
给定有序链表，以递归的方式移除列表中所有重复的元素。\\ \\
//**相关思考**：//\\ \\
递归的关键点就是将大问题分解为性质相同但规模更小的子问题。这个问题中，判断是否重复的行为最终都会转变为两个对象之间的比较。那么在递归的设计上，主要需要实现两点：
* 如何通过递归的方式来进行比较
* 比较的逻辑
//**实现思路**：//\\ \\
首先应该对递归的状态进行建模。具体的问题就是：
* 递归的输入是什么？输出是什么？
* 递归是如何通过输入输出来缩小目标问题的规模的？
对于 list 的来说，子问题通常来说就是其 sublist。本例中的数据结构是链表，那么不难想到的是：
* 本题的 sublist 都应该是与目标链表 ''head'' 相同，但长度不同的子链表
* 缩减链表的方向因该是**自尾部向头部进行**
根据这个思路，再来考虑一下递归的输入和输出。sublist 是通过移除重复的对象来进行缩减的，而重复的判定是通过**相邻**的两个对象比较来进行的。如果希望递归完成这个过程，那么递归的参数和返回值都应该是进行比较的对象：
* 接收的参数参与当前的比较
* 返回值作为下一轮的值进行比较
按照这个思路往下看，base case 也可以明确了。当没有东西可以比的时候，也就是参数值为 ''null'' 时，就是我们的递归最终开始返回的时候。联系到之前，我们讨论过缩减规模的方向是从链表的尾部开始，因此有两个状态需要讨论：
* 当参数值为 ''null''，也就是当前比较位置已经越过链表最后一位时，此时没有办法比较，直接返回 ''null''
* 此时位置位于链表最后一位的栈接收到了 ''null''，但 ''null'' 依然没法与当前元素比较，因此只能返回当前元素 ''curr''
当这一层返回本层对象时，由于下一层的栈中已经有其对应对象在等待了，因此可以进行正常的比较了。因此，我们的比较逻辑可以确认为：
* 如果参数对象的值为 ''null''，则返回 ''null''
* 如果函数返回值为 ''null''，则返回当前对象
* 否则，则判断当层栈中对象与返回的对象是否相等。如果相等，继续返回函数的返回值；否则则返回当层栈中的对象。
//**实现**：//\\ \\
* wrapper 函数：公共接口，封装使用。
public void removeDups() {
head = rRemove(head);
}
* 核心函数
private Node rRemove(Node curr) {
if(curr == null) {
return null;
}
else {
curr.next = rRemove(curr.next);
if(curr.next != null && curr.data.equals(curr.next.data)) {
return curr.next;
}
return curr;
}
}
以一个具体的链表 ''[233]'' 来进行栈跟踪：
\\ \\
{{ :cs:dsa:courses:gtx_1332x:i_lists:linked_list_rec.svg?600 |}}
- 首先通过 ''head = rRemove(head)'' 开始调用。此时的 ''curr'' 在 ''head'' 处，值是 ''2''
- 此时获取相邻的元素进行比较：''curr.next = rRemove(curr.next)''；由于 ''curr'' 不为 ''null''，因此会进行下一次的 ''rRemove'' 调用。
- 第二次调用，当前栈中的 ''curr'' ，也就是上一层的 ''curr.next''，为 ''3()''，依然不为 ''null''，因此继续展开
- 第三次调用，当前栈中的 ''curr'' 为 ''3'',依然不是 ''null''，因此展开
- 第四次调用，此时 ''curr'' 的值已经为 ''null'' （''3'' 已经是链表的最后一位）。至此整个递归调用拿到了第一个返回值，开始向下返回。
- 第二次返回，此时 ''curr'' 是之前的 ''3''(1st, 逆序）。因为 ''3(1st)'' 是链表最后一位，因此 ''curr.next == null''，因此返回值为本层的 ''curr''，也就是 ''3(1st)''。
- 第三次返回，此时 ''curr'' 是 ''3(2rd)''。将其与返回的 ''3(1st)'' 比较，相等，因此返回 ''3(2rd.)'' 的 ''curr.next''，也就是 ''3(1st)'' 。
- 第四次返回，此时 ''curr'' 是 ''2''。将其与返回的 ''3(1st)'' 比较，不等，因此返回 ''2''。至此栈清空，递归结束。
值得注意的是，在比较的过程中，我们通过 ''curr.next = return value'' 将符合条件的返回值串联起来的方式生成了结果链表。这种使用返回值生成结果链表的方法被称为 //Pointer reinforcement//。其主要的特点：
* 使用返回值构建结果链表
* 通过返回值来决定下一个节点的内容，实现了节点挑选逻辑和节点设定的分离
{{ :cs:dsa:courses:gtx_1332x:i_lists:recursivelinkedlist.java |Demo Code}}
===Doubly-Linked Lists (DLL)===
{{ :cs:dsa:courses:gtx_1332x:i_lists:doublylinkedlist.java |DoublyLinkedList Demo}}
//Doubly-Linked Lists//（双链表）在单链表的基础上添加了一个 ''previous'' 指针，用于指向之前的节点。双链表要求同时维护 ''head'' 与 ''tail''。
==AddingToFront(DLL)==
**//算法步骤：//**
- 创建新的节点
- 指向下个节点：将新节点的 ''next'' 指针指向 ''head''
- 指向上个节点：将 ''head'' 所在节点的 ''previous'' 指针指向新节点
- 重置 ''head''：将 ''head'' 指向新节点
**//边界条件：//**
* 起始为空链表时，''head'' 与 ''tail'' 都需要指向新创建的节点
{{ :cs:dsa:courses:gtx_1332x:i_lists:doubly_linked_list_add_front.svg?350 |}}
==AddingToBack(DLL)==
**//算法步骤：//**
- 创建新的节点
- 指向上个节点：将新节点的 ''previous'' 指针指向 ''tail'' 所在节点
- 指向下个节点：将 ''tail'' 所在节点的 ''next'' 指向新节点
- 重置 ''tail''：将 ''tail'' 指向新节点
**//边界条件：//**
* 起始为空链表时，''head'' 与 ''tail'' 都需要指向新创建的节点
{{ :cs:dsa:courses:gtx_1332x:i_lists:doubly_linked_list_add_to_back.svg?350 |}}
==RemoveFromFront(DLL)==
**//算法步骤：//**
- 重置 ''head''：将 ''head'' 指向 ''head.next'' 指向的节点（第二个节点）
- 将 ''head'' 的前置信息清空：将 ''head.prev'' 指向设置为 ''null''（第二个节点的 ''prev''）
**//边界条件：//**
* 双链表长度为 ''1'' 时，移除节点需要 ''head'' 与 ''tail'' 同时被设置为 ''null''
{{ :cs:dsa:courses:gtx_1332x:i_lists:doubly_linked_list_remove_from_front.svg?350 |}}
==RemoveFromBack(DLL)==
**//算法步骤：//**
- 重置 ''tail''：将 ''tail'' 指向 ''tail.previous'' 指向的节点（倒数第二个节点）
- 指向下个节点：将倒数第二个节点的 ''next'' 指向设置为 ''null''（也就是当前的 ''tail.next''）
**//边界条件：//**
* 双链表长度为 ''1'' 时，移除节点需要 ''head'' 与 ''tail'' 同时被设置为 ''null''
{{ :cs:dsa:courses:gtx_1332x:i_lists:doubly_linked_list_remove_from_back_.svg?350 |}}
==RemoveFromMiddle(DLL)==
该算法基于 index 移除内容。\\ \\
**//算法步骤：//**
- 判断删除节点的位置否位于首尾 (''0''，或者 ''size-1'')
- 如果是 ''0''，删除节点为首节点，调用 ''removeToFront''
- 如果是 ''size-1''，删除节点为尾节点，调用 ''removesToBack''
- 如果都不是，那么添加位置处于链表中部。此时需要遍历到被移除节点的前置节点。根据 index 的位置靠前还是靠后，有两种选择：
- 如果被移除节点位置靠前 (''index < size / 2'')，那么从链表前端，也就是 ''head'' 开始遍历。遍历结束的位置为被移除节点的前一个节点
- 否则，被移除节点位置靠后，那么从 ''tail'' 开始遍历，遍历结束的位置为被移除节点的后一个节点
- 遍历使用 ''index'' 作为循环条件：$[0, index)$ 和 $[size-1, index)$
- 缓存被移除的数据
- 更新链接。以被移除节点为中心：
- 其前节点的 ''next'' 指向其后节点
- 其后节点的 ''previous'' 指向其前节点
- 维护 ''size''，返回被移除的数据
===Circularly-Linked Lists (CLL)===
//Circularly-Linked Lists (CLL)// (环链表) 指尾部节点的 ''next'' 指向 ''head'' 的链表。
* 通常不包含 ''tail''
* 循环终止的条件是 ''curr.next.equals(head)''
==addToFront(O(n))==
**//算法步骤：//**
- 创建新节点
- 指向下个节点：将新节点的 ''next'' 指向 ''head'' 所在节点
- 重置 ''head''：将 ''head'' 指向新节点
- 重置指向 ''head'' 的尾节点：需要再进行一次遍历。更新尾部节点的 ''next''，使其指向更新后的 ''head''（$O(n)$）
==addToFront(O(1))==
**//算法步骤：//**
- 创建新节点：创建一个**空的**新节点
- 插入节点：将新节点插入到 ''head'' 之后（index 1）
- 将新节点的 ''next'' 指向原来的第二个节点
- 将 ''head'' 的 ''next'' 重定向到新节点
- 转移数据：将 ''head'' 内的内容拷贝到新节点中
- 添加数据：将新的数据写入到 ''head'' 对应的节点中
==addToBack==
**//算法步骤：//**
- 创建新节点：创建一个**空的**新节点
- 插入节点：将新节点插入到 ''head'' 之后（index 1）
- 转移数据：将 ''head'' 内的内容拷贝到新节点中
- 添加数据：将新的数据写入到 ''head'' 对应的节点中
- 重置 ''head''：将新节点作为新的 ''head''，这样一来原有的 ''head'' 就成为了尾部节点。
==RemovingFromFront==
与单链表不同，环链表中的移除的主要思路是从**内容**上替代节点。整体的逻辑可以描述为：
* 使用第二个节点代替头节点被移除
* 使用头节点模拟第二个节点
* 改变头节点的指向到第三个节点
**//算法步骤：//**
- 转移数据：将第二个节点的内容拷贝到 ''head'' 节点中。此处不需要考虑数据覆盖的问题，因为 ''head'' 节点需要被移除。
- 指向下个节点：将 ''head'' 的 ''next'' 指向从第二个节点改变为第三个节点。
**//边界条件：//**
* 当链表的长度为 1 时：
* ''head'' 需要设置为 ''null''
* ''head.next'' 需要指向其自身
==RemovingFromBack==
**//算法步骤：//**
- 定位新的尾部节点：遍历到倒数第二个节点
- 更新链接：将倒数第二个节点的 ''next'' 指向 ''head''
==RemovingFromMiddle==
**//算法步骤：//**
- 遍历到需要被移除节点的前一个节点
- 将该节点的 ''next'' 指向被移除节点的 ''next''
====Stacks and Queues====
==Linear Abstract Data Type==
* Linear：
* 有限
* 每个对象只有一个前置对象
* 每个对象只有一个后置对象
* ADT：
* 包含了有限数量的数据结构
* 被存储的对象之间存在联系
* 运算（行为）定义了 ADT
===Stacks 的原理===
//Stack//（栈） 是 ADT 一种，通常使用 Array 或者 SLL 实现。名如其意， //Stack// 就是一种看上去是堆起来的数据结构（比如薯片筒就是一种 stack）。因此，//Stack// 通常都包含了两种基本操作：
* **Push**：将对象**添加**到 //Stack// 中的操作（把薯片放进桶里）
* **Pop**：将对象从 //Stack// 中移除的操作（把薯片拿出来）
值得注意的是，根据 //Stack// 的概念，无论是添加还是移除，我们处理的对象都只能是**栈顶的对象**（最上面的薯片），这导致了一下的几个事实：
* //Stack// 是一个 //LIFO// （Last In First Out ，**后进先出**的数据结构）（最先放进去的薯片肯定在最底下）
* //Stack// 中不存在 random access & remove。唯一能够操作的就是栈顶的，最后 push 进去的对象。（只能拿到最上面的薯片）
* //Stack// 无法支持搜索
==Stack 的几个基础方法==
* ''void push(x)''：添加对象
* ''T pop()''：移除栈顶元素并返回
* ''T peek'' or ''T top''：返回栈顶元素（只读）
* ''boolean isEmpty()''：通过 size，或是 ''top'' 是否为 ''null'' 来判断栈是否为空。
* ''clear()''：设置 ''top'' 为 ''null'' 并清空栈。
==Stack 的一些应用==
* undo 功能
* 手机 app 的多开
===Stack 的实现（链表）===
链表是实现 //Stack// 最高效的手段，所有的操作复杂度都是 $O(1)$。一些实现细节：
* 链表的 ''head'' 用于模拟 //Stack// 的 ''top''
* 空栈的情况下，''head'' 为 ''null''
* 不需要 ''tail''
==Push==
使用链表实现时，''head'' 总是代表 top。因此每 push 一个对象，''head'' 指向的节点就会更新到最新推送的对象。
**//算法步骤：//**
- 建立新（对象）节点
- 将新节点的 ''next'' 指向原来的 ''head'' 所代表的节点
- 更新 ''head'' ，将其指向新的节点
{{ :cs:dsa:courses:gtx_1332x:i_lists:stack_push.svg?350 |}}
==Pop==
**//算法步骤：//**
- 将 ''head'' 指向下一个节点即可。
**//边界条件：//**
* 当 //Stack// 大小为 1 时，移除元素需要将 ''head'' 设置为 ''null''
===Stack 的实现（数组）===
实现细节：
* 是否为空通过检查 ''size'' 是否为 ''0'' 来确认。
* 从效率的角度出发，不实现物理上的栈顶：
* 将最右边的元素视作栈顶（''size - 1''），避免了每次 push / pop 都要做 $o(n)$ 的移动操作
* ''clear'' 的方式：
* （不推荐）将 ''size'' 归零
* （不推荐）手动将所有数组元素以新数据覆盖（比如 ''0''）, $O(n)$ 复杂度
* 使用该数组名指向新的数组，利用 java 的GC 功能清除数据 ,$O(1)$ 复杂度
===Queues 的原理===
//Queues//（**队列**） 的结构类似于一个两边都开口的薯片桶；一边是入口，另一边是出口。//Queues// 遵循 //FIFO// (First in First Out 先进先出) 原则。与 //Stack// 类似，//Queues// 不支持任何的**随机访问**和操作。
==Queues 的基础方法==
* ''void enqueue(x)''：添加 ''x'' 到队列的最后
* ''x dequeue()''：从队列中移除最先进入的元素
* ''x peak() & x top()''：返回队列的最新 dequeue 的元素
* ''boolean isEmpty()''：检查 size 是否为 0 或者 front 是否为 Null
* ''void clear()''：将 front 设置为 null
===Queues 的实现（链表）===
* 由于 Queues 出入口不同，因此需要同时维护 ''head'' 和 ''tail'' 两个指针
* 鉴于链表在尾部的 remove 操作总是 $O(n)$ 复杂度，处于效率考虑，Queues 的**添加入口在尾部，而删除出口在头部**（addToBack & removeFromFront）。这样能保证添加删除的操作的复杂度都是 $O(1)$
==enqueue(SLL)==
**//算法步骤：//**
- 同链表的 //addToBack()//
==dequeue(SLL)==
**//算法步骤：//**
- 同链表的 //removeFromFront()//
===Queues 的实现（数组）===
与链表数列相似，//Queue// 的数组实现主要依靠的是一前以后的两个指针 ''front'' & ''back'' 来体现出“队列”的概念。//Queue// 可以被视作存储于数组中的，以 //Back// 开头，以 //Front// 结尾的队列。需要注意的是，对效率的考虑给数组数列的组成方式带来了很大的影响：
==Front & Back==
由于 Array 的 AddToFront() 操作必须要求 Shifting 移位，因此数组队列的 enqueue 是在数组中对象序列的**后方**，而 dequeue 是在对象序列的**前方**。那么通常 ''back'' 会被视作是队列的入口，而 ''front'' 会被视作是队列的出口。
==数组与循环机制==
我们之前的设想是将队列视作存储在数组中的，有头有尾的一个对象序列。这意味着其占用数组的位置只与数组的 capcity 有关系，而与数组的 Index 没有关系。因此，我们很可能会遭遇如下的存储分布：
\\ \\
{{ :cs:dsa:courses:gtx_1332x:i_lists:deque_cases.svg?300 |}}
\\ \\
无论是哪种，我们都没有办法用 //ArrayList// 来实现。因为 //ArrayList// 要求首元素不能为空，且必须连续存储。因此，数组队列只能使用 //Array// 来实现。
\\ \\
再观察一下第二种情况。以图为例，这种例子出现的情况是：数列 ''[6,3,11]'' 存储在数组的最后三位。假设我们此时希望对该数列进行 enqueue 的操作；此时 capcity 为 7，数列长度为 3，即便添加一个元素也没有超过数组的容量。但由于存储的位置处于数组的末端，我们没有办法再往里插入新的元素了。\\ \\
为了解决这个问题，数组数列的实现引入了循环（//WrapAround//）的机制。如果 enqueue 的位置超出了数组的上限，但数组本身还有空可以做 enqueue 的话，我们就将 enqueue 的位置（back 的位置）往数组前方的空闲位置插入。具体的计算方式为：
\\
$$
\texttt{back = Index mod Capacity}
$$
以上图为例，我们原来希望插入的位置是 index = 7（当然没有 7），通过上述转换之后就是在 index = 0 处 enqueue 了。
''back''（起点） 并不是必须的。知道 ''front''（终点）和 ''size'' 长度，就可以计算出起点。
==enqueue==
===Priority queues===
//Priority queues// 是另外一种线性的 ADT。其特点是，当前移除的对象是**优先级最高的对象** 。这种 ADT 通常用于搜寻最大最小值。 由于有大小的存在，Priority queues 中的对象必须是 Comparable 的。
==功能与效率性==
Priority queues 会分为两个区：一个 Priority 区和一个备选区。Priority 区中存放优先级最高的数据用于操作。当 Priority 区中的数据移除后，备选区需要通过另一轮筛选选出下一个优先级最高的数据推送到 Priority 区中，以便接下来的操作。
\\ \\
可以注意到，每处理一轮 Priority 区中的数据，备选区中的数据就需要排序一次，为了更好的效率，具体实现是基于 heap 的。
Priority queues 是线性类型的 ADT，但使用线性数据结构实现确十分低效。不论使用数组还是链表，我们都需要Priority queue 是一个有序数列。这意味着，每次 enqueue 需要进行一次排序（链表需要遍历到插入新元素的位置），也就是每次 enqueue 的复杂度都在 $O(n)$。这样是非常不效率的。
===Deques===
//Deques//，指 //Double-ended queue//。//Deque// 允许在队列的两端添加和删除元素。//Deque// 不支持随机访问（添加删除）以及搜寻操作。
==Deque 的方法==
* ''void addFirst(x)''：在 Deque 队首添加元素
* ''void addLast(x)''：在 Deque 队尾添加元素
* ''x removeFirst()''：在 Deque 队首删除元素
* ''x removeLast()''：在 Deque 队尾删除元素
* ''boolean isEmpty()''
* ''int size()''
===Deque 的实现（数组）===
//Deque// 的数组实现同样需要使用到循环的方式。
==addLast() & removeFirst()==
* addLast() 通过 ''back % capacity'' 维护插入位置
* removeFirst() 通过 ''front % capacity'' 维护删除位置
==addFirst() & removeLast()==
这两个方法也需要通过循环的方式进行位置的维护。但由于其进出方向与之前的两个方法完全相反，如果使用同样的 ''back'' & ''front'' 指针，那么指针移动的操作是减而不是加。这意味着指针指向的 Index 很可能会变为负数，也就是会出现向前循环的情况。这种情况下，我们需要进行手动判断并做出以下处理：
//this applied to back as well
if (front < 0) {
front = capacity - front;
}
所有的操作（除开 resize）都是 $O(1)$，总的说来是 $O(1)^*$
==Java 的 modulo 操作==
通常情况下，末除是一个分类的过程。所有余数相同的数字都会被放入到一个类中。在这个类中，**最小的**，**非负的成员**会成为余数。这导致了负数做末除时存在着不同。比如 $9 % 5 = 4$；但进行 $-9 % 5$ 时，因为要保证余数非负，取余的方向实际上需要更往负数方向上进行。比如这里，如果之间按正数的取余方式 $-9$ 去除 $(-1)\times5$ 还有 $-4$，但由于需要余数为正，因此需要再去除一个 $(-1)\times5$。因此余数是 $1$。\\ \\
但在 Java 中，余数的结果并不要求为正，而是**最接近 0 的数**。这种情况是我们之前讨论的第一种情况：''9 % -5 = -4''。
===Deque 的实现（链表）===
//Deque// 的实现需要使用**双链表**（DLL）：
* //add first// & //remove first// 均在 head 处操作
* //add fisrt// & //remove last// 均在 tail 处操作
由于使用双链表，所有的操作都是 ($O(1)$)