深入手撕链表

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。

相关文章

深入解析C++ 中std::map内存管理

深入解析C++ 中std::map内存管理

《深入解析C++中std::map内存管理》文章详解C++std::map内存管理,指出clear()仅删除元素可能不释放底层内存,建议用swap()与空map交换以彻底释放,针对指针类型需手动de... 目录1️、基本清空std::map2️、使用 swap 彻底释放内存3️、map 中存储指针类型的对象
阅读更多...
Java集合中的链表与结构详解

Java集合中的链表与结构详解

《Java集合中的链表与结构详解》链表是一种物理存储结构上非连续的存储结构,数据元素的逻辑顺序的通过链表中的引用链接次序实现,文章对比ArrayList与LinkedList的结构差异,详细讲解了链表... 目录一、链表概念与结构二、当向单链表的实现2.1 准备工作2.2 初始化链表2.3 打印数据、链表长
阅读更多...
深入理解go中interface机制

深入理解go中interface机制

《深入理解go中interface机制》本文主要介绍了深入理解go中interface机制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录前言interface使用类型判断总结前言go的interface是一组method的集合，不
阅读更多...
深入解析Java NIO在高并发场景下的性能优化实践指南

深入解析Java NIO在高并发场景下的性能优化实践指南

《深入解析JavaNIO在高并发场景下的性能优化实践指南》随着互联网业务不断演进,对高并发、低延时网络服务的需求日益增长,本文将深入解析JavaNIO在高并发场景下的性能优化方法,希望对大家有所帮助... 目录简介一、技术背景与应用场景二、核心原理深入分析2.1 Selector多路复用2.2 Buffer
阅读更多...
深入理解Go语言中二维切片的使用

深入理解Go语言中二维切片的使用

《深入理解Go语言中二维切片的使用》本文深入讲解了Go语言中二维切片的概念与应用,用于表示矩阵、表格等二维数据结构,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录引言二维切片的基本概念定义创建二维切片二维切片的操作访问元素修改元素遍历二维切片二维切片的动态调整追加行动态
阅读更多...
从原理到实战深入理解Java 断言assert

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言（assert）：从原理到实战引言：为什么需要断言？一、断言基础1.1 语
阅读更多...
C++链表的虚拟头节点实现细节及注意事项

C++链表的虚拟头节点实现细节及注意事项

《C++链表的虚拟头节点实现细节及注意事项》虚拟头节点是链表操作中极为实用的设计技巧,它通过在链表真实头部前添加一个特殊节点,有效简化边界条件处理,：本文主要介绍C++链表的虚拟头节点实现细节及注... 目录C++链表虚拟头节点（Dummy Head）一、虚拟头节点的本质与核心作用1. 定义2. 核心价值二
阅读更多...
一文深入详解Python的secrets模块

一文深入详解Python的secrets模块

《一文深入详解Python的secrets模块》在构建涉及用户身份认证、权限管理、加密通信等系统时,开发者最不能忽视的一个问题就是“安全性”,Python在3.6版本中引入了专门面向安全用途的secr... 目录引言一、背景与动机：为什么需要 secrets 模块？二、secrets 模块的核心功能1. 基
阅读更多...
Linux链表操作方式

Linux链表操作方式

《Linux链表操作方式》：本文主要介绍Linux链表操作方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、链表基础概念与内核链表优势二、内核链表结构与宏解析三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势六、典型应用场景七、调试技巧与
阅读更多...
Go学习记录之runtime包深入解析

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,：本文主要介绍Go学习记录之runtime包的... 目录前言：一、runtime包内容学习1、作用：① Goroutine和并发控制：② 垃圾回收：③ 栈和
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2