AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】单链表--＞详细讲解，后赋源码

2024-08-08 28
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】单链表--＞详细讲解，后赋源码

前面已经介绍顺序表，顺序表存在一定的局限性，空间管理上存在一定的缺陷，今天介绍新的存储结构单链表。

前言：

单链表是一种基本的数据结构，它由一系列节点组成，每个节点包含数据部分和一个指向下一个节点的指针。在单链表中，每个节点的地址不一定是连续的，而是通过指针相互链接起来。单链表的特点是存储灵活，可以动态地添加或删除节点，不需要预先分配固定大小的存储空间。

一、单链表基本介绍

单链表创建

1.定义节点结构体：首先需要定义一个结构体来表示链表的节点，通常包括数据域和指针域。

2.动态创建节点：使用malloc函数为每个节点分配内存空间，并初始化数据域和指针域。

3.插入节点：根据需要将新节点插入到链表的适当位置。插入操作可以是头插法或尾插法。

4.遍历链表：通过遍历链表，可以访问链表中的每个节点，通常用于打印或搜索特定数据。

单链表的操作

单链表的常见操作包括插入、删除、查找和遍历。这些操作通常涉及到对链表节点的指针进行操作，以实现数据的动态管理。

单链表的理解

链表同名字一样，像一个链子一样，有一个一个节点相连接。

A

B

C

D

E

....

二、单链表的实现

2.1 单链表的功能

分装成函数，有助于我们一一管理。

// 动态申请一个节点
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 SLTInsert(SListNode** pplist, SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos); 
// 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos);
///删除pos前面的值
void SListEraseFront(SListNode* pos);
//单链表的销毁
void SLTDestory(SListNode** pphead);

2.2 定义节点结构体

数域 和 指针域

typedef int SLTDateType;

typedef struct SListNode
{
  SLTDateType data;
  struct SListNode* next;
}SListNode;

2.3 动态创建节点

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

  return newcode;
}

2.4 单链表的尾插

断言 pplist 避免传参时候造成不必要的麻烦

//单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
  assert(pplist);
  SListNode* newcode = BuySListNode(x);

  if (*pplist == NULL)
  {
    *pplist = newcode;
  }
  else
  {
    //找尾
    SListNode* tail = *pplist;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newcode;
  }
}

2.5 单链表的尾删除

//单链表尾删
void SListPopBack(SListNode** pplist)
{
  //节点断言
  assert(pplist);
  assert(*pplist);
  //存在节点 1.存在一个节点 2.存在两个节点
  if ((*pplist)->next == NULL)
  {
    free(*pplist);
    *pplist = NULL;
  }
  else
  {
    //找尾

    //SListNode* tail = *pplist;
    //while (tail->next->next != NULL)
    //{
    //  tail = tail->next;
    //}
    //free(tail->next);
    //tail->next = NULL;

    SListNode* prv = NULL;
    SListNode* tail = *pplist;
    while (tail->next != NULL)
    {
      prv = tail;
      tail = tail->next;
    }

    free(tail);
    prv->next = NULL;
  }
}

2.6 单链表的头插

这个相对简单

//单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
  SListNode* newcode = BuySListNode(x);
  newcode->next = *pplist;
  *pplist = newcode;
}

2.7 单链表的查找

//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
  SListNode* cur = plist;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

2.8 单链表在指定位置（pos）的插入

2.8.1 在pos后面
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  assert(pos);
  SListNode* newcode = BuySListNode(x);
  newcode->next = pos->next;
  pos->next = newcode;
}
2.8.2 在pos前面插入
// 在pos的前面插入
void SLTInsert(SListNode** pplist, SListNode* pos, SLTDateType x)
{
  assert(pplist);
  assert(*pplist);

  SListNode* newcode = BuySListNode(x);
  if (pos == *pplist)
  {
    SListPushFront(pplist,x);
  }
  else
  {
    SListNode* cur = *pplist;
    while (cur->next != pos)
    {
      cur = cur->next;
    }
    newcode->next = pos;
    cur->next = newcode;
  }
}
2.8.3 在pos后面插入
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  assert(pos);
  SListNode* newcode = BuySListNode(x);
  newcode->next = pos->next;
  pos->next = newcode;
}

2.9 在指定位置（pos）删除

2.9.1 删除在pos位置前面
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
  SListNode* del = pos->next;
  pos->next = pos->next->next;
  free(del);
  del = NULL;
}
2.9.2 删除 pos 本位上的值
// 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos)
{
  assert(pplist);
  assert(*pplist);

  SListNode* tail = *pplist;
  while (tail->next != pos)
  {
    tail = tail->next;
  }
  tail->next = pos->next;
  free(pos);
  pos = NULL;
}
2.9.3 删除pos位置后面的值
//删除pos前面的值
void SListEraseFront(SListNode** pplist,SListNode* pos)
{
  assert(pplist);
  assert(*pplist);

  SListNode* tail = *pplist;
  while (tail->next->next != pos)
  {
    tail = tail->next;
  }
  SListNode* del = tail->next;
  tail->next = pos;
  free(del);
  del = NULL;
}

2.10 单链表的销毁

不可以直接销毁*pplist，内存存贮不是连续的需要一个一个销毁。

