本文主要是介绍深入手撕链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
链表
- 分类
- 概念
- 单链表
- 增
- 尾插
- 头插
- 插入
- 删
- 尾删
- 头删
- 删除
- 查
- 完整实现
- 带头
- 不带头
- 双向链表
- 初始化
- 增
- 尾插
- 头插
- 插入
- 删
- 查
- 完整代码
- 数组
分类
概念
链表是一种物理存储结构上非连续
、非顺序
的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
单向与双向
带头与不带头
循环与不循环
单链表
增
尾插
带头
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题。
这篇关于深入手撕链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!