# LinkedList

线性表的顺序存储结构，是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，但是它的缺点就是删除、插入时，需要移动大量元素。

线性表的链式存储结构，由于它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但也失去了顺序存储可随机存取的优点。

链表分为单链表、双链表、循环链表、静态链表。

链表是通过一组任意的存储单元来存储线性表中的数据元素，并且还存放一个指向其后继结点的指针，双链表还会存放指向前驱结点的指针。

## 单链表

单链表中结点类型的描述如下：

```javascript
class LNode {
  data: any;    //数据域
  next: LNode;  //指针域
}
```

单链表的元素是离散地分布在存储空间中的，所以单链表是非随机存取的存储结构，既不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历依次查找。

通常，我们会加多一个 **头结点** 来标识一个链表。头结点的数据域可以不存储任何信息，也可以记录表长等信息。头结点的指针指向线性表的第一个结点，但头指针的指针域为 NULL 时，表示次单链表是空的。

引入头结点后，可以带来两个优点：

1. 由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
2. 无论链表是否为空，空表中头结点的指针域为空，因此空表和非空表的处理就统一了。

单链表的建立可以采用 **头插法** 或 **尾插法**，其插入的时间复杂度是 O(1)。

查找结点操作的时间复杂度是 O(n)。

插入结点操作的时间复杂度是 O(1），如果是在某个结点前插入一个新结点，可以转换成在某结点后插入，再交换两个元素。

删除结点操作的时间复杂度是 O(n)，因为找到其前驱结点需要 O(n) 的时间。

## 双链表

单链表结点中只有一个指向其后继的指针，这使得单链表只能从头结点依次顺序地向后遍历。
若要访问某个结点的前驱结点（插入、删除操作时），只能从头开始遍历，访问后继结点的时间复杂度是 O(1)，访问前驱结点的时间复杂度是 O(n)。

在双链表中，拥有两个指针域 **prior** 和 **next**，分别指向其前驱结点和后继结点。

```javascript
class DNode{
  data: any;    //数据域
  prior: DNode; //前驱结点域
  next: DNode;  //后继结点域
}
```

## 循环链表

### 循环单链表

循环单链表与单链表的区别在于，表中最后一个结点的指针不是 NULL，而应该指向头结点，从而整个链形成一个环。

在循环单链表中没有指针域为 NULL 的结点，因此**循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。**

循环单链表设置 **尾指针** 会更加高效，因若设置的是头指针，那么对表尾进行操作需要 O(n) 的时间复杂度。而如果设置的是尾指针 `r`，则 `r->next` 即为头指针了，对表头与表尾的操作都可以在 O(1) 的时间内完成。

### 循环双链表

在循环双链表中，头结点的 prior 指针指向表尾结点，表尾结点的 next 指针指向头结点。

**循环双链表判断是否为空表时，判断头结点的 prior 和 next 指针域是否指向当前头结点。**

## 静态链表

静态链表是借助数组来描述线性表的链式存储结构，结点有数据域 data 和 指针域 next。这里的指针是结点的相对地址（数组下标），又称为游标。

静态链表是需要预先分配一块连续的内存空间的。在静态链表中可以以 `next = -1` 作为其结束的标识。

静态链表的插入、删除操作与动态链表相同，只需要修改指针，而不需要移动元素。

```javascript
static MAX_SIZE = 100;
class StaticLinkList {
  data: any;
  next: number;
}
```

C语言定义：

```c
#define MaxSize 50  //静态链表的最大长度
typedef struct {    //静态链表结构类型的定义
  ElemType data;    //存储数据元素
  int next;         //下一个元素的数组下标
} SLinkList[MaxSize];
```