深入手撕链表

2024-09-09 08:28
文章标签 链表 深入

本文主要是介绍深入手撕链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

链表

  • 分类
  • 概念
  • 单链表
      • 尾插
      • 头插
      • 插入
      • 尾删
      • 头删
      • 删除
    • 完整实现
      • 带头
      • 不带头
  • 双向链表
    • 初始化
      • 尾插
      • 头插
      • 插入
    • 完整代码
  • 数组

分类

链表
单链表
双向链表
种类
循环与非循环
带头与不带头
STL
list

概念

链表是一种物理存储结构上非连续非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
在这里插入图片描述
单向与双向
在这里插入图片描述
带头与不带头
在这里插入图片描述
循环与不循环
在这里插入图片描述

单链表

尾插

带头

void SLPushBack(SLNode* head, SLNDataType x) {SLNode* newnode = CreateNode(x);SLNode* tail = head;while (tail->next != NULL) {tail = tail->next;}tail->next = newnode;}

不带头

void SLPushBack(SLNode** head, SLNDataType x) {assert(head);//头节点的地址不可能为空SLNode* newnode = CreateNode(x);if (*head == NULL) {//没有节点*head = newnode;}else {//找尾SLNode* tail = *head;while (tail->next != NULL) {tail = tail->next;}tail->next = newnode;}}

头插

带头

void SLPushPront(SLNode* head, SLNDataType x) {SLNode* newnode = CreateNode(x);newnode->next = head->next;head->next = newnode;
}

不带头

void SLPushPront(SLNode** head, SLNDataType x) {assert(head);SLNode* newnode = CreateNode(x);newnode->next = *head;*head = newnode;
}

插入

带头

void SLInsert(SLNode* head, SLNode* pos, SLNDataType x) {assert(head);assert(pos);SLNode* prev = head;while (prev->next != pos) {prev = prev->next;}SLNode* newnode = CreateNode(x);newnode->next = pos;prev->next = newnode;
}

不带头

void SLInsert(SLNode** head, SLNode* pos, SLNDataType x) {assert(head);assert(pos);assert(*head);if (*head == pos) {//头插SLPushPront(head, x);}else{SListNode* prev = *head;while (prev->next != pos) {prev = prev->next;}SListNode* newnode = CreateNode(x);newnode->next =pos;prev->next = newnode;}}

尾删

带头

void SLPopBack(SLNode* head) {assert(head);assert(head->next);SLNode* prev = head;while (prev->next->next != NULL) {prev = prev->next;}free(prev->next);prev->next = NULL;
}

不带头

void SLPopBack(SLNode** head) {assert(head);assert(*head);if ((*head)->next == NULL) {free(*head);*head = NULL;}else {SLNode* prev = *head;while (prev->next->next != NULL) {prev = prev->next;}free(prev->next);prev->next = NULL;}
}

头删

带头

void SLPopFront(SLNode* head) {assert(head);assert(head->next);SLNode* tmp = head->next;head->next = head->next->next;free(tmp);
}

不带头

void SLPopFront(SLNode** head) {assert(head);assert(*head);SLNode* tmp = *head;*head = (*head)->next;free(tmp);
}

删除

带头

void SLErase(SLNode* head, SLNode* pos) {assert(head);assert(head->next);assert(pos);SLNode* prev = head;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}

不带头

void SLErase(SLNode** head, SLNode* pos) {assert(head);assert(pos);if (*head == pos) {SLPopFront(head);}else {SLNode* prev = *head;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

带头

SLNode* SLFind(SLNode* head, SLNDataType x) {SLNode* cur = head->next;while (cur) {if (cur->val == x) {return cur;}cur = cur->next;}return NULL;
}

不带头

SLNode* CreateNode(SLNDataType x) {SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL) {perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;return newnode;
}

完整实现

带头

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLNDataType;typedef struct SListNode {SLNDataType val;struct SListNode* next;
}SLNode;void SLPrint(SLNode* head);void SLPushBack(SLNode* head, SLNDataType x);
void SLPushPront(SLNode* head, SLNDataType x);SLNode* SLFind(SLNode* head, SLNDataType x);void SLInsert(SLNode* head, SLNode* pos, SLNDataType x);void SLPopBack(SLNode* head);
void SLPopFront(SLNode* head);
void SLErase(SLNode* head, SLNode* pos);void SLDestroy(SLNode* head);
#include"SList.h"void SLPrint(SLNode* head) {while (head) {printf("%d -> ", head->val);head = head->next;}printf("NULL\n");
}SLNode* CreateNode(SLNDataType x) {SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL) {perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;return newnode;
}void SLPushBack(SLNode* head, SLNDataType x) {SLNode* newnode = CreateNode(x);SLNode* tail = head;while (tail->next != NULL) {tail = tail->next;}tail->next = newnode;}void SLPushPront(SLNode* head, SLNDataType x) {SLNode* newnode = CreateNode(x);newnode->next = head->next;head->next = newnode;
}SLNode* SLFind(SLNode* head, SLNDataType x) {SLNode* cur = head->next;while (cur) {if (cur->val == x) {return cur;}cur = cur->next;}return NULL;
}void SLInsert(SLNode* head, SLNode* pos, SLNDataType x) {assert(head);assert(pos);SLNode* prev = head;while (prev->next != pos) {prev = prev->next;}SLNode* newnode = CreateNode(x);newnode->next = pos;prev->next = newnode;
}void SLPopBack(SLNode* head) {assert(head);assert(head->next);SLNode* prev = head;while (prev->next->next != NULL) {prev = prev->next;}free(prev->next);prev->next = NULL;
}void SLPopFront(SLNode* head) {assert(head);assert(head->next);SLNode* tmp = head->next;head->next = head->next->next;free(tmp);tmp = NULL;
}void SLErase(SLNode* head, SLNode* pos) {assert(head);assert(head->next);assert(pos);SLNode* prev = head;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}void SLDestroy(SLNode* head) {assert(head);SLNode* cur = head->next;while(cur){SLNode* tmp = cur->next;free(cur);cur = tmp;}head->next = NULL;
}
#include"SList.h"void test1() {SListNode* plist = (SListNode*)malloc(sizeof(SListNode));plist->val = 0;plist->next = NULL;SLPushBack(plist, 1);SLPushBack(plist, 3);SLPushBack(plist, 1);SLPushBack(plist, 4);SLPrint(plist -> next);SLPushPront(plist, 0);SLPushPront(plist, 2);SLPushPront(plist, 5);SLPrint(plist->next);
}void test2() {SListNode* plist = (SListNode*)malloc(sizeof(SListNode));plist->val = 0;plist->next = NULL;SLPushBack(plist, 1);SLPushBack(plist, 3);SLPushBack(plist, 1);SLPushBack(plist, 4);SLPrint(plist->next);SLPushPront(plist, 0);SLPushPront(plist, 2);SLPushPront(plist, 5);SLPrint(plist->next);SLInsert(plist, SLFind(plist->next, 5), 520);SLPrint(plist->next);
}void test3() {SListNode* plist = (SListNode*)malloc(sizeof(SListNode));plist->val = 0;plist->next = NULL;SLPushBack(plist, 1);SLPopBack(plist);SLPrint(plist->next);
}void test4() {SListNode* plist = (SListNode*)malloc(sizeof(SListNode));plist->val = 0;plist->next = NULL;SLPushBack(plist, 1);SLPushBack(plist, 3);SLPushBack(plist, 1);SLPushBack(plist, 4);SLPrint(plist->next);SLPushPront(plist, 0);SLPushPront(plist, 2);SLPushPront(plist, 5);SLPrint(plist->next);SLPopFront(plist);SLPopFront(plist);SLPopFront(plist);SLPrint(plist->next);
}void test5() {SListNode* plist = (SListNode*)malloc(sizeof(SListNode));plist->val = 0;plist->next = NULL;SLPushBack(plist, 1);SLPushBack(plist, 3);SLPushBack(plist, 1);SLPushBack(plist, 4);SLPrint(plist->next);SLPushPront(plist, 0);SLPushPront(plist, 2);SLPushPront(plist, 5);SLPrint(plist->next);SLErase(plist, SLFind(plist, 0));SLPrint(plist->next);
}int main() {test5();return 0;
}

不带头

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLNDataType;typedef struct SListNode {SLNDataType val;struct SListNode* next;
}SLNode;void SLPrint(SLNode* head);void SLPushBack(SLNode** head, SLNDataType x);//尾插
void SLPushPront(SLNode** head, SLNDataType x);//头插
void SLInsert(SLNode** head, SLNode* pos, SLNDataType x); //插入SLNode* SLFind(SLNode* head,SLNDataType x);//查找void SLPopBack(SLNode** head);//尾删
void SLPopFront(SLNode** head);//头删
void SLErase(SLNode** head, SLNode* pos);//删除void SLInsertAfter(SLNode* pos, SLNDataType x);//往后插
void SLEraseAfter(SLNode* pos);//往后删void SLDestroy(SLNode** head);//清除
#include"SList.h"void SLPrint(SLNode* head) {while (head) {printf("%d -> ", head->val);head = head->next;}printf("NULL\n");
}SLNode* CreateNode(SLNDataType x) {SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL) {perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;return newnode;
}void SLPushBack(SLNode** head, SLNDataType x) {assert(head);//头节点的地址不可能为空SLNode* newnode = CreateNode(x);if (*head == NULL) {//没有节点*head = newnode;}else {//找尾SLNode* tail = *head;while (tail->next != NULL) {tail = tail->next;}tail->next = newnode;}}void SLPushPront(SLNode** head, SLNDataType x) {assert(head);SLNode* newnode = CreateNode(x);newnode->next = *head;*head = newnode;
}SLNode* SLFind(SLNode* head, SLNDataType x) {while (head) {if (head->val == x) {return head;}head = head->next;}return NULL;
}void SLInsert(SLNode** head, SLNode* pos, SLNDataType x) {assert(head);assert(pos);assert(*head);if (*head == pos) {//头插SLPushPront(head, x);}else{SListNode* prev = *head;while (prev->next != pos) {prev = prev->next;}SListNode* newnode = CreateNode(x);newnode->next =pos;prev->next = newnode;}}void SLPopBack(SLNode** head) {assert(head);assert(*head);if ((*head)->next == NULL) {free(*head);*head = NULL;}else {SLNode* prev = *head;while (prev->next->next != NULL) {prev = prev->next;}free(prev->next);prev->next = NULL;}
}void SLPopFront(SLNode** head) {assert(head);assert(*head);SLNode* tmp = *head;*head = (*head)->next;free(tmp);
}void SLErase(SLNode** head, SLNode* pos) {assert(head);assert(pos);if (*head == pos) {SLPopFront(head);}else {SLNode* prev = *head;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}void SLInsertAfter(SLNode* pos, SLNDataType x) {assert(pos);SLNode* newnode = CreateNode(x);newnode->next = pos->next;pos->next = newnode;
}void SLEraseAfter(SLNode* pos) {assert(pos);assert(pos->next);SLNode* cur = pos->next;pos->next = cur->next;free(cur);cur = NULL;
}void SLDestroy(SLNode** head) {assert(head);SLNode* cur = *head;while (cur) {SLNode* next = cur->next;free(cur);cur = next;}*head = NULL;
}
#include"SList.h"void test1() {SListNode* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 3);SLPushBack(&plist, 1);SLPushBack(&plist, 4);SLPrint(plist);SLPushPront(&plist, 0);SLPushPront(&plist, 2);SLPushPront(&plist, 5);SLPrint(plist);
}void test2() {SListNode* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 3);SLPushBack(&plist, 1);SLPushBack(&plist, 4);SLPrint(plist);SLPushPront(&plist, 0);SLPushPront(&plist, 2);SLPushPront(&plist, 5);SLPrint(plist);SLInsert(&plist, SLFind(plist, 2), 10);SLPrint(plist);
}void test3() {SListNode* plist = NULL;SLPushBack(&plist, 1);SLPopBack(&plist);SLPrint(plist);
}void test4() {SListNode* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 3);SLPushBack(&plist, 1);SLPushBack(&plist, 4);SLPrint(plist);SLPushPront(&plist, 0);SLPushPront(&plist, 2);SLPushPront(&plist, 5);SLPrint(plist);SLErase(&plist, SLFind(plist, 0));SLPrint(plist);
}int main() {test4();return 0;
}

双向链表

在这里插入图片描述

初始化

DLNode* DLInit() {DLNode* head = CreatDLNode(-1);head->next = head;head->prev = head;return head;
}

尾插

void DLPushBack(DLNode* head, DLTDataType x) {assert(head);DLNode* tail = head->prev;DLNode* newnode = CreatDLNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = head;head->prev = newnode;
}

头插

void DLPushPront(DLNode* head, DLTDataType x) {assert(head);DLNode* tail = head->next;DLNode* newnode = CreatDLNode(x);head->next = newnode;newnode->prev = head;newnode->next = tail;tail->prev = newnode;
}

插入

void DLInsert(DLNode* pos, DLTDataType x) {assert(pos);DLNode* tail = pos->prev;DLNode* newnode = CreatDLNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = pos;pos->prev = newnode;
}

void DLErase(DLNode* pos) {assert(pos);assert(pos != head);DLNode* tail = pos->prev;tail->next = pos->next;pos->next->prev = tail;free(pos);
}

DLNode* DLFind(DLNode* head, DLTDataType x) {assert(head);DLNode* cur = head->next;while (cur != head) {if (cur->val == x) {return cur;}cur = cur->next;}return NULL;
}

完整代码

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int DLTDataType;typedef struct DList{struct DList* next;struct DList* prev;DLTDataType val;
}DLNode;DLNode* DLInit();void DLPrint(DLNode* head);void DLPushBack(DLNode* head, DLTDataType x);
void DLPushPront(DLNode* head, DLTDataType x);
void DLInsert(DLNode* pos, DLTDataType x);DLNode* DLFind(DLNode* head, DLTDataType x);void DLPopBack(DLNode* head);
void DLPopFront(DLNode* head);
void DLErase(DLNode* pos);void DLDestroy(DLNode* head);
#include"DList.h"DLNode* CreatDLNode(DLTDataType x) {DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));if (newnode == NULL) {perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}DLNode* DLInit() {DLNode* head = CreatDLNode(-1);head->next = head;head->prev = head;return head;
}void DLPrint(DLNode* head) {assert(head);printf("head <=> ");DLNode* cur = head->next;while (cur != head) {printf("%d <=> ", cur->val);cur = cur->next;}printf("\n");
}void DLPushBack(DLNode* head, DLTDataType x) {assert(head);DLNode* tail = head->prev;DLNode* newnode = CreatDLNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = head;head->prev = newnode;
}void DLPushPront(DLNode* head, DLTDataType x) {assert(head);DLNode* tail = head->next;DLNode* newnode = CreatDLNode(x);head->next = newnode;newnode->prev = head;newnode->next = tail;tail->prev = newnode;
}DLNode* DLFind(DLNode* head, DLTDataType x) {assert(head);DLNode* cur = head->next;while (cur != head) {if (cur->val == x) {return cur;}cur = cur->next;}return NULL;
}void DLInsert(DLNode* pos, DLTDataType x) {assert(pos);DLNode* tail = pos->prev;DLNode* newnode = CreatDLNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = pos;pos->prev = newnode;
}void DLPopBack(DLNode* head) {assert(head);assert(head->next != head);DLErase(head->prev);
}void DLPopFront(DLNode* head) {assert(head);assert(head->next != head);DLErase(head->next);
}void DLErase(DLNode* pos) {assert(pos);DLNode* tail = pos->prev;tail->next = pos->next;pos->next->prev = tail;free(pos);
}void DLDestroy(DLNode* head) {assert(head);DLNode* cur = head->next;while (cur != head) {DLNode* tail = cur->next;free(cur);cur = tail;}free(head);
}
#include"DList.h"void test1() {DLNode* head = DLInit();DLPushBack(head, 1);DLPushBack(head, 3);DLPushBack(head, 1);DLPushBack(head, 4);DLPushPront(head, 0);DLPushPront(head, 2);DLPushPront(head, 5);DLPrint(head);
}void test2() {DLNode* head = DLInit();DLPushBack(head, 1);DLPushBack(head, 3);DLPushBack(head, 1);DLPushBack(head, 4);DLPushPront(head, 0);DLPushPront(head, 2);DLPushPront(head, 5);DLPrint(head);DLInsert(DLFind(head, 2), 3);DLPrint(head);
}void test3() {DLNode* head = DLInit();DLPushBack(head, 1);DLPushBack(head, 3);DLPushBack(head, 1);DLPushBack(head, 4);DLPushPront(head, 0);DLPushPront(head, 2);DLPushPront(head, 5);DLPrint(head);DLInsert(DLFind(head, 2), 3);DLPrint(head);DLErase(DLFind(head, 3));DLPopBack(head);DLPopFront(head);DLPrint(head);
}int main() {test3();return 0;
}

