【单链表】

本文围绕以下七个部分展开：

一、单链表
二、读取
三、插入
四、删除
五、整表创建
六、整表删除
七、单链表与顺序存储方式的比较






一、单链表

二、读取

        该算法主要核心思想：“工作指针后移”。该算法就是：从头开始找，直到第i个元素为止。最坏时间复杂度：O(n)。



三、插入

四、删除

        插入与删除算法均由两部分组成：

            （1）遍历查找第i个结点：时间复杂度：O(n)

            （2）插入和删除结点：时间复杂度：O(1)

            故：对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。



五、整表创建

            单链表的创建过程，是一个动态生成链表的过程。即：从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

            1. 头插法

            让新结点始终在第一的位置。

            2. 尾插法

六、整表删除

七、单链表与顺序存储方式的比较

            （1）当线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。
            若需要频繁插入和删除时，宜采用单链表结构。

            （2）当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。
            而若事先知道线性表的大致长度，用顺序存储结构，效率会高很多。






整理时重点参考：《大话数据结构》程杰著