数据结构--单链表-阿里云开发者社区

一、引言

单链表是数据结构中最基础也是最重要的一种链式数据结构。它在内存中的元素不需要连续存储，每个元素通过指针连接到下一个元素。这种结构使得插入和删除操作变得高效，适合动态数据的管理。本文将全面介绍单链表的基本概念、结构、常见操作，并提供完整的实现代码。

二、单链表的基本概念与结构

1. 概念

单链表是一种链式存储的数据结构，由一系列节点（Node）组成。每个节点包含两部分：

数据域（Data）：存储实际的数据。

指针域（Next）：指向链表中的下一个节点。

链表的特点是节点不需要在内存中连续存储，这允许链表在插入和删除操作时具有更高的灵活性和效率。

2. 基本结构

单链表的基本结构如下：

typedef int DataType;
typedef struct ListNode
{
  DataType data;//数据域
  struct ListNode* next;//指针域,指向下一个节点
}LN;

三、单链表优缺点

1.优点

动态内存管理：节点在内存中不需要连续存储，支持动态扩展。

高效插入和删除：在链表中插入或删除节点的操作时间复杂度为 O(1)O(1)O(1)。

适应不同数据大小：可以处理动态变化的数据大小，无需事先定义固定大小。

2.缺点

额外空间开销：每个节点需要额外存储一个指针，增加内存开销。

访问效率低：访问链表中的第 nnn 个元素需要逐一遍历，时间复杂度为 O(n)O(n)O(n)。

不支持反向遍历：只能从头到尾遍历，不能直接反向遍历。

四、单链表的常见操作

单链表的操作包括节点的插入、删除、查找以及链表的遍历。下面是这些操作的详细说明及代码实现。

1.创建节点

