链表的实现(文末附完整代码)

简介: 链表的实现(文末附完整代码)

链表的概念及结构

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

我们在上一篇文章所学习的顺序表是连续存储的

例如:

顺序表就好比火车上的一排座位,是连续的

而链表就好比是火车的各节车厢,中间有东西将其互相连接的

链表的基本结构图如下:

有一个指针指向下一个节点

链表的概念及结构

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

链表可以是单向和双向,循环和不循环,带头和不带头,这样一组合,就会出现八种类型的列表

单向的列表如下:

双向列表:

相比较单向,双向的增删查改较为容易,他会自带一个prev的节点,能顾标记当前节点的前一个节点

循环列表:

其实循环列表就是最后一个节点指向了开头节点

带头和不带头:

头节点我们可以称其为哨兵位,它是不会在链表中存储有效的数据的

其实八种链表我们最常用的只有两种:

无头单向非循环链表:

带头双向循环列表:

  1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构
  2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是后面的学习中你会发现其实他是比较简单的

链表的实现

首先我们要了解的就是单链表的实现:

头文件如下:

#include<stdio.h>
#include<assert.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
typedef int SLTDateType;
typedef struct SListNode
{
  SLTDateType data;
  struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode** plist);

新节点的创建:

我们要创建一个节点,首先就是要为他动态开辟一个空间

然后再将这个新节点newnode的值赋予x,并且将他的next置为空,然后函数返回这个节点

