线性表是具有相同数据类型的 n（n ≥ 0）个数据元素的有限序列。其中 n 为表长，当 n = 0 时，该线性表是一个空表。若用 L 命名线性表，则其一般表示为： L = ( a 1 , a 2 , . . . , a i , a i + 1 , . . . , a n ) L=(a_1,a_2,...,a_i,a_{i+1},...,a_n) L=(a1,a2,...,ai,ai+1,...,an) 其中，a1 是唯一的 “第一个” 数据元素，又称为表头元素；an 是唯一的 “最后一个” 数据元素，又称为表尾元素。除了第一个元素外，每个元素有且仅有一个直接前驱。除了最后一个元素外，每个元素有且仅有一个直接后继。这就是线性表的逻辑特性。
线性表的特点：
表中元素的个数有限；表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后顺序；表中元素都是数据元素，每一个元素都是单个元素；表中元素的数据类型都相同。这意味着每一个元素占有相同的存储空间；表中元素具有抽象性。即仅讨论元素间的逻辑关系，不考虑元素究竟表示什么内容。注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念。
线性表的基本操作如下：
InitList(&L)：初始化表。构造一个空的线性表；Length(L)：求表长；LocateElem(L,e)：按值查找操作；GetElem(L,i)：按位查找操作；ListInsert(&L,i,e)：插入操作；ListDelete(&L,i,&e)：删除操作；PrintList(L)：输出操作；Empty(L)：判空操作；DestoryList(&L)：销毁操作。注意：
基本操作的实现取决于哪一种存储结构，存储结构不同，算法的实现也不相同；“&” 表示 C/C++ 中的引用。如果传入的变量是指针型的变量，且在函数体内要对传入的指针进行改变，则将要用到指针变量引用型；线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理上也相邻。
假设线性表 L 存储的起始位置为 LOC(A)，sizeof(ElemType) 是每个数据元素所占用的存储空间的大小，则表 L 所对应的顺序存储如图：
假设线性表的元素类型是 ElemType，线性表的顺序存储类型描述为：
#define Maxsize 50 //定义线性表的最大长度 typedef struct{ ElemType data[Maxsize]; //顺序表的元素 int length; //顺序表的当前长度 }SqList; //顺序表的类型定义一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将产生溢出。
而动态分配时，存储空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，可以另外开辟一个更大的存储空间，用以替换原来的存储空间，从而达到扩充存储空间的目的，而不需要一次性划分所有需要的空间给线性表。
#define InitSize 50 //表长度的初始定义 typedef struct{ ElemType *data; //指示动态分配数组的指针 int MaxSize,length; //数组的最大容量和当前个数 }SeqList; //动态分配书序顺序表的类型定义 C 语言初始动态分配语句为：
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);C++ 语言初始动态分配语句为：
L.data = new ElemType[InitSize];注意：动态分配并不是链式存储，同样还是属于顺序存储结构，其物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。
顺序表的最主要特点是随机访问，即通过首地址和元素序号可以在 O(1) 的时间内找到指定的元素。
由于顺序表的插入、删除操作需要移动大量的元素，影响了运行效率，由此引入了线性表的链式存储。链式存储线性表时，不需要使用地址连续的存储单元，即它不要求逻辑上相邻的两个元素在物理上也相邻，它通过 “链” 建立起数据元素之间的逻辑关系，因此，对线性表的插入、删除不需要移动元素，而只需要修改指针。
线性表的链式存储又称为单链表，它是指通过一组任意的存储单元来存储线性表的数据元素。为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息之外，还需要存放一个指向其后继的指针。单链表结点结构如图：
其中，data 为数据域，存放数据元素；next 为指针域，存放其后继结点的地址。
单链表中结点类型的描述如下：
typedef struct LNode{ //定义单链表结点类型 ElemType data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList;利用单链表可以解决顺序表需要大量的连续存储空间的缺点，但是单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素是离散地分布在存储空间中的，所以单链表是非随机存储的存储结构。即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。
通常用一个 “头指针” 来标识一个单链表，如单链表 L，头指针为 “NULL” 时则表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等相关信息。头结点的指针域指向线性表的第一个元素结点，如图：
头结点和头指针的区别：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息。
引入头结点后，可以带来两个优点：
由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理；无论链表是否为空，其头结点是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的操作也就一致了。该方法从一个空表开始，生成一个新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后，如图：
算法实现如下：
LinkList CreateList1(LinkList &L){ LNode *s;int x; L = (LinkList)malloc(sizeof(LNode)); //创建头结点 L-next = NULL; //初始为空链表 scanf("%d",&x); //输入结点的值 while(x!=9999){ //输入 9999 表示结束 s = (LNode*)malloc(sizeof(LNode)); //创建新结点 s->data = x; s->next = L->next; //最重要的两步 L->next = s; //将新结点插入表中，L 为头指针 scanf("%d",&x); }//while 结束 return L; }采用头插法建立单链表，读入数据的顺序与生成的链表中元素的顺序是相反的。
为了保证生成的单链表中的数据元素的顺序和读入的顺序一致，采用尾插法建立单链表，这时需要增加一个尾指针，如图：
尾插法建立单链表算法如下：
LinkList CreateList1(LinkList &L){ int x; //设元素类型为整型 L = (LinkList)malloc(sizeof(LNode)); //创建头结点 LNode *s,*r = L; //r 为尾指针 scanf("%d",&x); //输入结点的值 while(x!=9999){ s = (LNode*)malloc(sizeof(LNode)); //创建新结点 s->data = x; r->next = s; r = s; //r 指向新的表尾结点 scanf("%d",&x); } r->next = NULL; //尾结点置空 return L; }先检查插入结点位置的合法性，然后再找到插入位置的前驱结点，即 i-1 个结点，再在其后插入结点。
算法如下：
p = GetElem(L,i-1); //第 1 步,找到插入位置的前驱结点 s->next = p->next; //下图的操作 1 p->next = s; //下图的操作 2仍然需要知道要删除结点的前驱结点。
算法：
p = GetElem(L,i-1); //查找删除位置的前驱结点 q = p->next; //令 q 指向被删除的结点 p->next = q->next; //将 *q 结点从链表中 “断开” free(q); //释放结点的存储空间为了克服单链表中为了访问某个结点只能从头结点开始依次顺序地向后遍历的问题，引入了双链表，双链表结点中有两个指针 prior 和 next，分别指向其前驱结点和后继结点，如图：
双链表的结点类型描述如下：
typedef struct DNode{ //定义双链表结点类型 ElemType data; //数据域 struct DNode *prior,*next; //前驱和后继指针 }DNode,*DLinkList;在双链表中 p 所指向的结点之后插入结点 *s，指针变化如图：
s->next = p->next; //将结点 *s 插入到结点 *p 之后 p->next->prior = s; s->prior = p; p->next = s;删除双链表结点 *p 的后继结点 *q，其指针的变化过程如图：
算法：
p->next = q->next; q->next =->prior = p; free(q);循环链表和单链表的区别在于，表中最后一个结点的指针不是 NULL，而改为指向头结点，从而整体形成一个环，如图：
判空条件不再是头结点的指针域是否为空，而是判断头结点的指针域是否等于头指针。
在循环双链表中，头结点的 prior 指针还要指向表尾结点，如图：
在双链表中 L 中，某结点 *p 为尾结点时，p->next == L; 当循环双链表为空表时，其头结点的 prior 和 next 域都等于 L。
静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域 data 和指针域 next，这里的指针域是结点的相对地址（数组下标），又称为游标。
顺序表可以顺序存取，也可以随机存取。链表只能从表头顺序存取元素。
