【数据结构】链表的学习和介绍-阿里云开发者社区

前言

今天，我们来学习，数据结构中的链表

链表是什么

链表，就是多个结构体变量之间，通过结构体指针连接在一起的一种数据结构

提示：

本篇文章主要讲解动态链表，对于静态链表不做过多介绍

链表的分类

链表可分为静态链表和动态链表

静态链表

只是初步了解，更详细的操作（比如插入节点、删除节点）在这篇文章中不做说明

静态链表，实际上就是一个结构体数组

分配一整片连续的内存空间，各个结构体变量集中安置，逻辑结构上相邻的数据元素，存储在指定的一块内存空间中，数据元素只允许在这块内存空间中随机存放，这样的存储结构生成的链表称为静态链表。也就是说静态链表是用数组来实现链式存储结构

下面，给出一段例子

这就是静态链表的定义和初始化

#include<iostream>
using namespace std;
struct Node
{
  int data;//数据域
  int next;//指针域
  //注释1
  //静态链表的节点是索引值 不是结构体指针
};
int main()
{
  struct Node n[10];
  for (int i = 0; i < 10; i++)
  {
    n[i].data = i;
    n[i].next = i + 1;//每个节点的下一个节点位当前索引值+1
  }
  n[9].next = -1;
  //注释2
  return 0;
}

注释1：

相信大家都知道，链表这种数据结构，前面一部分存储的是数据，后面一部分存储的是指向下一个变量（一般称为节点）的指针

存储数据的区域，就称为数据域

存储指针的区域，就称为指针域

注释2：

n[9].next = -1;

这行代码的意思是：将这个链表的最后一个节点的指针（索引值）赋为-1

为什么要这么做呢？

首先：

当我们已经遍历到最后一个节点时，没有下一个节点了，那么此时的next指针指向的就是一个随机值，这可能会导致发生不可预期的行为，比如程序崩溃

其次，将最后一个节点的指针赋为-1，有便于我们检查对于链表的遍历是否结束，这一点在后面会详细说明

最后，当我们在处理链表的最后一个字节时，可以通过-1来直接找到它

静态链表的特点

静态链表需要预先开辟一块空间来存储，并且，静态链表的大小是固定的，（毕竟它没用到动态内存分配没法变大），以及，静态链表在存储时，在内存中是连续存储的

静态链表也有一些好处，比如：

静态链表可以直接通过索引访问，不需要指针（好像这二者差不多）

动态链表

接下来，就进入到我们这篇文章的重头戏：动态链表了

要实现动态链表，有两个东西比较重要：

动态内存的申请，是动态链表之所以被称为动态链表的原因

模块化设计，可以使代码可读性和简洁性提升（当然，都写在一起也不是不行…）

下文为了便于理解，对于数据域只使用一个int类型的变量

动态链表的实现思路

本篇文章将动态链表的实现分为五个步骤，

1.创建链表表头
2.创建节点
3.插入节点
4.删除节点
5.打印链表

前四步比较关键，最后一步一般用于测试自己创建的链表是否符合自己的预期

创建链表表头

要创建链表，我们首先需要创建一个表头，来指向整个链表，可以将表头理解为第一个节点，

想指向一个结构体变量（也就是节点），那表头应该是结构体指针c

问题来了，如何把一个结构体指针，变成结构体变量呢

这时候，我们就要学习动态内存申请，即malloc函数

（注意：使用new也可以，会在本节的末尾附上使用new创建动态链表的代码）

给出一个示例来说明如何创建头节点

struct Node* createList()
{
  struct Node* headNode = (struct Node*)malloc
  (sizeof(struct Node));
  //
  //用malloc申请内存
  headNode->next = nullptr;
  //注释3
  return headNode;
}

注释3：

有的同学可能会有疑问，为什么要将头节点初始化为空指针

首先，现在链表里只有一个变量（节点），不初始化成空指针，那不就变成野指针了

其次，初始化成空指针的话，当我们后续无论是查找头节点还是继续插入新的节点的时候，都是能很轻松的找到头节点

创建节点（一个）

/*

创建节点的这个函数

/*/

下面给出一个例子：

将创建节点的内容模块化城createNode函数

struct Node* createNode(int data)
{
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  //传入数据
  newNode->next = nullptr;
  //注释4
  return newNode;
}

注释4：

类似的，在创建新的节点时，将next赋值为空指针，

是因为这个新节点并不知道链表中下一个节点是什么，所以只能赋值为空指针

插入节点

对于插入，有三种方式：头插法，尾插法，指定位置插入

下面给出一个使用头插法例子：

将创建节点的内容模块化城insertNodeByHead函数

