线性表（ Java 版 ）

带着问题思考

• 线性表是什么 ?
• 哪些应用场景（案例） ?
• 使用注意事项有哪些 ？

线性表是什么？

我们来看一张图片

从图中可以看出 :

1. A1 是 A2 的前驱
2. A2 是 A1 的后继

规律

1. Ai + 1 是 Ai 的后继
2. A1 没有前驱 An 没有后继

理解：

一组数据，一对一，直到 An 就结束了 A1没有前驱 An 没有后继

存储方式

线性表是什么我们有了一个了解，现在要说说它的存储方式

• 顺序存储(生活例子排队)
• 链式存储(生活例子特工潜伏)

顺序存储

存储位置连续，可以很方便的计算各个元素的地址如每个元素占 C 个存储单元那么
Loc(An) = Loc(An - 1) + C
Loc(An) = Loc(A1) + (i-1)*C
例如 Loc(A2) = Loc(A1) + A1的存储单元

链式存储

一组数据存储 可以是连续的也可以是不连续的，他们之间通过指针确定位置与关系，
在初始化的时候默认添加一个的头指针

1. 单项链表 理解: 字面意思( B 的后继指向 C 的前驱)

2. 双向链表 理解: 字面意思( B 的后继指向 C 的前驱，同时 C 的前驱指向 B 的后继)
   2.1 双向循环链表： 理解：尾指针(最后一个元素所属指针)的后继指向头指针的前驱，头指针的前驱指向尾指针的后继
   3.2 空双向循环链表：理解：头指针的前驱指向自己的后继，头指针的后继指向自己前驱

   
   单项链表
   循环双向链表
   空双向循环链表

---

哪些应用场景（案例） ?

顺序存储

1. ArrayList()
   总结 优势 查询 ，弱势 插入，删除

链式存储

2. LinkedList()
   总结 优势 插入，删除，弱势 查询

---

使用注意事项有哪些 ？

顺序存储：优势 查询 ，弱势 插入，删除
链式存储：优势 插入，删除，弱势 查询
根据需求，选择合适的存储结构的线性表