SListNode* BuySListNode(SLTDateType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  if (newnode == NULL)
  {
    perror("malloc");
    return NULL;
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}

链表的打印:

打印链表是我们可以用一个符号->来代替空格,但是链表实际上是没有这个符号的

我们可以首先定义cur,从链表的第一个节点开始遍历,知道cur为空时,就不会打印了,并且打印一次cur的data,cur要等于cue的next

void SListPrint(SListNode* plist)
{
  SListNode* cur = plist;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

单链表的尾插:

这里我们要注意的是要记得用二级指针,因为当链表为空时,我们要改变的是节点的地址,而我们要改变地址,就要用地址的地址,也就是二级指针

首先,需要插入一个节点我们要做的就是创建一个新节点,我们之前定义了的一个函数直接使用

然后我们创建一个tail指针,让他从链表的第一个位置开始遍历,一直遍历到最后一个节点,此时令tail的next等于newnode即可

void SListPushBack(SListNode** pplist, SLTDateType x)
{
  assert(pplist);
  /*assert(*pplist);*///链表为空时可以尾插
  SListNode* newnode = BuySListNode(x);
  if (*pplist == NULL)
  {
    *pplist = newnode;
  }
  else
  {
    SListNode* tail = *pplist;
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}

单链表的头插:

头插比较简单,我们直接将新节点的next等于链表的第一个节点即可,也就是*pplist,我们传进来的是**pplist,是节点地址的地址,所以我们需要解引用一次才能将地址给newnode的next

void SListPushFront(SListNode** pplist, SLTDateType x)
{
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pplist;
  *pplist = newnode;
}

单链表的尾删:

尾删的情况我们要分为两种:

1.只有一个节点时:

只有一个节点时我们直接free掉这个节点,其次为了防止野指针,我们要将其置空

2.当有多个节点时:

我们创建一个tail和prev,然后用循环将tail遍历到最后一个节点,循环的终止条件时tail->next为空,条件满足时就将tail赋予prev,当跳出循环时,prev就是尾节点的前一个节点,我们直接将tail给free掉,将其置空,这样尾节点就被删除了

void SListPopBack(SListNode** pplist)
{
  assert(*pplist);//链表为空时不能再删,暴力检查 
  if ((*pplist)->next == NULL)
  {
    free(*pplist);
    *pplist = NULL;
  }
  else
  {
    SListNode* prev = NULL;
    SListNode* tail = *pplist;
    while (tail->next)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    prev->next = NULL;
  }
}

单链表的头删:

头删就很简单了,首先定义一个tail存入第一个节点的位置,然后将第一个节点的位置移动到他的next,注意记得将临时存储第一个节点位置的指针给free掉,避免出现野指针的问题

void SListPopFront(SListNode** pplist)
{
  assert(*pplist);//链表为空时不能再删,暴力检查
  SListNode* tail = *pplist;
  *pplist = (tail)->next;
  free(tail);
}

节点的查找:

节点的查找也比较容易,直接用while循环遍历,如果cur的data和x相等,就返回cur,否则就是没有这个节点,返回null

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
  SListNode* cur = plist;
  while (cur->next)
  {
    if (cur->data == x)
    {
      return cur;
      //break;
    }
    cur = cur->next;
  }
  return NULL;
}

在一个节点之后插入节点:

需要插入节点首先要做的就是创建一个新节点

然后首先要做的是将newnode的next连接到要插入位置pos的next

再将pos的next置为newnode

这里注意,位置不能颠倒,不然newnode的next就找不到了

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  assert(pos);
  SListNode* newnode = BuySListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

删除一个节点之后的节点:

要删除节点之后的一个节点,首先这个节点之后一定要有一个节点,所以要对pos->next进行断言

我们将pos->next存储到next中,然后将pos->next直接指向next->next即可,也就是把pos->next=pos->next->next

void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  assert(pos->next);
  //pos->next = pos->next->next;
  SListNode* next = pos->next;
  pos->next = next->next;
  free(next);
}

单链表的销毁:

直接将pplist置空即可

void SListDestroy(SListNode** pplist)
{
  SListNode* node = *pplist;
  node = NULL;
  free(node);
}

好了,今天的分享到这里就结束了,感谢大家的支持!

完整代码如下:

SListNode* BuySListNode(SLTDateType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  if (newnode == NULL)
  {
    perror("malloc");
    return NULL;
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
void SListPrint(SListNode* plist)
{
  SListNode* cur = plist;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
void SListPushBack(SListNode** pplist, SLTDateType x)
{
  assert(pplist);
  /*assert(*pplist);*///链表为空时可以尾插
  SListNode* newnode = BuySListNode(x);
  if (*pplist == NULL)
  {
    *pplist = newnode;
  }
  else
  {
    SListNode* tail = *pplist;
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
void SListPushFront(SListNode** pplist, SLTDateType x)
{
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pplist;
  *pplist = newnode;
}
void SListPopBack(SListNode** pplist)
{
  assert(*pplist);//链表为空时不能再删,暴力检查 
  //SListNode* tail = pplist;
  //while (tail->next->next)
  //{
  //  tail = tail->next;
  //}
  //free(tail->next);
  //tail->next = NULL;
  if ((*pplist)->next == NULL)
  {
    free(*pplist);
    *pplist = NULL;
  }
  else
  {
    SListNode* prev = NULL;
    SListNode* tail = *pplist;
    while (tail->next)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    prev->next = NULL;
  }
}
void SListPopFront(SListNode** pplist)
{
  assert(*pplist);//链表为空时不能再删,暴力检查
  SListNode* tail = *pplist;
  *pplist = (tail)->next;
  free(tail);
}
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
  SListNode* cur = plist;
  while (cur->next)
  {
    if (cur->data == x)
    {
      return cur;
      //break;
    }
    cur = cur->next;
  }
  return NULL;
}
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  assert(pos);
  SListNode* newnode = BuySListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  assert(pos->next);
  //pos->next = pos->next->next;
  SListNode* next = pos->next;
  pos->next = next->next;
  free(next);
}
void SListDestroy(SListNode** pplist)
{
  SListNode* node = *pplist;
  node = NULL;
  free(node);
}
相关文章
|
2月前
|
存储 编译器 C语言
【数据结构】C语言实现带头双向循环链表万字详解(附完整运行代码)
【数据结构】C语言实现带头双向循环链表万字详解(附完整运行代码)
24 0
【数据结构】数组、双链表代码实现
【数据结构】数组、双链表代码实现
|
9月前
代码随想录Day03 | 链表基础1 LeetCode T203 移除链表元素 T707设计链表 T206 反转链表
代码随想录Day03 | 链表基础1 LeetCode T203 移除链表元素 T707设计链表 T206 反转链表
35 0
|
27天前
|
存储 算法
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
|
2月前
leetcode代码记录(移除链表元素
leetcode代码记录(移除链表元素
19 0
|
2月前
|
存储
数据结构基础:一篇文章教你单链表(头插,尾插,查找,头删等的解析和代码)
数据结构基础:一篇文章教你单链表(头插,尾插,查找,头删等的解析和代码)
|
2月前
在实现链表的代码中,为什么要使用继承而不是组合?
在实现链表的代码中,为什么要使用继承而不是组合?
21 3
|
2月前
|
设计模式 测试技术
在实现链表的代码中,为什么要使用`Node`类而不是直接在`LinkedList`类中定义节点?
在实现链表的代码中,为什么要使用`Node`类而不是直接在`LinkedList`类中定义节点?
29 1
|
2月前
【数据结构】双向链表中删除节点的方法实现(代码+详解)
【数据结构】双向链表中删除节点的方法实现(代码+详解)
127 0
|
7月前
数据结构之带头结点的双向循环链表(含全部代码)
数据结构之带头结点的双向循环链表(含全部代码)
41 0