(代码中给出了相应的注释）

void insertNodeByHead(struct Node* headNode, int data)
{
  struct Node* newNode = createNode(data);
  //创建插入的节点
  newNode->next = headNode->next;
  //修改指针域
  headNode->next = newNode;
  //指向要插入的数据
}

注释5：

在编写创建节点和插入节点的时候，我感觉这两步有一些联系，在此说明一下：

这两个步骤通常是相互关联的，因为通常我们需要先创建一个新的节点，然后将其插入到链表中。

删除节点

下面给出一个例子：

将创建节点的内容模块化城deleteNodeByAppoin函数

(代码中给出了相应的注释）

//删除节点
void deleteNodeByAppoin(struct Node* headNode, int posData)
//headNode只是一个传入的参数名，不是真的头节点 不要弄混
//posData是要删除的数据
{
  struct Node* posNode = headNode->next;
  struct Node* posNodeFront = headNode;
  //分别对于链表是否为空和posData是否存在进行判断
  if (posNode == nullptr)
  {
    cout << "链表为空 操作错误" << endl;
  }
  else
  {
    while (posNode->data != posData)
    //遍历查找
    {
      posNodeFront = posNode;
      posNode = posNodeFront->next;
      if (posNode == nullptr)
      {
        cout << "未找到要删除的数据" << endl;
        return;
      }
    }
    posNodeFront->next = posNode->next;
    //用free函数释放内存
    free(posNode);
  }
}

遍历打印链表

通过遍历打印链表

void PrintList(struct Node* headNode)
{
  struct Node* pMove = headNode->next;
  while (pMove)
  //当pmove不为空指针时 持续遍历
  //这里就可以联系到创建节点时，为什么要将next初始化为空指针
  //巧妙 妙
  //while这里还能这么写 学到了 学到了
  {
    cout << pMove->data;
    pMove = pMove->next;
  }
  cout << endl;
}

主函数

int main()
{
  struct Node* list = createList();
  insertNodeByHead(list, 1);
  insertNodeByHead(list, 2);
  insertNodeByHead(list, 3);
  PrintList(list);
  return 0;
}

运行结果：

注释6：

因为用的是头插法，所以先插入的变量在遍历输出的时候，在后面

完整代码

#include<iostream>
using namespace std;
struct Node
{
  int data;
  struct Node* next;//静态链表的节点是索引值 不是结构体指针
};
//创建表头
struct Node* createList()
{
  struct Node* headNode = (struct Node*)malloc
  (sizeof(struct Node));
  //用malloc申请内存
  headNode->next = nullptr;
  //注释3
  return headNode;
}
//创建节点（一个）
struct Node* createNode(int data)
{
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  //传入数据
  newNode->next = nullptr;
  return newNode;
}
//插入节点
void insertNodeByHead(struct Node* headNode, int data)
{
  struct Node* newNode = createNode(data);
  //创建插入的节点
  newNode->next = headNode->next;
  //修改指针域
  headNode->next = newNode;
  //指向要插入的数据
}
//删除节点
void deleteNodeByAppoin(struct Node* headNode, int posData)
//headNode只是一个传入的参数名，不是真的头节点 不要弄混
//posData是要删除的数据
{
  struct Node* posNode = headNode->next;
  struct Node* posNodeFront = headNode;
  //分别对于链表是否为空和posData是否存在进行判断
  if (posNode == nullptr)
  {
    cout << "链表为空 操作错误" << endl;
  }
  else
  {
    while (posNode->data != posData)
    {
      posNodeFront = posNode;
      posNode = posNodeFront->next;
      if (posNode == nullptr)
      {
        cout << "未找到要删除的数据" << endl;
        return;
      }
    }
    posNodeFront->next = posNode->next;
    //用free函数释放内存
    free(posNode);
  }
}
//遍历打印链表
void PrintList(struct Node* headNode)
{
  struct Node* pMove = headNode->next;
  while (pMove)
  //当pmove不为空指针时 持续遍历
  //这里就可以联系到创建节点时，为什么要将next初始化为空指针
  //巧妙 妙
  //while这里还能这么写 学到了 学到了
  {
    cout << pMove->data;
    pMove = pMove->next;
  }
  cout << endl;
}
int main()
{
  struct Node* list = createList();
  insertNodeByHead(list, 1);
  insertNodeByHead(list, 2);
  insertNodeByHead(list, 3);
  PrintList(list);
  return 0;
}

使用new

使用new的话，只需要在创建节点和插入节点那里修改一下就可以了

Node* createList()  
{  
 Node* headNode = new Node;  
 headNode->next = nullptr;  
 return headNode;  
}  
Node* createNode(int data)  
{  
 Node* newNode = new Node;  
 newNode->data = data;  
 newNode->next = nullptr;  
 return newNode;  
}

实际项目中可能会遇到的小问题

在编写如通讯录、图书馆信息管理系统的时候，data一般都是结构体，那么在输入的时候，就可能会遇到输入完数字，再输入字符串，

那么就存在需要清空缓冲区的问题

此时，我们可以用setbuf函数

使用格式如下：

setbuf(stdin,NULL);清空缓冲区函数

（在此只是介绍一下，作者也不会）

结语

算是初步把链表中的静态和动态链表了解和学习了一下，希望这篇文章对你有帮助，我们下篇文章见~~

【数据结构】链表的学习和介绍

前言