[数据结构]——单链表超详细总结

带你走进链表的世界

目录：
一、线性表的概念
二、顺序表
三、链表
- 3.1 链表的概念
- 3.2 链表的分类
- 3.3 无头+单向+非循环链表的实现
- 3.4 带头+双向+循环链表的实现
四、顺序表和链表的区别和联系

链表是个优秀的结构，没有容量概念，可以在任意位置增加删除数据，这个博客，我准备花大量篇幅去总结链表（特别是单链表），同时也总结一下顺序表（顺序表和我们以前写的通讯录动态版类似，一般采用数组存储的方法，在数组上完成数据的增删查改）

一、线性表的概念

线性表的定义：由n个数据元素组成具有相同特性的有限序列。
常见的线性表：顺序表、链表、栈、队列、字符串等等。
线性表的概念：线性表在逻辑上是线性结构，也就是说它是一条直线，它的物理结构并不一定是连续的，线性表在物理上存储时，通常以数组和链表的形式存储。

二、顺序表

顺序表的定义：
顺序表是一段物理地址连续的存储单元，是一种用来依次存储数据的线性结构。
在这里插入图片描述
1.静态顺序表：使用定常数组存储元素

#define N 7//方便改变数组大小
typedef int SLDatatype;
typedef struct SLD
{
SLDatatype arr[N];//定长数组
size_t size;//有效数据的个数
}SeqList;//顺序表

2.动态顺序表：使用动态开辟的数组存储元素（空间不够就可以扩容）

typedef int SLDatatype;
typedef struct SLD
{
SLDatatype* p;//指向动态开辟的数组
size_t size;//有效数据的个数
size_t capicity;//表示容量空间的大小
}SeqList;//顺序表

三、链表

3.1 链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
注意:
链式结构在逻辑上是连续的，但是在物理上不一定连续。
现实中的节点一般都是从堆上申请出来的
从堆上申请的空间是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

3.2 链表的分类

链表的结构非常多，结合起来有8种：
1、单向或者双向
在这里插入图片描述
2、带头或者不带头

3、循环或者不循环

实际中常用的两种结构是：

无头单向非循环链表：
结构简单，一般不会单独存数据。其他数据的子结构，如哈希桶、图的领接表等等。
带头双向循环链表：
结构最复杂，一般可以单独存数据。实际中使用的链表数据结构，都是带头双向循环链表。

3.3 无头+单向+非循环链表的实现

头文件里的函数声明

// slist.h
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode** pplist);

下面将是各个函数的实现

// slist.c
#include "SList.h"
//动态申请一个结点
SListNode* BuySListNode(SLTDateType x)
{
//在堆上开辟一个存放指针的变量，并给它初始化SListNode* node = (SListNode*)malloc(sizeof(SListNode));node->data = x;node->next = NULL;return node;//返回指针
}
//单链表打印
void SListPrint(SListNode* plist)
{
//定义一个指针，指针指向头指针SListNode* cur = plist;//遍历指针，不是空就循环while (cur){printf("%d->", cur->data);cur = cur->next;}//cur指向空printf("NULL\n");
}
//单链表尾插一个数据
void SListPushBack(SListNode** pplist, SLTDateType x)
{
//开辟一个新结点SListNode* newnode = BuySListNode(x);//如果头指针指向的是空就让它指向这个新结点if (*pplist == NULL){*pplist = newnode;}else//如果头指针指向的不是空{//创建一个尾指针SListNode* tail = *pplist;//尾指针不在尾部，遍历单链表，让尾指针指向链表的最后结点while (tail->next != NULL){tail = tail->next;}
//把开辟的新结点尾插到尾指针结点的下一个结点tail->next = newnode;}
}
//单链表尾删
void SListPopBack(SListNode** pplist)
{
//定义两个指针SListNode* prev = NULL;//当前位置的指针SListNode* tail = *pplist;//尾结点的指针// 1.空、只有一个节点// 2.两个及以上的节点if (tail == NULL || tail->next == NULL){
//给空间释放free(tail);*pplist = NULL;}else{//遍历链表，找到尾指针while (tail->next){prev = tail;tail = tail->next;}free(tail);tail = NULL;
//让最后一个结点指向空prev->next = NULL;}
}//单链表头插法
void SListPushFront(SListNode** pplist, SLTDateType x)
{
//这个指针是空就报错assert(pplist);// 1.空// 2.非空SListNode* newnode = BuySListNode(x);if (*pplist == NULL)//pplist指针指向的是空{*pplist = newnode;}else{//在*pplist指针指向的那个结点前面头插一个结点newnode->next = *pplist;//*pplist指针重新指向头结点*pplist = newnode;}
}
//单链表头删
void SListPopFront(SListNode** pplist)
{// 1.空// 2.一个// 3.两个及以上SListNode* first = *pplist;//定义一个头指针，它为空就返回，if (first == NULL){return;}else if (first->next == NULL)//只有一个结点，就释放空间，然后置空{free(first);*pplist = NULL;}else{//两个以上结点SListNode* next = first->next;//把头指针的下一个结点位置存起来free(first);//释放头指针*pplist = next;//让首指针重新指向头指针}
}
 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur = plist;while (cur){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)//用单链表查找，找到值x的位置，返回的指针给pos
{assert(pos);SListNode* next = pos->next;//next指针存放pos之后的节点SListNode* newnode = BuySListNode(x);//开辟一个新结点pos->next = newnode;//在pos后面插入新开辟的结点newnode->next = next;//让新结点连接上next指向的那个结点
}
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)//用单链表查找，找到值x的位置，返回的指针给pos
{assert(pos);// pos next nextnextSListNode* next = pos->next;if (next != NULL){SListNode* nextnext = next->next;free(next);pos->next = nextnext;}
}
// 单链表的销毁
void SListDestroy(SListNode** pplist)
{SListNode* cur = *pplist;while (cur){*pplist = cur->next;free(cur);cur = *pplist;}
}

