## 链表
链表是一种**链式存储**的线性表, 所有元素的内存地址不一定是连续的
## 实现 LinkedList
底层的 Node 有数据域和指针域，分别用于存储数据元素和下一节点的引用
### 1. 属性
私有内部类 Node 用于存储数据，size 记录当前已经存入的元素个数，first 指向第一个 Node
```java
public class LinkedList {
// 当前存储的数据的长度（元素个数）
private int size;
// 头结点
private Node first;
// 未查询到返回值
private static final int MINUS_ONE = -1;
// 私有内部类，存储数据的链表节点
private static class Node {
// 存储的元素
E element;
// 指向下一个节点
Node next;
// Node 的构造器
Node(E element,Node next) {
this.element = element;
this.next = next;
}
}
}
```
### 2. 构造器
创建链表时不用指定容量，链表元素在内存中并不是连续存储的
```java
// LinkedList 的构造器
public LinkedList() {
size = 0;
first = null;
}
```
### 3. 获取节点
私有方法，获取指定位置的节点，方便其他方法调用，同时进行了索引越界检查
```java
private Node getNode(int index) {
checkRange(index);
Node node = first;
// 指针向后移动 index 次
for(int i=0;i(ele,first);
}else {
// 获取要插入位置前一个 Node
Node prev = getNode(index-1);
// 创建新的Node，其next 指向之前的 prev.next，然后引用赋给 prev.next
prev.next = new Node<>(ele,prev.next);
}
size++;
}
```
### 5. 删除元素
同样分为删除第一个元素和删除其他元素，将要删除的 node 的前驱节点的 next 修改为 node 的后继
```java
public E remove(int index) {
checkRange(index);
Node node = first;
if(index==0) {
first = first.next;
}else {
Node prev = getNode(index-1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}
```
### 6. 清空元素
只要置空 first，其他节点都会被释放
```java
// 清空元素
public void clear() {
first = null;
size = 0;
}
```
### 7. 修改元素
```java
// 修改指定索引位置上的元素，并返回旧的元素
public E set(int index,E ele) {
Node node = getNode(index);
E old = node.element;
node.element = ele;
return old;
}
```
### 8. 查找元素
```java
// 返回指定索引位置上的元素
public E get(int index) {
return getNode(index).element;
}
```
### 9. 返回指定元素的索引
遍历链表，LinkedList 允许存储 null 值，所以要特殊处理
```java
// 返回 target 元素的第一次出现的索引，如果不存在，返回-1
public int indexOf(E target) {
Node node = first;
// 看一下 target 是不是 null
if(target==null) {
// 注意循环中不能使用查找元素的方法get(index)，否则复杂度急剧上升
for(int i=0;i node = first;
for(int i=0;i=size) {
indexOutOfBounds();
}
}
private void checkRangeForAdd(int index) {
if(index<0 || index>size) {
indexOutOfBounds();
}
}
```
## 复杂度
对于 add 和 remove 操作，复杂度来自遍历查找目标 index 的操作，并没有移动数据元素，这是和动态数组不同的地方
|操作|最好|最坏|平均|
|:---:|:---:|:---:|:---:|
|add(int index,E ele)|$O(1)$|$O(N)$|$O(N)$|
|remove(int index)|$O(1)$|$O(N)$|$O(N)$|
|set(int index,E ele)|$O(1)$|$O(N)$|$O(N)$|
|get(int index)|$O(1)$|$O(N)$|$O(N)$|
## 参考
* [恋上数据结构与算法（第一季）](https://ke.qq.com/course/385223)
* [小码哥《恋上数据结构与算法》笔记（二）：链表](https://juejin.im/post/5df98c92e51d455836159eef)
数据结构 | 单链表 SingleLinkedList
