单链表的定义

链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系。除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这里把存储数据元素信息的域称为数据域，把存储直接后继存储位置的域称为指针域；指针域中存储的信息称为指针或链；这两部分信息组成数据元素ai的存储映像，称为节点（Node）。

具有n个结点（的存储映像）链接成一个链表，即为线性表的链式存储结构。由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。如图所示：

单链表有头有尾，整个链表的存储必须从头指针开始进行，头指针指示链表中的第一个结点（即第一个数据元素的存储映像，也称为首元结点）的存储位置。尾结点就是最后一个数据元素，没有直接后继，则单链表中最后一个结点的指针为空（NULL）。如图所示：

通常单链表在第一个结点前附设一个结点，称为头节点。头节点的数据域可以不存储任何信息，也可以存储如链表长度等附加信息；头节点的指针域存储指向第一个结点的指针。如图所示：

单链表的存储结构

单链表可由头指针唯一确定，在C语言中可用“结构指针” 来描述：

typedef struct _LinkedListNode
{
  ElemType data;				//数据类型
  struct _LinkedListNode* next;	//指向直接后继元素的指针
}LinkedListNode, *LinkedList;

• 该结构体定义单链表中每个结点的存储结构，其中包括：存储结点的数据域data，其类型标识符ElemType可以表示int、char、float等，也可以表示自定义的数据类型；存储后继结点位置的指针域next，其类型为指针类型_LinkedListNode*。
• 结构体名称LinkedListNode和*LinkedList是等价的。通常习惯用LinkedList定义单链表，强调定义的是单链表的头指针；用LinkedListNode*定义单链表中任意结点的指针变量。
• 单链表是由表头指针唯一确定，因此单链表可以用头指针的名称命名。若头指针名是L，则简称链表为表L。
• 注意区分指针变量和结点变量是两个不同的概念。定义LinkedListNode *p和LinkedList p，则p为指向结点的指针变量，表示该结点的地址；而*p为对应的结点变量，表示该结点的名称。
• 假设p是指向单链表中第i个元素的指针，则结点ai的数据域用，p->data来表示；结点的指针域，用p->next来表示；p->next指向第i+1个元素，即指向的指针。可以用下图表示：

单链表中的头结点

【首元结点、头指针和头节点的概念】

• 首元结点是指链表中存储第一个数据元素的结点。
• 头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针所指结点为链表的头结点；若链表不设头结点，则头指针所指结点为该链表的首元结点；无论链表是否为空，头指针均不为空；头指针是链表的必要元素。
• 头结点是在首元结点之前附设的一个结点，是为了操作的统一和方便而设立的，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可以存储与数据元素类型相同的其他附加信息。例如，当数据元素为整数型时，头结点的数据域中可存放该线性表的长度。

【链表增加头结点的作用】

• 便于首元结点的处理：增加头结点后，首元结点的地址保存在头结点的指针域中，则对链表的第一个数据元素的操作与其他数据元素相同，插入在表头或者删除第一个结点时无需特殊处理。
• 便于空表和非空表的统一处理：当链表没有头结点，其头指针应该指向首元结点；则当链表的长度为0（空表）时，头指针也为空。当链表有头结点时，无论链表是否为空，头指针都是指向头结点的非空指针。如图所示的非空单链表，头指针指向头结点；若为空表，则头结点的指针域为空。

单链表的初始化

创建头结点，其指针域指向空。

【算法代码】

LinkedList LinkedListInit()
{
  LinkedListNode* header = (LinkedListNode*)malloc(sizeof(LinkedListNode));
  if (nullptr == header)
  {
    cout << "创建链表头失败" << endl;
    return nullptr;
  }
  header->data = 0;
  header->next = nullptr;
  return header;
}

单链表的创建

单链表和顺序表不同，它是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统按需即时生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。从空表的初始状态开始，依次建立各元素的结点，并逐个插入链表。根据结点插入位置的不同，链表的创建方法可以分为头插法和尾插法。

【头插法】

头插法是指每次申请一个新结点，读入相应的数据元素值，然后将新结点从链表的头部之后逐个插入。如图所示，每次将s所指结点插在最前端：

如图所示为线性表(a, b, c, d, e)采用头插法的创建过程。因为每次插入在链表的头部，所以应该逆位序输入数据，依次输入e、d、c、b、a, 输入顺序和线性表中的逻辑顺序是相反的。

【算法代码】

LinkedList LinkedListCreateByHeader(LinkedList slist, ElemType elem)
{
  if (nullptr == slist)
  {
    cout << "链表未初始化" << endl;
    return nullptr;
  }
  else
  {
    LinkedListNode* header = slist;
    LinkedListNode* node = (LinkedListNode*)malloc(sizeof(LinkedListNode));
    if (nullptr == node)
    {
      cout << "创建结点失败" << endl;
      return nullptr;
    }
    else
    {
      node->data = elem;
      node->next = header->next;
      header->next = node;
      return header;
    }
  }
}

釆用头插法建立单链表，读入数据的顺序与生成的链表中元素的顺序是相反的。每个结点插入的时间为，设单链表长为n，则总的时间复杂度为。

【尾插法】

头插法建立单链表的算法虽然简单，但生成的链表中结点的次序与输入数据的顺序相反。尾插法是通过将新结点逐个插入到链表的尾部来创建链表。同头插法一样，每次申请一个新结点，读入相应的数据元素值。不同的是，为了使新结点能插入到链表尾部，必须增加一个尾指针r, 使其始终指向当前链表的尾结点，如图所示：

如图所示为线性表(a, b, c, d, e) 后插法的创建过程，读入数据的顺序和线性表中的逻辑顺序是相同的。

【算法代码】

