计算机二级公共基础知识章节知识点：1.5线性链表

　　前面的线性表均是采用顺序存储结构及在顺序存储结构下的运算。
　　1）顺序存储的优点：结构简单、运算方便
　　2）顺序存储结构的缺点：
　　对于大的线性表或元素变动频繁的大线性表不宜采用顺序存储结构，而应采用链式存储结构。
　　3）链式存储结构  
　　在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系不一致，而数据元素之间的逻辑关系是由指针域来确定的。
　　链式存储结构既可以用于线性结构，也可用于非线性结构。
　　4）线性链表
　　线性表的链式存储结构称为线性链表。
　　对于线性链表，可以从头指针开始，沿着各结点的指针扫描到链表中的所有结点。
　　这种线性链表称为线性单链表，即可以从表头开始向后扫描链表中的所有结点，而不能从中间或表尾结点向前扫描位于该结点之前的元素。
　　这种链表结构的缺点是不能任意地对链表中的元素按下同的方向进行扫描。在某些应用时，如果对链表中的元素设置两个指针域，一个为指向前件的指针域，称为左指针（LLink），一个为指向后件的指针域，称为右指针（RLink）。则这种链表是双向链表。
　　5）带链的栈 来自www.examzz.com
　　带链的栈即是用来收集计算机存储空间中的所有空闲的存储结点，这种带链的栈称为可利用栈。
　　在计算机中所有空闲的空间，均可以以结点的方式链接到可利用栈中，随着其他线性链表中结点的插入与删除，可利用栈处于动态变化之中，即可利用栈经常要进行退栈和入栈操作。
　　6）带链的队列
　　队列也是线性表，也可利用链式存储结构来进行保存。

　　线性链表包括的基本运算：
　　在链表中包含指定元素的结点之前插入一个新元素
　　在链表中删除包含指定元素的结点
　　将两个线性链表按要求合并成一个线性链表
　　将一个线性链表按要求进行分解
　　逆转线性链表
　　复制线性链表
　　线性链表的排序
　　线性链表的查找
　　1）线性链表中查找指定的元素
　　在线性链表中查找元素X：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为X为止。在查找时，往往是需要记录下该结点的前一个结点。
　　2）线性链表的插入
　　线性链表的插入即在链式存储结构的线性表中插入一个新元素。
　　线性链表的插入操作，新结点是为来自于可利用栈，因此不会造成线性表的溢出。同样，由于可利用栈可被多个线性表利用，因此，不会造成存储空间的浪费，大家动态地共同使用存储空间。
　　3）线性链表的删除
　　线性链表的删除，即是在链式存储结构下的线性表中删除指定元素的结点。
　　操作方式：
　　（1）在线性表中找到包含指定元素x的前一个结点p
　　（2）将该结点p后的包含元素x的结点从线性链表中删除，然后将被删除结点的后一个结点q的地址提供给结点p的指针域，即将结点p指向结点q。
　　（3）将删除的结点送回可利用栈。
　　从以上的删除操作可见，删除一个指定的元素，不需要移动其他的元素即可实现，这是顺序存储的线性表所不能实现的。同时，此操作还可更有效地利用计算机的存储空间。