1. 顺序表的问题及思考

问题：

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

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

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

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

2.链表的概念结构和分类

2.1 概念及结构

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

2.2 分类

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

1. 单项或者双向

2. 带头或者不带头

3. 循环或者非循环

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

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

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

下面我就来实现一下无头单向非循环链表~

3. 单链表的实现

这里我就具体实现一下接口~（SList.h)

#define _CRT_SECURE_NO_WARNINGS
#pragma once//避免头文件被多次引用
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SListDataType;//便于改变数据类型
 
//定义一个结构体类型的节点
typedef struct SListNode
{
  SListDataType data;
  struct SListNode* next;//存储下一个节点的地址
}SListNode;
 
//1. 新节点的创建
SListNode* SListCreatNode(SListDataType x);
 
//2. 打印单链表
void PrintSList(SListNode* phead);
 
//3. 头插
void SListPushFront(SListNode** phead, SListDataType x);
 
//4. 头删
void  SListPopFront(SListNode** phead);
 
//5. 尾差
void SListPushBack(SListNode** phead, SListDataType x);
 
//6. 尾删
void  SListPopBack(SListNode** phead);
 
//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x);
 
//8. 在pos位置修改
void SListModify(SListNode* pos, SListDataType x);
 
//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x);
 
//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos);
 
//11. 销毁单链表
void SListDestroy(SListNode** phead);

3.1 新节点的创建

(1)代码实现

//1. 新节点的创建
SListNode*  SListCreatNode(SListDataType x)
{
  SListNode* NewNode= (SListNode*)malloc(sizeof(SListNode));//开辟空间
  if (NewNode == NULL)//判断空间是否开辟成功
  {
    perror("malloc fail");
    return NULL;
  }
  NewNode->data = x;//赋值
  NewNode->next = NULL;//置空
  return NewNode;
}

3.2 打印单链表

(1)代码实现

