单链表建立——头插法和尾插法

大家好，欢迎来到IT知识分享网。

引言

当我们准备采用单链表形式实现线性表，第一步就是要建立单链表，即初始化。由于链表是一个动态结构，不需要预先分配空间，因此生成链表的过程就是“逐个插入”的过程，插入结点的位置可以让我们自由选择，故有了“头插法”和“尾插法”这两种方法。

1、头插法（前插法）

课本的解释：通过将新结点逐个插入链表的头部（头节点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。

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

算法描述：

void CreateList(LinkList &L, int n) { 
    L=new LNode; L->next=NULL; //建立带头结点的空表  for(int i=0;i<n;i++) { 
    p=new LNode; //生成新结点  cin>>p->data; //输入元素值赋给新结点*p的数据域  p->next=L->next; //这一步和下一步是将新结点*p插入到头结点子之后  L->next=p; } } 

时间复杂度：O(n)

2、尾插法（后插法）

课本的解释：通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样，每次申请一个新结点，读入相应的数据元素值。不同的是，为了使新结点能够插入到表尾，需要增加一个尾指针 r 指向链表的尾结点。

重点：生成的一个新结点是直接插入当前链表的尾部，也就是让原来最后一个结点指向该新结点。这也是链表长度增长的一种最基本的方式。通过这种方法建立的链表是后来居后的，即链表是顺序的。一般情况下使用尾插法更方便。

算法描述：

void CreateList(LinkList &L, int n) { 
    L = new LNode; L->next = NULL; // 建立带头结点的空表 LinkList r = L; // 尾指针r指向头结点 for (int i = 0; i < n; i++) { 
    LinkList p = new LNode; // 生成新结点 cin >> p->data; // 输入元素值赋给新结点*p的数据域 p->next = NULL; // 新结点的next初始化为NULL r->next = p; // 将新结点*p插入到尾结点r之后 r = p; // 更新r指向新的尾结点*p } } 

时间复杂度：O(n)