//创建节点
LN* CreateNode(DataType x)
{
  LN* newnode = (LN*)malloc(sizeof(LN));
  if (newnode==NULL) {
    perror("malloc fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}

2.初始化(创建头节点)

// 初始化链表（创建头节点）
LN*ListInit() 
{
  LN* headnode = CreateNode(0); // 头节点值为0（或任何不使用的值）
  return headnode;
}

3.头插

//头插
void ListPushHead(LN* phead, DataType x)
{
  assert(phead);
  LN* newnode = CreateNode(x);
  newnode->next = phead->next;
  phead->next = newnode;
 
}

4.尾插

//尾插
void ListPushBack(LN* phead, DataType x)
{
  assert(phead);
  LN* newnode = CreateNode(x);
  LN* pcur = phead;
  while (pcur->next != NULL)
  {
    pcur = pcur->next;
  }
  pcur->next = newnode;
}

5.头删

//头删
void ListDelHead(LN* phead)
{
  assert(phead);
  if (phead->next == NULL)
  {
    printf("链表为空，无法进行删除操作！\n");
    return;
  }
  LN* temp = phead->next;
  phead->next = phead->next->next;
  free(temp);
}

6.尾删

//尾删
void ListDelBack(LN* phead)
{
  assert(phead);
  if (phead->next == NULL)
  {
    printf("链表为空，无法进行删除操作！\n");
    return;
  }
  LN* pcur = phead;
  while (pcur->next->next != NULL)
  {
    pcur = pcur->next;
  }
  free(pcur->next);
  pcur->next = NULL;
}

7.查找

//查找
LN* ListFind(LN* phead, DataType x)
{
  assert(phead);
  LN* pcur = phead->next;
  while (pcur)
  {
    if (pcur->data == x)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
  return NULL;
}

8.指定位置前插入

//指定位置前插入
void ListInsertFront(LN* phead, LN*pos,DataType x)
{
  assert(phead);
  LN* pcur = phead;
  if (pos==NULL)
  {
    printf("插入位置非法\n");
    return;
  }
  while (pcur->next != pos)
  {
    pcur=pcur->next;
  }
  LN* newnode = CreateNode(x);
  newnode->next = pos;
  pcur->next = newnode;
}

9.指定位置后插入

//指定位置后插入
void ListInsertBack(LN* pos, DataType x)
{
  if (pos == NULL)
  {
    printf("插入位置非法\n");
    return;
  }
  LN* newnode = CreateNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

10.指定位置删除

//指定位置节点删除
void ListErase(LN*phead,LN*pos)
{
  assert(phead);
  if (pos == NULL)
  {
    printf("删除位置非法\n");
    return;
  }
  if (phead->next == NULL)
  {
    printf("链表为空，无法进行删除操作！\n");
    return;
  }
  LN* pcur = phead;
  while (pcur->next!=pos)
  {
    pcur = pcur->next;
  }
  pcur->next = pos->next;
  free(pos);
}

11.打印

//打印链表
void ListPrint(LN* phead)
{
  assert(phead);
  LN* pcur = phead->next;//注意这里带头节点，所以打印数值从头节点的下一位打印
  while (pcur)
  {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("NULL\n");
}

12.销毁

//销毁
void ListDestory(LN** pphead)
{
  LN* pcur=*pphead;
  LN* temp = NULL;
  while (pcur)
  {
    temp = pcur->next; // 保存下一个节点的指针
    free(pcur);// 释放当前节点的内存
    pcur = temp;// 移动到下一个节点
  }
  // 将头指针置为 NULL，确保链表被正确销毁
  *pphead= NULL;
}

五、完整代码

1.List.h

该部分放顺序表结构定义、函数的声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
typedef struct ListNode
{
  DataType data;//数据域
  struct ListNode* next;//指针域,指向下一个节点
}LN;
//创建节点
LN* CreateNode(DataType x);
// 初始化链表（创建头节点）
LN* ListInit();
//尾插
void ListPushBack(LN* phead, DataType x);
//头插
void ListPushHead(LN* phead, DataType x);
//尾删
void ListDelBack(LN* phead);
//头删
void ListDelHead(LN* phead);
//打印链表
void ListPrint(LN *phead);
//查找
LN* ListFind(LN* phead, DataType x);
//指定位置前插入
void ListInsertFront(LN* phead, LN*pos,DataType x);
//指定位置后插入
void ListInsertBack(LN* pos, DataType x);
//指定位置节点删除
void ListErase(LN*phead,LN*pos);
//销毁
void ListDestory(LN**pphead);

2.List.c

该部分是函数功能的实现

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
//创建节点
LN* CreateNode(DataType x)
{
  LN* newnode = (LN*)malloc(sizeof(LN));
  if (newnode==NULL) {
    perror("malloc fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
// 初始化链表（创建头节点）
LN*ListInit() 
{
  LN* headnode = CreateNode(0); // 头节点值为0（或任何不使用的值）
  return headnode;
}
//尾插
void ListPushBack(LN* phead, DataType x)
{
  assert(phead);
  LN* newnode = CreateNode(x);
  LN* pcur = phead;
  while (pcur->next != NULL)
  {
    pcur = pcur->next;
  }
  pcur->next = newnode;
}
//头插
void ListPushHead(LN* phead, DataType x)
{
  assert(phead);
  LN* newnode = CreateNode(x);
  newnode->next = phead->next;
  phead->next = newnode;
 
}
//尾删
void ListDelBack(LN* phead)
{
  assert(phead);
  if (phead->next == NULL)
  {
    printf("链表为空，无法进行删除操作！\n");
    return;
  }
  LN* pcur = phead;
  while (pcur->next->next != NULL)
  {
    pcur = pcur->next;
  }
  free(pcur->next);
  pcur->next = NULL;
}
//头删
void ListDelHead(LN* phead)
{
  assert(phead);
  if (phead->next == NULL)
  {
    printf("链表为空，无法进行删除操作！\n");
    return;
  }
  LN* temp = phead->next;
  phead->next = phead->next->next;
  free(temp);
}
//打印链表
void ListPrint(LN* phead)
{
  assert(phead);
  LN* pcur = phead->next;//注意这里带头节点，所以打印数值从头节点的下一位打印
  while (pcur)
  {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("NULL\n");
}
//查找
LN* ListFind(LN* phead, DataType x)
{
  assert(phead);
  LN* pcur = phead->next;
  while (pcur)
  {
    if (pcur->data == x)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
  return NULL;
}
//指定位置前插入
void ListInsertFront(LN* phead, LN*pos,DataType x)
{
  assert(phead);
  LN* pcur = phead;
  if (pos==NULL)
  {
    printf("插入位置非法\n");
    return;
  }
  while (pcur->next != pos)
  {
    pcur=pcur->next;
  }
  LN* newnode = CreateNode(x);
  newnode->next = pos;
  pcur->next = newnode;
}
//指定位置后插入
void ListInsertBack(LN* pos, DataType x)
{
  if (pos == NULL)
  {
    printf("插入位置非法\n");
    return;
  }
  LN* newnode = CreateNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
//指定位置节点删除
void ListErase(LN*phead,LN*pos)
{
  assert(phead);
  if (pos == NULL)
  {
    printf("删除位置非法\n");
    return;
  }
  if (phead->next == NULL)
  {
    printf("链表为空，无法进行删除操作！\n");
    return;
  }
  LN* pcur = phead;
  while (pcur->next!=pos)
  {
    pcur = pcur->next;
  }
  pcur->next = pos->next;
  free(pos);
}
//销毁
void ListDestory(LN** pphead)
{
  LN* pcur=*pphead;
  LN* temp = NULL;
  while (pcur)
  {
    temp = pcur->next; // 保存下一个节点的指针
    free(pcur);// 释放当前节点的内存
    pcur = temp;// 移动到下一个节点
  }
  // 将头指针置为 NULL，确保链表被正确销毁
  *pphead= NULL;
}

3.test.c

该部分用来测试我们写的函数(函数的调用)

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void test1()
{
  LN* phead = ListInit();//创建头节点，头指针指向头节点 
  ListPushHead(phead, 1);
  ListPushHead(phead, 2);
  ListPushHead(phead, 3);
  //ListDelBack(phead);
  //ListDelHead(phead);
  //测试查找
  LN * find = ListFind(phead,2);
  /*if (find == NULL)
  {
    printf("没有找到!\n");
  }
  else
  {
    printf("找到了!\n");
  }*/
  //ListInsertFront(phead, find, 99);
  //ListInsertBack(find,88);
  //ListErase(phead, find);
  ListPrint(phead);
  //ListDestory(&phead);
}
int main()
{
  test1();
  return 0;
}

六、总结

单链表是一种简单而强大的数据结构，适用于动态数据存储和管理。通过本文，我们介绍了单链表的基本概念、常见操作及其实现。掌握单链表的操作可以帮助我们更好地解决实际编程问题，特别是在需要频繁插入和删除操作的场景中。

希望这篇博客对你理解和使用单链表有所帮助。如果你有任何问题或想进一步了解更多高级用法，请随时留言讨论！

数据结构--单链表