深入手撕链表

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。

相关文章

深入理解Apache Kafka(分布式流处理平台)

深入理解Apache Kafka(分布式流处理平台)

《深入理解ApacheKafka(分布式流处理平台)》ApacheKafka作为现代分布式系统中的核心中间件,为构建高吞吐量、低延迟的数据管道提供了强大支持,本文将深入探讨Kafka的核心概念、架构... 目录引言一、Apache Kafka概述1.1 什么是Kafka？1.2 Kafka的核心概念二、Ka
阅读更多...
Java并发编程必备之Synchronized关键字深入解析

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.
阅读更多...
一文带你深入了解Python中的GeneratorExit异常处理

一文带你深入了解Python中的GeneratorExit异常处理

《一文带你深入了解Python中的GeneratorExit异常处理》GeneratorExit是Python内置的异常,当生成器或协程被强制关闭时,Python解释器会向其发送这个异常,下面我们来看... 目录GeneratorExit：协程世界的死亡通知书什么是GeneratorExit实际中的问题案例
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
深入解析Spring TransactionTemplate 高级用法(示例代码)

深入解析Spring TransactionTemplate 高级用法(示例代码)

《深入解析SpringTransactionTemplate高级用法(示例代码)》TransactionTemplate是Spring框架中一个强大的工具,它允许开发者以编程方式控制事务,通过... 目录1. TransactionTemplate 的核心概念2. 核心接口和类3. TransactionT
阅读更多...
深入理解Apache Airflow 调度器(最新推荐)

深入理解Apache Airflow 调度器(最新推荐)

《深入理解ApacheAirflow调度器(最新推荐)》ApacheAirflow调度器是数据管道管理系统的关键组件,负责编排dag中任务的执行,通过理解调度器的角色和工作方式,正确配置调度器,并... 目录什么是Airflow 调度器？Airflow 调度器工作机制配置Airflow调度器调优及优化建议最
阅读更多...
深入理解C语言的void*

深入理解C语言的void*

《深入理解C语言的void*》本文主要介绍了C语言的void*,包括它的任意性、编译器对void*的类型检查以及需要显式类型转换的规则,具有一定的参考价值,感兴趣的可以了解一下... 目录一、void* 的类型任意性二、编译器对 void* 的类型检查三、需要显式类型转换占用的字节四、总结一、void* 的
阅读更多...
深入理解Redis大key的危害及解决方案

深入理解Redis大key的危害及解决方案

《深入理解Redis大key的危害及解决方案》本文主要介绍了深入理解Redis大key的危害及解决方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着... 目录一、背景二、什么是大key三、大key评价标准四、大key 产生的原因与场景五、大key影响与危
阅读更多...
深入理解C++ 空类大小

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中，规
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

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

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

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2