数据结构----链表头插中插尾插

news/2024/12/20 20:13:34/

一、链表的基本概念

链表是一种线性数据结构,它由一系列节点组成。每个节点包含两个主要部分:

  1. 数据域:用于存储数据元素,可以是任何类型的数据,如整数、字符、结构体等。
  2. 指针域:用于存储下一个节点(在单链表中)或前一个节点与下一个节点(在双链表中)的地址。

与数组不同,链表中的节点在内存中不是连续存储的。它们通过指针链接在一起,形成一个链状结构。这种非连续存储方式使得链表在插入和删除操作上具有一定的优势。

二、单链表

  1. 结构
    • 链表节点的定义(以C语言为例):
typedef struct ListNode {int data;       // 数据域,可以根据需要存储不同类型的数据struct ListNode *next; // 指针域,指向下一个节点
} ListNode;
  • 这里,data用于存储数据,next是一个指向同类型结构体的指针,用于指向下一个节点。
  1. 基本操作
    • 创建节点
      • 函数实现:
ListNode* createNode(int value) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (newNode == NULL) {// 内存分配失败处理return NULL;}newNode->data = value;newNode->next = NULL;return newNode;
}
 - 解释:- 首先使用`malloc`函数分配足够的内存来存储一个`ListNode`结构体。如果内存分配成功,将传入的值赋给新节点的数据域,并将指针域初始化为`NULL`,表示这是一个孤立的节点,目前没有下一个节点。最后返回新创建的节点。
  • 插入节点
    • 头插法
      • 函数实现:
ListNode* insertAtHead(ListNode* head, int value) {ListNode* newNode = createNode(value);newNode->next = head;return newNode;
}
   - 解释:- 首先调用`createNode`函数创建一个新节点。然后将新节点的`next`指针指向当前的头节点(如果`head`为`NULL`,则新节点成为唯一的节点)。最后,将新节点作为新的头节点返回。这意味着每次插入操作都会使新节点成为链表的第一个节点。- **尾插法**- 函数实现:
ListNode* insertAtTail(ListNode* head, int value) {ListNode* newNode = createNode(value);if (head == NULL) {return newNode;}ListNode* current = head;while (current->next!= NULL) {current = current->next;}current->next = newNode;return head;
}
   - 解释:- 同样先创建新节点。如果链表为空(`head`为`NULL`),则直接返回新节点作为头节点。如果链表不为空,通过一个循环找到链表的最后一个节点(即当前节点的`next`指针为`NULL`的节点)。找到后,将最后一个节点的`next`指针指向新节点,从而将新节点插入到链表的尾部。最后返回原头节点,因为尾插法不会改变头节点。- **中插法(在指定位置插入)**- 函数实现:
ListNode* insertAtPosition(ListNode* head, int value, int position) {if (position == 0) {return insertAtHead(head, value);}ListNode* newNode = createNode(value);ListNode* current = head;for (int i = 0; i < position - 1 && current!= NULL; i++) {current = current->next;}if (current == NULL) {return head;}newNode->next = current->next;current->next = newNode;return head;
}
   - 解释:- 首先判断要插入的位置是否为0,如果是,则调用头插法函数进行插入。如果不是0,先创建新节点。然后通过一个循环找到要插入位置的前一个节点(循环条件确保不会超出链表长度且能找到正确位置)。如果在遍历过程中发现当前节点为`NULL`,说明已经到达链表末尾但还没找到插入位置,此时直接返回原链表。找到插入位置的前一个节点后,将新节点的`next`指针指向当前节点的下一个节点,再将当前节点的`next`指针指向新节点,完成插入操作。最后返回原头节点。
  • 删除节点
    • 函数实现:
ListNode* deleteNode(ListNode* head, int target) {if (head == NULL) {return NULL;}if (head->data == target) {ListNode* temp = head;head = head->next;free(temp);return head;}ListNode* current = head;while (current->next!= NULL && current->next->data!= target) {current = current->next;}if (current->next!= NULL) {ListNode* temp = current->next;current->next = current->next->next;free(temp);}return head;
}
 - 解释:- 首先判断链表是否为空,如果为空则无法删除,直接返回`NULL`。如果头节点的数据就是要删除的数据,那么将头节点的下一个节点作为新的头节点,并释放原来的头节点,然后返回新头节点。如果头节点不是要删除的节点,通过循环找到要删除节点的前一个节点(通过判断当前节点的下一个节点的数据是否为目标数据)。找到后,将前一个节点的`next`指针指向要删除节点的下一个节点,然后释放要删除的节点,最后返回原头节点。