LinkedList LinkedListCreateByTail(LinkedList slist, ElemType elem)
{
  if (nullptr == slist)
  {
    cout << "链表未初始化" << endl;
    return nullptr;
  }
  else
  {
    LinkedListNode* header = slist;
    LinkedListNode* clist = slist;
    while (nullptr != clist->next)
    {
      clist = clist->next;
    }	
    LinkedListNode* node = (LinkedListNode*)malloc(sizeof(LinkedListNode));
    if (nullptr == node)
    {
      cout << "创建结点失败" << endl;
      return nullptr;
    }
    else
    {
      node->data = elem;
      node->next = nullptr;
      clist->next = node;
      return header;
    }
  }
}

单链表的取值

单链表与顺序表不同，其逻辑相邻的结点并没有存储在物理相邻的单元中。根据给定的结点位置序号i访问该结点的值是行不通的，只能从链表的首元结点出发，顺着链域next逐个结点向下访问。

【算法代码】

LinkedListNode* GetLinkedListNode(LinkedList slist, int pos)
{
  if (nullptr == slist)
  {
    cout << "空链表" << endl;
    return nullptr;
  }
  else if (pos <= 0)
  {
    cout << "输入位置错误" << endl;
    return nullptr;
  }
  else
  {
    LinkedListNode* clist = slist;//当前结点
    for (int i = 0; i < pos && clist->next != nullptr; ++i)
    {
      clist = clist->next;
    }
    return clist;
  }
}

单链表的查找

链表中按值查找的过程和顺序表类似，从链表的首元结点出发，依次将结点值和给定值elem进行比较，返回查找结果。

【算法代码】

LinkedListNode* LocateLinkedListNode(LinkedList slist, ElemType elem)
{
  if (nullptr == slist)
  {
    cout << "空链表" << endl;
    return nullptr;
  }
  else
  {
    LinkedListNode* clist = slist->next;//当前结点
    while (clist && elem != clist->data)
    {
      clist = clist->next;
    }
    return clist; //查找成功返回值为elem的结点地址, 查找失败p为NULL
  }
}

单链表的插入

单链表插入新结点时，根据插入的位置不同，分为以下3种情况：

• 插入到链表的头部（头节点之后），作为首元节点。
• 插入到链表中间的某个位置。
• 插入到链表的尾部，作为链表中最后一个数据元素。

虽然新元素的插入位置不固定，但是链表插入元素的思想是固定的，只需做以下两步操作，即可将新元素插入到指定的位置：

• 将新结点的 next 指针指向插入位置后的结点；
• 将插入位置前结点的 next 指针指向插入结点；

例如，在链表 {1,2,3,4} 的基础上分别实现在头部、中间部位、尾部插入新元素 5，其实现过程如图所示：

注意：链表插入元素的操作必须是先步骤 1，再步骤 2；反之，若先执行步骤 2，除非再添加一个指针，作为插入位置后续链表的头指针，否则会导致插入位置后的这部分链表丢失，无法再实现步骤 1。

【算法代码】

LinkedList LinkedListInsert(LinkedList slist, ElemType elem, int pos)
{
  if (nullptr == slist)
  {
    cout << "空链表" << endl;
    return nullptr;
  }
  else
  {
    LinkedListNode* header = slist;//头结点
    LinkedListNode* clist = slist;//当前结点
    for (int i = 1; i < pos && nullptr != clist->next; ++i)
    {
      clist = clist->next;
    }
    LinkedListNode* node = (LinkedListNode*)malloc(sizeof(LinkedListNode));
    if (nullptr == node)
    {
      cout << "创建结点失败" << endl;
      return nullptr;
    }
    else
    {
      node->data = elem;
      node->next = clist->next;
      clist->next = node;
      return header;
    }
  }
}

单链表的插入操作虽然不需要像顺序表的插入操作那样需要移动元素，但平均时间复杂度仍

为。

单链表的删除

从链表中删除指定数据元素时，实则就是将存有该数据元素的节点从链表中摘除，同插入元素一样，首先应该找到该位置的前驱结点。

例如，从存有{1, 2, 3, 4}的链表中删除元素3，则此代码的执行效果如图所示：

其中，从链表上摘除某节点的实现非常简单，只需找到该节点的直接前驱节点 temp，执行一行程序：

clist->next= clist->next->next;

但在删除数据元素3结点时，除了修改数据元素2结点的指针域外，还要释放数据元素3的结点所占的空间，所以在修改指针前，应该引入另一指针tlist, 临时保存数据元素3结点的地址以备释放。

【算法代码】

LinkedList LinkedListDelete(LinkedList slist, ElemType elem)
{
  if (nullptr == slist)
  {
    cout << "空链表" << endl;
    return nullptr;
  }
  else
  {
    bool FindFlag = false;
    LinkedListNode* header = slist;//头结点
    LinkedListNode* clist = slist;//当前结点
    LinkedListNode* tlist = nullptr;
    while (nullptr != clist->next)
    {
      if (elem == clist->next->data)
      {
        tlist = clist->next;
        clist->next = clist->next->next;
        free(tlist);
        tlist = nullptr;
        FindFlag = true;
        break;
      }
      else
      {
        clist = clist->next;
      }
    }
    if (!FindFlag)
    {
      cout << "未找到该元素: " << elem << endl;
    }
    return header;
  }
}

类似于插入算法，删除算法时间复杂度亦为。

获取链表长度

遍历链表中每一个结点，直到指针域next为空结束，则遍历的次数就是链表的长度。

【算法代码】

int GetLinkedListLength(LinkedList slist)
{
  LinkedListNode* p = slist->next;
  int length = 0;
  while (p)
  {
    ++length;
    p = p->next;
  }
  return length;
}

完整代码

Github：https://github.com/MrYuxiangZhu/DataStructure/tree/master/01.%20LinkedList