一、链表介绍

顺序表缺点：

1. 中间/头部的插入删除，时间复杂度为O(N),因为需要移动数据.

2. 增容需要申请新空间，特别是异地扩容,拷贝数据，释放旧空间。消耗不小。

3. 增容不是一次增容到位,而是每次增容后判断是否符合要求，并且增容一般是2倍增容,一次次扩容消耗太大.

4. 除此之外,还可能有一定的空间浪费。

例如:当前容量为200，如果有201个待插入数据,势必要增容到400(原来容量的两倍),这样就浪费了199个空间.

我们不妨来看一下链表的存储结构.

链表的概念:

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

🌰栗子

单链表的结点声明:

typedef int DateType;
typedef struct SListN0de
{
  DateType Date;//数据域
  struct SListN0de* next;//指针域
}SLTNode;

结点:

1.1 链表结构图:

通过上图我们不难知道:

1. 链表在逻辑上是连续的(next指针,指向下一个结点,链接在一起),而物理上可能连续,也可能不连续.

2. 链表是由一个个结点链接在一起组成的,每个结点其实是malloc在堆区上申请的,所以地址可能连续,也可能不连续.

1.2 链表分类(图解分析)

共有八种链表,我们主要学习不带头单向链表与带头双向链表,学会这两种,其它的大同小异,写起来并不苦难.

单向、双向:

不带头、带头:

带头与不带头的区别在于:

带头:链表是通过一个特殊的结点—头结点指向链表的第一个有效结点.

不带头:通过结点指针指向链表的第一个有效结点.

头结点作用:传送门

不须换、循环:

重点掌握:

1. 无头单向非循环链表(本篇重点)：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多,因为单链表不能回头,可以考察的地方很多.

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。这种结构的链表虽然结构复杂,但是优势也很明显,并且实现起来反而很简单.后续跟着学到了就可以理解了.

二、单链表实现:

2.1 链表的"结点"声明:

typedef int DateType;
typedef struct SListN0de
{
  DateType Date;//数据域
  struct SListN0de* next;//指针域
}SLTNode;

单链表初始化:

单链表是不需要初始化操作的,只需要创建一个结点指针就行.初始状态:指针指向NULL.

头指针:

SLTNode* plist=NULL;

2.2 "插入"元素操作.

我们需要插入数据时,只需要申请一个结点,将数据放入结点,然后将结点链接起来就行.

单链表的"尾插":

单链表的尾插步骤:

1. 找尾:

由于单链表的结点之间不一定是连续存储的,不支持向顺序表那样的随机访问,需要通过遍历才能找到目标结点.

2. 将最后一个结点的next指向新节点.

图解:

那如果链表本身就是空链表呢?

此时需要修改头指针,将头指针指向这个新节点.

注意:

1. 需要传二级指针:

这点很重要,因为需要修改头指针,而头指针的类型是:SLTNode*,相信友友们学到这里应该知道,如果想要在函数中形参的改变影响实参,则需要传址调用,通过地址来影响实参.

那么,指针的地址是?二级指针相信友友们应该没有忘记.😂😂😂

2. 断言,这里需要灵活断言.

"尾插"函数声明:

void PushBack(SLTNode** pphead, DateType x)

pphead需要断言:

pphead是指向 *pphead(一级指针/头指针)的指针,即值存储的是头指针的地址,只要头指针存在,则不为空.而头指针一定存在.

*phead不能断言:

*phead是头指针,头指针在链表为空时,头指针的值是NULL,所以不能断言.

链表中有数据时,指向第一个结点,值是第一个结点的地址.

3. 头指针是很重要的一个指针,我们都是通过头指针找到链表的,所以,除了头插需要修改头指针以外,其他插入都不能修改头指针,所以我们需要创建一个临时指针:SLTNode*tail = *pphead代替头指针找尾.

代码:

void PushBack(SLTNode** pphead, DateType x)
{
  assert(pphead);//如果头指针的地址为NULL,则报错.
  SLTNode*tail = *pphead;//创建一个指针代替头指针遍历
  SLTNode* newnode = BuyNode(x);
  //*pphead代表代表头指针,phead表示头指针的地址
  //如果*pphead指向NULL,说明为空链表
  if (*pphead == NULL)
  {
    //这里可以使用tail代替*phead吗?
    //不能,因为这里要改变的是,头结点的指针,需要用二级指针(解引用)来改变
    *pphead = newnode;//空链表是将头指针指向新节点
  }
  else
  {
    //找尾巴,画图解析
    //这里可以使用tail,是因为,要改变的是结构体的内容,只需要用结构体指针(解引用)就行
    while ( tail->next != NULL)//如果该节点的下一个节点是空指针则停止循环
    {
      tail = tail->next;
    }
    tail->next = newnode;//让尾节点的next指向新节点.
  }
}

单链表的"头插"

尾插是不是显得有些麻烦?那我们试着看一下头插.

头插步骤:

1. 创建一个新节点.

2. 将新节点指向头指针指向的结点.

3. 更新头指针(头指针指向新节点)

图解:

代码实现:

//写法1
void PushFront(SLTNode** pphead, DateType x)
{
  assert(pphead);
  SLTNode* newnode = BuyNode(x);
  //下面两句的顺序不能变
  newnode->next = *pphead;
  *pphead = newnode;
}

写法2:

//写法2
void PushFront(SLTNode** pphead, DateType x)
{
  assert(pphead);
  SLTNode* newnode = BuyNode(x);
  SLTNode* phead = *pphead;//创建一个临时指针,保存一下头指针指向的头结点.
  //顺序随便改
  *pphead = newnode;
  newnode->next = phead;
}

两种方法都比较好理解,也很简单,单链表的头插效率很高,不需要遍历,

指定位置之后"插入"新节点

该函数很简单,只需要通过查找目标结点函数找到目标结点的位置,然后将将新节点链接上去就行了.

步骤:

1. 将新节点的指针域(next)指向指定结点的下一个结点.

2. 将指定位置的结点的指针域(next)指向新节点,

图解:

//使用此函数之前可以先使用,查找目标结点函数(SListFind),找到位置先
void SLTInsertBack( SLTNode* pos, DateType x)
{
  assert(pos);
  SLTNode* newnode = BuyNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}