数组

接下来我们用数组简单实现一下链表,可以用于一些oj题。


这篇关于深入手撕链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1150639

相关文章

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

深入理解RxJava:响应式编程的现代方式

在当今的软件开发世界中,异步编程和事件驱动的架构变得越来越重要。RxJava,作为响应式编程(Reactive Programming)的一个流行库,为Java和Android开发者提供了一种强大的方式来处理异步任务和事件流。本文将深入探讨RxJava的核心概念、优势以及如何在实际项目中应用它。 文章目录 💯 什么是RxJava?💯 响应式编程的优势💯 RxJava的核心概念

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

深入理解数据库的 4NF:多值依赖与消除数据异常

在数据库设计中, "范式" 是一个常常被提到的重要概念。许多初学者在学习数据库设计时,经常听到第一范式(1NF)、第二范式(2NF)、第三范式(3NF)以及 BCNF(Boyce-Codd范式)。这些范式都旨在通过消除数据冗余和异常来优化数据库结构。然而,当我们谈到 4NF(第四范式)时,事情变得更加复杂。本文将带你深入了解 多值依赖 和 4NF,帮助你在数据库设计中消除更高级别的异常。 什么是

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

深入解析秒杀业务中的核心问题 —— 从并发控制到事务管理

深入解析秒杀业务中的核心问题 —— 从并发控制到事务管理 秒杀系统是应对高并发、高压力下的典型业务场景,涉及到并发控制、库存管理、事务管理等多个关键技术点。本文将深入剖析秒杀商品业务中常见的几个核心问题,包括 AOP 事务管理、同步锁机制、乐观锁、CAS 操作,以及用户限购策略。通过这些技术的结合,确保秒杀系统在高并发场景下的稳定性和一致性。 1. AOP 代理对象与事务管理 在秒杀商品