//销毁链表
void SLTDestory(SListNode** pplist)
{
  assert(pphead);
  SListNode* cur = *pphead;
  while (cur)
  {
    SListNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;


源码

SLT.h

#pragma once


#include <stdio.h>
#include <assert.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 SLTInsert(SListNode** pplist, SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos); 
// 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos);
///删除pos前面的值
void SListEraseFront(SListNode* pos);
//单链表的销毁
void SLTDestory(SListNode** pplist);

SLT.c

#define _CRT_SECURE_NO_WARNINGS
#include"SLT.h"


//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
  SListNode* newcode = (SLTDateType*)malloc(sizeof(SListNode));
  if (newcode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  newcode->data = x;
  newcode->next = NULL;

  return newcode;
}

//打印单链表
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)
{
  SListNode* newcode = BuySListNode(x);

  if (*pplist == NULL)
  {
    *pplist = newcode;
  }
  else
  {
    //找尾
    SListNode* tail = *pplist;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newcode;
  }
}


//单链表尾删
void SListPopBack(SListNode** pplist)
{
  //节点断言
  assert(*pplist);
  //if（(*pplist)==NULL）
  // return ;

  //存在节点 1.存在一个节点 2.存在两个节点
  if ((*pplist)->next == NULL)
  {
    free(*pplist);
    *pplist = NULL;
  }
  else
  {
    //找尾

    //SListNode* tail = *pplist;
    //while (tail->next->next != NULL)
    //{
    //  tail = tail->next;
    //}
    //free(tail->next);
    //tail->next = NULL;

    SListNode* prv = NULL;
    SListNode* tail = *pplist;
    while (tail->next != NULL)
    {
      prv = tail;
      tail = tail->next;
    }

    free(tail);
    prv->next = NULL;
  }
}


//单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
  SListNode* newcode = BuySListNode(x);
  newcode->next = *pplist;
  *pplist = newcode;
}

//单链表头删
void SListPopFront(SListNode** pplist)
{
  //节点断言
  assert(*pplist);

  SListNode* first = *pplist;
  *pplist = first->next;
  free(first);
  first = NULL;
}

//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
  SListNode* cur = plist;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  assert(pos);
  SListNode* newcode = BuySListNode(x);
  newcode->next = pos->next;
  pos->next = newcode;
}

// 在pos的前面插入
void SLTInsert(SListNode** pplist, SListNode* pos, SLTDateType x)
{
  assert(pplist);
  assert(*pplist);

  SListNode* newcode = BuySListNode(x);
  if (pos == *pplist)
  {
    SListPushFront(pplist,x);
  }
  else
  {
    SListNode* cur = *pplist;
    while (cur->next != pos)
    {
      cur = cur->next;
    }
    newcode->next = pos;
    cur->next = newcode;
  }
}

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
  SListNode* del = pos->next;
  pos->next = pos->next->next;
  free(del);
  del = NULL;
}

// 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos)
{
  assert(pplist);
  assert(*pplist);

  SListNode* tail = *pplist;
  while (tail->next != pos)
  {
    tail = tail->next;
  }
  tail->next = pos->next;
  free(pos);
  pos = NULL;
}

//删除pos前面的值
void SListEraseFront(SListNode** pplist,SListNode* pos)
{
  assert(pplist);
  assert(*pplist);

  SListNode* tail = *pplist;
  while (tail->next->next != pos)
  {
    tail = tail->next;
  }
  SListNode* del = tail->next;
  tail->next = pos;
  free(del);
  del = NULL;
}


//销毁链表
void SLTDestory(SListNode** pplist)
{
  assert(pplist);
  SListNode* cur = *pplist;
  while (cur)
  {
    SListNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pplist = NULL;

Test.c

#define _CRT_SECURE_NO_WARNINGS


#include "SLT.h"

void testSList1()
{
  SListNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);

  SListNode* ret = SListFind(plist, 2);
  //ret->data = (ret->data) * 3;

  //SListInsertAfter(ret, 66);

  SLTInsert(&plist, ret, 77);

  //SListEraseAfter(ret);

  //SLTErase(&plist, ret);

  SListEraseFront(&plist, ret);

  SListPrint(plist);

}

void testSList2()
{
  SListNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);


  SListPopFront(&plist);
  SListPopFront(&plist);

  SListPrint(plist);



}

int main()
{

  testSList1();
  //testSList2();


  return 0;
}

文章标签：
存储
关键词：
数据结构源码
数据结构单链表
数据结构单链表源码
chian-ocean
目录
相关文章
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
159 9
ephemerals__
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
71 16
ephemerals__
|
1月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
120 8
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
66 4
java冯坚持
|
2月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
42 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
ephemerals__
|
1月前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
71 3
白子寰
|
2月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
白子寰
26 1
Dylaniou
|
2月前
|
Java C++ 索引
让星星⭐月亮告诉你，LinkedList和ArrayList底层数据结构及方法源码说明
`LinkedList` 和 `ArrayList` 是 Java 中两种常见的列表实现。`LinkedList` 基于双向链表，适合频繁的插入和删除操作，但按索引访问元素效率较低。`ArrayList` 基于动态数组，支持快速随机访问，但在中间位置插入或删除元素时性能较差。两者均实现了 `List` 接口，`LinkedList` 还额外实现了 `Deque` 接口，提供了更多队列操作。
Dylaniou
26 3
ephemerals__
|
1月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
48 0
努力学习的小廉
|
2月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
努力学习的小廉
29 2