1. 定义

线性表( list )：由零个或多个数据元素组成的有限序列。全名线性存储结构。
线性表结构存储的数据往往是可以依次排列的，就像小朋友手拉手，每位学生的前面和后面都仅有一个小朋友和他拉手，具备这种“一对一”关系的数据就可以使用线性表来存储。例如：存储类似 { 1，4，6，8，9，11 } 这样的数据时，各元素依此排列，每个元素的前面和后边有且仅有一个元素与之相邻（除首元素和尾元素），即可以使用线性表来进行存储。
将具有“一对一”关系的数据 “线性”地存储在物理空间中，这种存储结构就称为线性存储结构（简称线性表）。

注意：线性表存储的数据，要求数据类型必须一致

2. 存储结构

线性表存储数据可分为以下2种：

  1. 顺序存储结构：将数据依此存储在连续的整块物理空间种，这种存储结构称为顺序存储结构（简称顺序表）。
  2. 链式存储结构：将数据分散的存储在物理空间中，通过特定的方式来保存着它们之间的前后逻辑关系，这样的存储结构称为链式存储结构（简称链表）。

3. 前驱和后继

数据结构中，一组数据中的每个个体被称为“数据元素”（简称“元素”）。例如下图中，元素1234都是这组数据种的一个元素
image.png
在对于这种具有“一对一”逻辑关系的数据，在描述前后两个元素的关系的时候，用到了下面的术语：

  • 某一个元素的左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素都统称为“前驱元素”。
  • 某一个元素的右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素都统称为“后继元素”。

4. 抽象数据类型定义

  1. ADT 线性表（List）
  2. Data（数据类型）
  3.     线性表的数据对象集合为{a1,a2,...,an}，每个元素的类型均为DataType。
  4.     其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素， 
  5.     除了最后一个元素an外，每一个元素有且只有一个直接后继元素。
  6.     数据元素之间的关系是一对一的关系。
  7. Operation（操作）
  8.     InitList（*L）：初始化操作，建立一个空的线性表L。
  9.     ListEmpty（L）：判断线性表是否为空表
  10.                     若线性表为空，返回true，否则返回false。
  11.     ClearList（*L）：将线性表清空。
  12.     GetElem（L,i，*e）：将线性表L中的第i个位置元素值返回给e。
  13.     LocateElem（L，e）：在线性表L中查找与给定值e相等的元素，
  14.                         如果查找成功，返回该元素在表中序号表示成功；
  15.                         否则，返回0表示失败。
  16.     ListInsert（*L，i，e）：在线性表L中第i个位置插入新元素e。
  17.     ListDelete（*L，i，*e）：删除线性表L中第i个位置元素，并用e返回其值。
  18.     ListLength（L）：返回线性表L的元素个数。
  19. endADT

线性表关键点：
1.像排队一样，具有线一样的性质，是一个序列，元素之间有先来后到的顺序。
2.若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其它元素都有且仅有一个前驱和后继。
3.是有限的。