void traverseList(ListNode* head) {ListNode* current = head;while (current!= NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}
 - 解释:- 从链表的头节点开始,通过循环依次访问每个节点的数据域,并将其打印出来。每次循环将当前节点更新为下一个节点,直到当前节点为`NULL`,表示已经遍历完整个链表

在这里插入图片描述

三、双链表

  1. 结构
    • 链表节点的定义(以C语言为例):
typedef struct DoubleListNode {int data;struct DoubleListNode *prev;struct DoubleListNode *next;
} DoubleListNode;
  • 这里,data用于存储数据,prev是指向前一个节点的指针,next是指向后一个节点的指针。
  1. 基本操作
    • 创建节点
      • 函数实现:
DoubleListNode* createDoubleNode(int value) {DoubleListNode* newNode = (DoubleListNode*)malloc(sizeof(DoubleListNode));if (newNode == NULL) {return NULL;}newNode->data = value;newNode->prev = NULL;newNode->next = NULL;return newNode;
}
 - 解释:- 与单链表创建节点类似,使用`malloc`分配内存。成功分配后,将数据赋给新节点的数据域,并将`prev`和`next`指针都初始化为`NULL`,因为新创建的节点暂时没有前后连接的节点。最后返回新节点。
  • 插入节点
    • 例如,在双链表头部插入节点:
      • 函数实现:
DoubleListNode* insertAtHeadDouble(DoubleListNode* head, int value) {DoubleListNode* newNode = createDoubleNode(value);if (head == NULL) {return newNode;}newNode->next = head;head->prev = newNode;return newNode;
}
   - 解释:- 先创建新节点。如果链表为空,直接返回新节点作为头节点。如果链表不为空,将新节点的`next`指针指向当前头节点,同时将当前头节点的`prev`指针指向新节点,最后将新节点作为新的头节点返回。
  • 删除节点
    • 例如,删除双链表中值为target的节点:
      • 函数实现:
DoubleListNode* deleteDoubleNode(DoubleListNode* head, int target) {if (head == NULL) {return NULL;}if (head->data == target) {DoubleListNode* temp = head;if (head->next!= NULL) {head->next->prev = NULL;}head = head->next;free(temp);return head;}DoubleListNode* current = head;while (current->next!= NULL && current->next->data!= target) {current = current->next;}if (current->next!= NULL) {DoubleListNode* temp = current->next;if (temp->next!= NULL) {temp->next->prev = current;}current->next = temp->next;free(temp);}return head;
}
   - 解释:- 首先判断链表是否为空,为空则无法删除,返回`NULL`。如果头节点的数据是要删除的数据,判断头节点的下一个节点是否存在,如果存在则将其`prev`指针置为`NULL`,然后将头节点更新为下一个节点,并释放原来的头节点,最后返回新头节点。如果头节点不是要删除的节点,通过循环找到要删除节点的前一个节点(通过判断当前节点的下一个节点的数据是否为目标数据)。找到后,如果要删除的节点的下一个节点存在,则将其下一个节点的`prev`指针指向当前节点,然后将当前节点的`next`指针指向要删除节点的下一个节点,最后释放要删除的节点,返回原头节点。
  • 遍历链表
    • 例如,从头部开始向前遍历:
      • 函数实现:
void traverseDoubleListForward(DoubleListNode* head) {DoubleListNode* current = head;while (current!= NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}
   - 解释:- 与单链表的遍历类似,从头节点开始,通过循环依次访问每个节点的数据域并打印,每次将当前节点更新为下一个节点,直到当前节点为`NULL`。双链表还可以从尾部开始向后遍历,原理类似,只是使用`prev`指针。

四、循环链表

  1. 结构

    • 循环链表分为循环单链表和循环双链表
    • 循环单链表是最后一个节点的next指针指向头节点,形成一个环。
    • 循环双链表是最后一个节点的next指针指向头节点,头节点的prev指针指向最后一个节点,形成一个双向的环。
  2. 基本操作

    • 创建循环单链表
      • 例如,通过尾插法创建循环单链表
        • 函数实现:
ListNode* createCircularList(int values[], int size) {if (size == 0) {return NULL;}ListNode* head = createNode(values[0]);ListNode* current = head;for (int i = 1; i < size; i++) {ListNode* newNode = createNode(values[i]);current->next = newNode;current = newNode;}current->next = head;return head;
}
   - 解释:- 首先判断数组大小是否为0,如果是则返回`NULL`。如果不为0,先创建头节点,然后通过循环依次创建新节点并将其插入到链表尾部。最后将最后一个节点的`next`指针指向头节点,形成循环链表,并返回头节点。
  • 遍历循环单链表
    • 例如:
      • 函数实现:
void traverseCircularList(ListNode* head) {if (head == NULL) {return;}ListNode* current = head;do {printf("%d ", current->data);current = current->next;} while (current!= head);printf("\n");
}
   - 解释:- 首先判断链表是否为空,如果为空则直接返回。如果不为空,从头节点开始遍历,通过`do - while`循环依次访问每个节点的数据域并打印。循环条件是当前节点不等于头节点,因为是循环链表,当再次回到头节点时表示遍历结束。最后换行。

循环链表在一些特定的应用场景中非常有用,例如操作系统中的资源分配循环队列等。双链表在需要双向访问数据的场景下有优势,而单链表则在空间利用和简单操作场景下较为常用。在这里插入图片描述


http://www.ppmy.cn/news/1556719.html

相关文章

ilqr算法原理以及常见自动驾驶轨迹优化问题建模

1. ilqr ILQR算法是基于nominal trajectory ( x ~ , u ~ ) (\tilde{x}, \tilde{u}) (x~,u~)来优化求解的。ILQR是求解状态变量和控制变量的增量序列 ( δ x ∗ , δ u ∗ ) (\delta x^*, \delta u^*) (δx∗,δu∗)求解轨迹的局部最优值。 1.1 无约束轨迹优化问题形式 x ∗ ,…

如何制作搞笑配音视频?操作方法

在数字娱乐盛行的今天&#xff0c;搞笑配音视频凭借其独特的幽默感和创意&#xff0c;在网络上赢得了大量观众的喜爱。如果你也想尝试制作一部让人捧腹的搞笑配音视频&#xff0c;那么请跟随以下步骤&#xff0c;从撰写搞笑文案到视频配音剪辑&#xff0c;一步步打造你的作品。…

Spark-Streaming性能调优

一、概览 从集群上的Spark Streaming应用程序中获得最佳性能需要一些调整。一般会考虑2个因素&#xff1a; 通过高效利用集群资源&#xff0c;减少每批数据的流转时长设置正确的批量大小&#xff0c;以便批量数据可以在接收到时尽快处理&#xff08;即数据处理跟上数据摄取&a…

基于SpringBoot的嗨玩旅游网站:一站式旅游信息服务平台的设计与实现

摘要 在旅游需求日益增长的今天&#xff0c;一个全面、便捷的旅游信息服务平台显得尤为重要。嗨玩旅游网站正是为了满足这一需求而设计的在线平台&#xff0c;它提供了包括景点信息、旅游线路、商品信息、社区信息和活动推广等在内的丰富旅游目的地信息&#xff0c;旨在帮助用…

J8学习打卡笔记

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 Inception v1算法实战与解析 导入数据数据预处理划分数据集搭建模型训练模型正式训练结果可视化详细网络结构图个人总结 import os, PIL, random, pathlib imp…

航电系统组成架构详解!

一、航电系统的组成架构 航电系统通常由多个子系统组成&#xff0c;这些子系统协同工作&#xff0c;确保飞机的正常飞行和高效管理。以下是一些关键的子系统&#xff1a; 人机接口&#xff1a; 显示系统&#xff1a;包括平显&#xff08;HUD&#xff09;、头盔显示器&#x…

从源码分析swift GCD_DispatchGroup

前言&#xff1a; 最近在写需求的时候用到了DispatchGroup&#xff0c;一直没有深入去学习&#xff0c;既然遇到了那么就总结下吧。。。。 基本介绍&#xff1a; 任务组&#xff08;DispatchGroup&#xff09; DispatchGroup 可以将多个任务组合在一起并且监听它们的完成状态。…

samout llm解码 幻觉更低更稳定

这段代码定义了一个简单的对话生成系统&#xff0c;包括模型加载、词汇表加载、以及基于给定提示生成文本的功能。下面是对代码的解析&#xff1a; load_model_and_voc(device"cpu"): 该函数用于加载预训练的模型和词汇表&#xff08;vocabulary&#xff09;。它首先…