本章重点

• 链表
• 链表的结合实现
• 顺序表和链表的区别和联系

1.链表

顺序表的问题及思考

顺序表的优点：

1. 顺序表中的元素在内存中是连续存储的，因此可以通过索引直接访问任意位置的元素。
2. 顺序表尾插尾删操作实现简单。

问题：

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

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看。

链表的概念

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

特点： 链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成 （malloc），每个节点包括两个部分：

• 一个是存储数据元素的数据域：存放各种实际的数据
• 另一个是存储下一个节点地址的指针域：存放下一节点的首地址

链表的概念结构

2.链表的结合实现

(1)、动态申请一个结点：SLTNode* BuySListNode(SLTDataType x)

注意：我们这里只申请了结点，并没有进行连接，后续通过头插或者尾插进行连接。

// 动态申请一个结点
SLTNode* BuySListNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        perror("malloc");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

(2)、单链表尾插：void SListPushBack(SLTNode** pplist, SLTDataType x)

单链表如何尾插入？只需将尾插的结点的地址给到前一个结点的空白位置（也就是前结点->next）

问题：我们上面的代码中，tail 指针的位置不对，遍历寻找尾节点的循环没有正确地将新节点连接到尾节点的 next 上，通过遍历寻找尾结点，当 tail 为空时，由于上一个结点的 next 也为空，此时链接会造成对空指针的解引用操作，tail = newnode，虽然 tail 被修改为 newnode 的值，但是上一个结点的 next 的值没有被修改为 newnode 的值，而不会影响链表本身。正确的做法是，要将新节点连接到前一个节点的 next 上，然后更新尾节点指针，让其指向空地址处。

如果我们刚开始一个结点也没有，我们就需要对链表为空作单独处理

上面的代码有什么问题吗？我们先来看一下交换两个指针变量需要怎么交换呢？

void Swap1(int *p1, int *p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void Swap2(int** pp1, int** pp2)
{
  int* tmp = *pp1;
  *pp1 = *pp2;
  *pp2 = tmp;
}
int main()
{
  int a = 0, b = 1;
  Swap1(&a, &b);//数据交换需要传入地址
  int* p1 = &a, * p2 = &b;
  Swap1(p1, p2);
  //修改版本
  Swap2(&p1, &p2);
  return 0;
}

交换两个指针变量需要将指针变量的地址，也就是二级指针传入到函数参数，通过二级指针去找到指针变量从而去交换它们。传入指针变量只是在函数内部交换了，并没有交换原数据。所以我们上面写的代码并没有将plist指针修改，只在函数内部修改了pplist，出了函数pplis这个局部遍历就被释放了，plist仍然指向空地址处。

// 单链表尾插
void SListPushBack(SLTNode** pplist, SLTDataType x)
{
  assert(pplist);
    SLTNode* newnode = BuySListNode(x);
  if (*pplist == NULL)
  {
    //改变的结构体指针，要传入二级指针
    *pplist = newnode;//传入地址才能修改原数据
  }
  else
  {
    SLTNode* tail = *pplist;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    //改变结构体内容，用结构体的指着即可
    tail->next = newnode;
    //这里不用写newnode->next = NULL；该BuySListNode函数已经处理了
  }
}

总结：要改变函数传入的参数，就需要传入要改变这个参数的地址。

• int ----- 传入int*
• int* ------- 传入int**

(3)、单链表的头插：void SListPushFront(SLTNode** pplist, SLTDataType x)

单链表的头插我们首先需要将头结点所指向的结点给到要插入结点的next位置（防止后面的结点丢失），然后再将要插入的结点的地址给到头结点。

// 单链表的头插
void SListPushFront(SLTNode** pplist, SLTDataType x)
{
    assert(pplist); 
    SLTNode* newnode = BuySListNode(x);
  newnode->next = *pplist;
  *pplist = newnode;
}

(4)、单链表的尾删：void SListPopBack(SLTNode** pplist)

下面这样写有问题吗嘛？

【编织时空二：探究顺序表与链表的数据之旅】（下）：https://developer.aliyun.com/article/1424872