一·：线性表

1.线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。
•前驱元素： 
        若A元素在B元素的前面，则称A为B的前驱元素。
•后继元素： 
        若B元素在A元素的后面，则称B为A的后继元素。

2.线性表的特征：①. 第一个数据元素没有前驱，这个数据元素被称为头结点； 
②. 最后一个数据元素没有后继，这个数据元素被称为尾结点； 
③. 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。 

3.分类：线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表。

4.线性表的存储结构：①顺序存储：逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现.借助于语言的数组来实现。②链式存储：不要求逻辑上相邻的结点物理上也相邻，结点间的逻辑关系是由附加的指针字段表示的，在java中使用“对象引用”来实现指针。

二：顺序表

以顺序存储结构进行存储的线性表称为顺序表。顺序表存储结构采用顺序存储方式，逻辑上相邻的元素物理存储位置也相邻，元素存储都是连续的。由这种结构特点可知，顺序表可以随机访问快速定位某个元素，查找效率高，但删除和插入元素时，需要移动大量元素，效率低。

在顺序表中·，元素插入操作为将指定位置后的所有元素向后移动一位，然后插入元素。元素删除为将指定位置后的所有元素向前移动一位。

顺序表的时间复杂度：由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，尤其是元素越多，这个问题越明显。虽然顺序表的查询很快，时间复杂度为O(1)但是增删的效率是比较低的因为每次增删操作都伴随着大量的数据元素移动。

三：链表

1.链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。

2.链表的分类：①单向链表：a)在单向链表中，每个节点包含一个数据域和一个指向下一个节点的引用（指针）。这是最简单的链表形式，只能从头节点遍历到尾节点。b)优点：实现简单；节省空间（每个节点只需要一个额外的指针）。c)缺点：不能反向遍历；插入和删除操作需要找到前驱节点。

②双向链表：a)双向链表中的每个节点除了包含指向下一个节点的引用外，还有一个指向前一个节
点的引用。b)优点：可以从两个方向遍历链表；插入和删除操作更加方便。c)缺点：每个节点需要两个额外的指针，因此比单向链表占用更多空间。

③循环链表：a)循环链表可以是单向的也可以是双向的，其特点是最后一个节点的“下一个”指针
不是指向null，而是回指到链表的第一个节点，形成一个闭环。b)优点：便于实现循环遍历；没有明确的尾节点，处理起来更方便。c)缺点：如果不小心处理，可能会陷入无限循环。

LinkListResult类中的head属性代表指向链表第一个节点的指针。LinkListResult类的构造函数设置头结点为空结点,并初始化链表长度为0。

四：链表VS顺序表

①相比较顺序表，链表插入和删除的时间复杂度虽然一样，但仍然有很大的优势，因为链表的物理地址是不连续的，它不需要预先指定存储空间大小，或者在存储过程中涉及到扩容等操作，同时它并没有涉及的元素的交换。
②相比较顺序表，链表的查询操作性能会比较低。因此，如果我们的程序中查询操作比较多，建议使用顺序表，增删操作比较多，建议使用链表。

五：java中LinkedList

1.在Java中，LinkedList是一个基于链表的数据结构，它实现了List接口并且提供了对元素的快速插入和删除操作。
2.与ArrayList相比，LinkedList在元素的添加和移除上表现得更高效，因为它不需要在数组中移动元素来保持连续性。然而，访问元素时不如ArrayLi快，因为它是通过遍历链表来查找元素的位置。

六：练习题

假设你正在开发一个简单的学生管理系统，使用顺序表(SequenceList)来存储学生姓名。请完成以下任务：

1、创建一个可以存储字符串的顺序表和链表，初始容量为10

2、添加以下学生姓名到顺序表中：“张三”, “李四”, “王五”，“赵六”。

3、在“李四”后面插入“李四”（注意：需要先找到“李四”的位置）

4、删除“李四”并从顺序表中移除

5、查找“李四”在顺序表中的位置（索引）

6、打印最终顺序表中的所有学生姓名

7、清空顺序表并验证它确实为空

顺序表：

链表：