# 线性表 Linear List

1. [线性表的存储结构](#线性表的存储结构)\
   1.1 [顺序存储](#顺序存储)\
   1.2 [链式存储](#链式存储)

**线性表**：零个或多个数据元素的有限序列

**抽象的数据结构**

```
定义
    线性表
数据
    线性表的数据对象集合为{a1, a2, ..., an}，每个数据元素类型均为DataType
    其中，除第一个元素a1外，每个元素都有且只有一个直接前驱元素
    除最后一个元素an外，每个元素都有且只有一个直接后驱元素
    数据元素之间的关系是一对一的关系
操作
    初始化
    增，删，改，除
    空判断
    获取元素
    清空元素
```

## 线性表的存储结构

* 顺序存储
* 链式存储

## 顺序存储

1. 线性表顺序存储的三个基本属性

* 存储空间的起始位置
* 线性表的最大存储容量
* 线性表的当前长度

2. 顺序存储的优点及缺点

* 优点：
  * 不需要为表示表中元素之间的逻辑关系而增加额外的存储空间
  * 可以快速存取表中的任意一个位置的元素
* 缺点：
  * 插入和删除操作，需要移动大量的元素
  * 当线性表长度变化较大时，难以确定存储空间的容量
  * 造成存储空间的“碎片化”

数组就是最常见的顺序存储的线性表。

## 链式存储

1. 线性表链式存储的属性

* 头指针，头节点
* 指针域，数据域

头指针与头节点的区别：

* 头指针
  * 头指针是指向链表第一个节点的指针，若链表有头节点，则是指向头节点的指针
  * 头指针具有标识作用，常用于标识链表的名字
  * 无论链表是否为空，头指针都不为空。**头指针是链表的必要元素**。
* 头节点
  * 头节点是为了操作的统一和方便设计的，放在第一个元素的节点之前，其数据一般无意义（可以存放链表的长度信息）。
  * 头节点不是链表的必要元素。

2. 链式存储的优点和缺点

* 优点：
  * 采用链式存储单元存放线性表数据元素
  * 不需要预先分配固定大小的存储空间
* 缺点：
  * 查找时间复杂度O(n)
  * 找到元素后，插入和删除操作的时间复杂度为O(1)

链式存储的线性表根据指针域的不同，可分为单向链表，循环链表和双向链表等。

## 单向链表

单向链表中每个节点有两个域，一个数据域和一个指针域。数据域用于表示单链表中的数据，指针域用于指向当前节点后驱节点的指针，简称为单链表。

## 循环链表

将单链表中的最后一个节点的指针指向该单链表的头节点，使得整个链表形成一个环。这种首尾相连的单链表称为单循环链表，简称循环链表。

## 双向链表

若在单链表中增加一个指向当前节点前驱节点的指针域，则构成双向链表。双向链表中包含三个域，一个数据域和两个指针域（一个指向后驱节点，一个指向前驱节点）。