线性表：

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的.

线性表在物理上存储时，通常以数组(顺序表)和链式结构(链表)的形式存储。

顺序表：

在前面的通讯录程序的书写中，我们使用了顺序表来存放每个人的信息。但是我们会发现，顺序表存在以下问题：

中间/头部的插入删除，时间复杂度为O(N)

增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

链表

1 链表的概念及结构

概念：

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

05e6a07ecfdbbc8f95142e9dafe4dbf8_cbbc98b0fe69495a8b4b6a5abe3d1857.png

注意：

从上图看出，链式结构在逻辑上是连续的，但在物理上不一定连续

现实中的结点一般是从堆上申请出来的

从堆上申请的空间，是按照一定的策略来分配的，两次申请空间可能连续可能不连续。

2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

单向或者双向

带头或者不带头

循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

02c2d0b5ef1cf1848244918f7a8e2a6a_78a6101fbbf04722a77c687a7478caaa.png

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

3.链表的实现

无头+单向+非循环链表增删查改实现

typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
我们先来看看链表的结构：
用data来保存数据，用*next保存下一个链表的指针。
动态申请一个结点
SLTNode* BuySLTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
  perror("malloc fail");
  return NULL;
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}

单链表打印

在这里我们可以看出我们是如何遍历链表的：通过寻找NULL来遍历。

void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  //while (cur->next != NULL)
  //while(cur != NULL)
  while (cur)
  {
  printf("%d->", cur->data);
  cur = cur->next;
  //cur++;
  }
  printf("NULL\n");
}

单链表尾插

这段代码会出现两个问题：

这里有一个很致命的问题，就是断言问题。大家在以往的学习中会习惯性的以为出现指针就断言，但是实际上应该具体情况具体分析！

我们的链表在没有建立之前都是不存在的，此时head指向NULL，但是如果断言的话就会无法建立链表。所以我们不应该对于head进行断言。

当传过来的指针为空时，我们要通过二级指针使head指向第一个链表的头节点，所以我们要穿head指针的地址！当然，head指针的地址不可能为空，所以我们要断言他！

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuySLTNode(x);
  if (*pphead == NULL)
  {
  *pphead = newnode;
  }
  else
  {
  // 找尾
  SLTNode* tail = *pphead;
  while (tail->next != NULL)
  {
    tail = tail->next;
  }
  tail->next = newnode;
  }
}

单链表的头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}

单链表的尾删

对于删除链表，我们是一定要断言的，因为对于空我们是无法删除的！我们只需找到倒数第二个节点然后把其next置空即可。

void SLTPopBack(SLTNode** pphead)
{
  // 暴力检查
  assert(pphead);
  assert(*pphead);
  // 温柔的检查
  //if (*pphead == NULL)
  //  return;
  // 1、只有一个节点
  // 2、多个节点
  if ((*pphead)->next == NULL)
  {
  free(*pphead);
  *pphead = NULL;
  }
  else
  {
  // 找尾
  //SLTNode* prev = NULL;
  //SLTNode* tail = *pphead;
  //while (tail->next != NULL)
  //{
  //  prev = tail;
  //  tail = tail->next;
  //}
  //free(tail);
  //tail = NULL;
  //prev->next = NULL;
  SLTNode* tail = *pphead;
  while (tail->next->next != NULL)
  {
    tail = tail->next;
  }
  free(tail->next);
  tail->next = NULL;
  } 
}

单链表头删

void SLTPopFront(SLTNode** pphead)
{
  // 暴力检查
  assert(pphead);
  assert(*pphead);
  // 温柔的检查
  //if (*pphead == NULL)
  //  return;
  SLTNode* first = *pphead;
  *pphead = first->next;
  free(first);
  first = NULL;
}

单链表查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
  if (cur->data == x)
  {
    return cur;
  }
  cur = cur->next;
  }
  return NULL;
}

单链表在pos位置之后插入x

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

分析思考为什么不在pos位置之前插入？

我们先来看看前插的代码：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pos);
  assert(pphead);
  if (pos == *pphead)
  {
  SLTPushFront(pphead, x);
  }
  else
  {
  // 找到pos的前一个位置
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  SLTNode* newnode = BuySLTNode(x);
  prev->next = newnode;
  newnode->next = pos;
  }
}

在单链表我们无法通过节点找到该节点的上一个节点。要在pos前面插入节点，需要从前向后遍历链表，时间复杂度会变高。所以我们一般都是后插。

单链表删除pos位置之后的值

void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
  assert(pos->next);
  //SLTNode* del = pos->next;
  //pos->next = pos->next->next;
  //free(del);
  //del = NULL;
  SLTNode* del = pos->next;
  pos->next = del->next;
  free(del);
  del = NULL;
}

分析思考为什么不删除pos位置？

同样的先看看代码：

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  //assert(*pphead);
  if (*pphead == pos)
  {
  SLTPopFront(pphead);
  }
  else
  {
  // 找到pos的前一个位置
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  prev->next = pos->next;
  free(pos);
  //pos = NULL;
  }
}

我们还是要先通过遍历找到pos的前一个节点，所以时间复杂度也会增加。

总结：

对于每一个问题的所有情况都应该考虑周全。比如在对链表进行操作时，链表为空的情况，链表不为空都是只有一个链表的等等情况如何处理，头指针在什么时候需要断言的思考。

更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

【数据结构】链表

线性表：

顺序表：

链表

1 链表的概念及结构

2 链表的分类

3.链表的实现

总结：

热门文章

最新文章

相关课程

相关电子书