【数据结构】单链表的建立——头插法与尾插法

【数据结构】单链表的建立——头插法与尾插法。

单链表的建立

当我们准备采用单链表的形式来实现线性表，那么第一步我们需要考虑到的就是单链表的建立，也就是初始化的过程。而由于链表是一个动态的结构，它不需要预先分配空间，因此生成链表的过程是一个结点“逐个插入”的过程，而结点插入的位置是我们可以选择的，所以按照结点插入的位置可以将单链表的建立方法分为头插法和尾插法。

①头插法

该算法的官方描述为∶从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后。

这里的重点就是：每次生成的新结点都是要与头结点相连接的，每个新结点都插在了原来第一个节点的前面。通过这种方法建立的链表是后来居前的，也就是链表是逆序的。因此，当有题目让我们实现线性表的逆序表示，就应该首先考虑头插法。

图示为：

其中，指针H始终指向头结点，指针s指向新结点。①表示初始化空表②表示申请新结点并赋值③表示插入第一个结点④表示插入第二个结点（④-1和④-2代表了先后顺序）。整个图示过程展现了头插法的基本原理。

对应的算法为：

②尾插法

该算法的官方描述为∶从一个空表开始，重复读入数据，生成新结点将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾结点之后。

这里的重点就是：生成的一个新结点是直接插入当前单链表的尾端，也就是让原来最后一个结点指向该新结点。这也是链表长度增长的一种最基本的方式。后来居后，生成的链表是顺序的。

图示为：

其中指针H始终指向头结点，指针s指向新结点，指针r始终指向单链表的表尾。①表示初始化空表②表示申请新结点并赋值③表示插入第一个结点④表示插入第二个结点（④-1和④-2代表了先后顺序）

整个图示过程展现了尾插法的基本原理。

对应的算法为：

分析完头插法和尾插法，又到了辨析两者时间复杂度的经典问题。

头插法：

每个节点：只需要移动一下它本身和头指针的指向即可，不需要移动其他的元素，实际也和其他的元素没有关系，所以单个节点的时间复杂度是O（n）。

整个链表：设单链表的总长度为n，在一个已有N个元素的单链表中插入元素，如果插入位置为x那么需要找到它的前驱才可以插入，最坏时间复杂度为O（n），时间复杂度也为O（n）

尾插法：

每个节点：只需要移动一下它本身和尾指针的指向即可，不需要移动其他的元素，实际也和其他的元素没有关系，所以单个节点的时间复杂度是O（1）。

整个链表：设单链表的总长度为n，在一个已有N个元素的单链表中插入元素，如果插入位置为x那么需要找到它的前驱才可以插入，最坏时间复杂度为O（n），时间复杂度也为O（n）。

思维导图：