3.4 带头+双向+循环链表的实现

头文件里的函数声明

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;
//创建新结点ListNode* ListNodes(LTDataType x);
//双向链表初始化ListNode* ListInit();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
//求链表有多少数据
int listsize(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

函数的定义实现

// 创建新节点
ListNode* ListNodes(LTDataType x)
{ListNode* head = (ListNode*)malloc(sizeof(ListNode));if (head == NULL){perror("malloc fail");exit(-1);}head->data = x;head->next = NULL;head->prev = NULL;return head;
}
//链表初始化
ListNode* ListInit()
{ListNode* phead = ListNodes(-1);phead->next = phead;phead->prev = phead;return phead;
}
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = ListNodes(x);//创建一个新节点ListNode* tail = phead->prev;newnode->data = x;//双向链表尾插tail->next = newnode;newnode->next = phead;newnode->prev = tail;phead->prev = newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->next != NULL);ListNode* tail = phead->prev;ListNode* tailPrev = tail->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;
}
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{ListNode* next = phead->next;ListNode* newnode = ListNodes(x);phead->next = newnode;newnode->prev = phead;newnode->next = next;next->prev = newnode;
}
// 双向链表头删
void ListPopFront(ListNode* phead)
{assert(phead);assert(phead->next != NULL);ListNode* node = phead->next;phead->next = node->next;node->next->prev = phead;free(node);
}
//求链表有多少数据
int listsize(ListNode* phead)
{int  size = 0;assert(phead);ListNode* cur = phead->next;while (cur != phead){size++;cur = cur->next;}return size;
}
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{ListNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{ListNode* newnode = ListNodes(x);ListNode* prevnode = pos->prev;prevnode->next = newnode;newnode->prev = prevnode;newnode->next = pos;pos->prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* nodeprev = pos->prev;ListNode* nodenext = pos->next;free(pos);nodeprev->next = nodenext;nodenext->prev = nodeprev;
}
// 双向链表打印
void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}
}
// 双向链表销毁
void ListDestory(ListNode* phead)
{//断言指针指针不为NULLassert(phead);ListNode* cur = phead;//定义一个指针//断开循环链表phead->prev->next = NULL;while (cur){ListNode* Next = cur->next;free(cur);cur = Next;}
}

四、顺序表和链表的区别和联系

在这里插入图片描述
补充： 高速缓存利用率
先要对存储器的层次结构有一定了解
如图：

数据是存在内存中的，CPU要访问数据，它不会去内存直接访问数据。看数据在不在缓存，在缓存，数据就命中（cpu访问数据时，数据恰好在缓存里），不在缓存，访问不命中（cpu访问数据，不会把4个字节加载到缓存，它会把一长段的数据加载到缓存）