//2. 打印单链表
void PrintSList(SListNode* phead)
{
  if (phead == NULL)
  {
    printf("NULL");//如果链表没有元素就打印NULL
    return;
  }
  SListNode* cur = phead;
  //循环单链表打印
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

(2) 复杂度分析

时间复杂度：因为需要遍历整个链表，显然时间复杂度为O(N)。
空间复杂度：打印链表不需要格外的空间，所以空间复杂度为O(1).

3.3 头插

(1)代码实现

//3. 头插
void SListPushFront(SListNode** phead, SListDataType x)
{
  assert(phead);
  SListNode* newnode =SListCreatNode(x);//创建一个新节点
  newnode->next =*phead;
  *phead = newnode;
}

(2) 复杂度分析

时间复杂度：不需要额外时间的消耗，时间复杂度为O(1)。
空间复杂度：固定创造一个节点，空间复杂度为O(1)。

3.4 头删

(1)代码实现

//4. 头删
void  SListPopFront(SListNode** phead)
{
  assert(phead);
  assert(*phead);//如果没有数据就不用头删，并报错
  SListNode* cur = (*phead)->next;
  free(*phead);
  *phead = cur;
}

(2) 复杂度分析

时间复杂度：不需要额外时间的消耗，时间复杂度为O(1)。
空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.5 尾插

(1)代码实现

//5. 尾插
void SListPushBack(SListNode** phead, SListDataType x)
{
  assert(phead);
  if (*phead == NULL)
  {
    *phead = SListCreatNode(x);//创建新节点并插入
  }
  else
  {
    SListNode* tail = *phead;
    while (tail->next != NULL)//找到尾节点
    {
      tail = tail->next;
    }
    tail->next = SListCreatNode(x);//创建新节点并插入
  }
}

(2) 复杂度分析

时间复杂度：需要遍历整个链表，时间复杂度为O(N)。
空间复杂度：固定创造一个节点，空间复杂度为O(1)。

3.6 尾删

(1)代码实现

//6. 尾删
void  SListPopBack(SListNode** phead)
{
  assert(phead);
  assert(*phead);//链表为空就不进行尾删
  SListNode* tail = *phead;
  if (tail->next == NULL)//如果链表就只有一个元素就进行头删
  {
    SListPopFront(phead);
  }
  else
  {
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}

(2) 复杂度分析

时间复杂度：需要遍历整个链表，时间复杂度为O(N)。
空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.7 查找元素X

(1)代码实现

//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x)
{
  assert(phead);
  while (phead->next!=NULL)//注意最后一个节点是没有查找的
  {
    if (phead->data == x)
      return phead;
      phead = phead->next;
  }
  if (phead->data == x)
    return phead;//最后一个节点没有查找
  else
  return NULL;//没找到
}

(2) 时间复杂度

时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.8 在pos位置修改

(1)代码实现

 
//8. 在pos位置修改
void SListModify( SListNode* pos, SListDataType x)
{
  assert(pos);
  pos->data = x;
}

(2) 时间复杂度

时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.9 在任意位置之前插入

(1)代码实现

//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x)
{
  assert(phead);
  assert(*phead);
  if (pos==*phead)//如果pos位置刚好是第一个节点就进行头插
  {
    SListPushFront( phead,x);
  }
  else
  {
    SListNode* newnode = SListCreatNode(x);
    SListNode* cur = *phead;
    while (cur->next != pos)//找到pos前一个节点
    {
      cur = cur->next;
    }
    cur->next = newnode;
    newnode->next  = pos;
  }
}

(2) 复杂度分析

时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.10 在任意位置删除

(1)代码实现

//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos)
{
  assert(phead && *phead && pos);
  if (pos==*phead)//如果pos位置就是第一个节点就进行头删
  {
    SListPopFront(phead);
  }
  else
  {
    SListNode* cur = *phead;
    while (cur->next != pos)//找到pos前一个节点
    {
      cur = cur->next;
    }
    cur->next = pos->next;
    free(pos);
  }
}

(2) 复杂度分析

时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.11 单链表的销毁

(1)代码实现

//11. 销毁单链表
void SListDestroy(SListNode** phead)
{
  assert(*phead && phead);
  SListNode* cur = *phead;
  while (cur!= NULL)
  {
    SListNode* tmp = cur->next;
    free(cur);
    cur = tmp;
  }
  *phead = NULL;
}

(2) 复杂度分析

时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

4. 完整代码

SList.c

#define _CRT_SECURE_NO_WARNINGS
 
#include"SList.h"
 
//1. 新节点的创建
SListNode*  SListCreatNode(SListDataType x)
{
  SListNode* NewNode= (SListNode*)malloc(sizeof(SListNode));//开辟空间
  if (NewNode == NULL)//判断空间是否开辟成功
  {
    perror("malloc fail");
    return NULL;
  }
  NewNode->data = x;//赋值
  NewNode->next = NULL;//置空
  return NewNode;
}
 
//2. 打印单链表
void PrintSList(SListNode* phead)
{
  if (phead == NULL)
  {
    printf("NULL");//如果链表没有元素就打印NULL
    return;
  }
  SListNode* cur = phead;
  //循环单链表打印
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
 
//3. 头插
void SListPushFront(SListNode** phead, SListDataType x)
{
  assert(phead);
  SListNode* newnode =SListCreatNode(x);//创建一个新节点
  newnode->next =*phead;
  *phead = newnode;
}
 
//4. 头删
void  SListPopFront(SListNode** phead)
{
  assert(phead);
  assert(*phead);//如果没有数据就不用头删，并报错
  SListNode* cur = (*phead)->next;
  free(*phead);
  *phead = cur;
}
 
//5. 尾插
void SListPushBack(SListNode** phead, SListDataType x)
{
  assert(phead);
  if (*phead == NULL)
  {
    *phead = SListCreatNode(x);//创建新节点并插入
  }
  else
  {
    SListNode* tail = *phead;
    while (tail->next != NULL)//找到尾节点
    {
      tail = tail->next;
    }
    tail->next = SListCreatNode(x);//创建新节点并插入
  }
}
 
//6. 尾删
void  SListPopBack(SListNode** phead)
{
  assert(phead);
  assert(*phead);//链表为空就不进行尾删
  SListNode* tail = *phead;
  if (tail->next == NULL)//如果链表就只有一个元素就进行头删
  {
    SListPopFront(phead);
  }
  else
  {
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}
 
//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x)
{
  assert(phead);
  while (phead->next!=NULL)//注意最后一个节点是没有查找的
  {
    if (phead->data == x)
      return phead;
      phead = phead->next;
  }
  if (phead->data == x)
    return phead;//最后一个节点没有查找
  else
  return NULL;//没找到
}
 
//8. 在pos位置修改
void SListModify( SListNode* pos, SListDataType x)
{
  assert(pos);
  pos->data = x;
}
 
//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x)
{
  assert(phead);
  assert(*phead);
  if (pos==*phead)//如果pos位置刚好是第一个节点就进行头插
  {
    SListPushFront( phead,x);
  }
  else
  {
    SListNode* newnode = SListCreatNode(x);
    SListNode* cur = *phead;
    while (cur->next != pos)//找到pos前一个节点
    {
      cur = cur->next;
    }
    cur->next = newnode;
    newnode->next  = pos;
  }
}
 
//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos)
{
  assert(phead && *phead && pos);
  if (pos==*phead)//如果pos位置就是第一个节点就进行头删
  {
    SListPopFront(phead);
  }
  else
  {
    SListNode* cur = *phead;
    while (cur->next != pos)//找到pos前一个节点
    {
      cur = cur->next;
    }
    cur->next = pos->next;
    free(pos);
  }
}
 
//11. 销毁单链表
void SListDestroy(SListNode** phead)
{
  assert(*phead && phead);
  SListNode* cur = *phead;
  while (cur!= NULL)
  {
    SListNode* tmp = cur->next;
    free(cur);
    cur = tmp;
  }
  *phead = NULL;
}

数据结构之单链表及其实现！

1. 顺序表的问题及思考

2.链表的概念结构和分类

2.1 概念及结构

2.2 分类

3. 单链表的实现

3.1 新节点的创建

3.2 打印单链表

3.3 头插

3.4 头删

3.5 尾插

3.6 尾删

3.7 查找元素X

3.8 在pos位置修改

3.9 在任意位置之前插入

3.10 在任意位置删除

3.11 单链表的销毁

4. 完整代码

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构之单链表及其实现！

1. 顺序表的问题及思考

2.链表的概念结构和分类

2.1 概念及结构

2.2 分类

3. 单链表的实现

3.1 新节点的创建

3.2 打印单链表

3.3 头插

3.4 头删

3.5 尾插

3.6 尾删

3.7 查找元素X

3.8 在pos位置修改

3.9 在任意位置之前插入

3.10 在任意位置删除

3.11 单链表的销毁

4. 完整代码

热门文章

最新文章

相关课程

相关电子书