程序地带

数据结构——链表(无头单向非循环链表+ 带头双向循环链表)


之前学习链表一头雾水,这讲的什么,黑人问号。现在重新学完链表,不错不错,有意思。这篇文章主要来说两种链表,一是无头+单向+非循环链表增删查改,二是带头+双向+循环链表增删查。


1.链表概念及结构

链表是一种物理存储结构上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。


在这里插入图片描述在这里插入图片描述


2.链表的实现

2.1无头单向非循环链表


typedef int LDataType;
//定义结点
typedef struct ListNode
{
LDataType data;
struct ListNode* next;
}ListNode;
//定义链表
typedef struct list
{
//保存第一个结点的地址
ListNode* head;
}list;
//初始化链表
void initList(list* lst)
{
if (lst == NULL)
return;
lst->head = NULL;
}
//创建一个结点
listNode* createListNode(LDataType val)
{
listNode* newNode = (listNode*)malloc(sizeof(listNode));
newNode->data = val;
newNode->next = NULL;
return newNode;
}
//尾插
void listPushBack(list* lst, LDataType val)
{
if (lst == NULL)
return;
if (lst->head == NULL)
{
//创建第一个结点
lst->head = createListNode(val);
}
else
{
//先遍历找到最后一个结点
listNode* tail = lst->head;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = createListNode(val);
}
}
//尾删
void listPopBack(list* lst)
{
if (lst == NULL || lst->head == NULL)
return;
struct listNode* pre = NULL;
struct listNode* tail = lst->head;
while (tail->next != NULL)
{
pre = tail;
tail = tail->next;
}
free(tail);
if (pre == NULL)
{
//只有一个结点
lst->head = NULL;
}
else
{
pre->next = NULL;
}
}
//头插
void listPushFront(list* lst, LDataType val)
{
if (lst == NULL)
return;
struct listNode* newNode = createListNode(val);
newNode->next = lst->head;
lst->head = newNode;
}
//头删
void listPopFront(list* lst)
{
if (lst == NULL || lst->head == NULL)
return;
struct listNode* tail = lst->head->next;
free(lst->head);
lst->head = tail;
}
//在任意位置后插入
void listInsertAfter(listNode* node, LDataType val)
{
if (node == NULL)
return;
struct listNode* newNode = createListNode(val);
newNode->next = node->next;
node->next = newNode;
}
//在任意位置后删除
void listEraseAfter(listNode* node)
{
if (node == NULL || node->next == NULL)
return;
struct listNode* tail = node->next->next;
free(node->next);
node->next = tail;
}
//找到某值的位置
struct listNode* listFind(list* lst, LDataType val)
{
if (lst == NULL || lst->head == NULL)
return NULL;
struct listNode* tail = lst->head;
while (tail != NULL)
{
if (tail->data == val)
return tail;
tail = tail->next;
}
return NULL;
}
//销毁
void listDestory(list* lst)
{
if (lst == NULL || lst->head == NULL)
return;
struct listNode* tail = lst->head;
while (tail != NULL)
{
struct listNode* cur = tail->next;
free(tail);
tail = cur;
}
lst->head = NULL;
}
//打印
void listPrint(list* lst)
{
if (lst == NULL || lst->head == NULL)
return;
struct listNode* tail = lst->head;
while (tail != NULL)
{
printf("%d ", tail->data);
tail = tail->next;
}
}

2.2 带头双向循环链表


typedef int LDataType;
//双向结点
typedef struct ListNode
{
LDataType val;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
typedef struct List
{
struct ListNode* head;
}List;
//初始化链表
void initList(List* lst)
{
//创建头结点
lst->head = (struct ListNode*)malloc(sizeof(struct ListNode));
//创建循环结构
lst->head->next = lst->head;
lst->head->prev = lst->head;
}
//创建结点
struct ListNode* createNode(LDataType val)
{
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
//尾插
void listPushBack(List* lst,LDataType val)
{
if (lst == NULL)
return;
struct ListNode* cur = lst->head->prev;
struct ListNode* newNode = createNode(val);
cur->next = newNode;
newNode->prev = cur;
newNode->next = lst->head;
lst->head->prev = newNode;
}
//尾删
void listPopBack(List* lst)
{
if (lst == NULL || lst->head == lst->head->prev)
return;
struct ListNode* tail = lst->head->prev;
lst->head->prev = tail->prev;
tail->prev->next = lst->head;
free(tail);
}
//头插
void listPushFront(List* lst, LDataType val)
{
struct ListNode* next = lst->head->next;
struct ListNode* newNode = createNode(val);
lst->head->next = newNode;
newNode->prev = lst->head;
newNode->next = next;
next->prev = newNode;
}
//头删
void listPopFront(List* lst)
{
if (lst == NULL || lst->head->prev == lst->head)
return;
struct ListNode* next = lst->head->next;
struct ListNode* nextnext = next->next;
free(next);
lst->head->next = nextnext;
nextnext->prev = lst->head;
}
//在任意结点之前插入
void listInsert(ListNode* node, LDataType val)
{
struct ListNode* newNode = createNode(val);
struct ListNode* prev = node->prev;
prev->next = newNode;
newNode->prev = prev;
newNode->next = node;
node->prev = newNode;
}
//删除某一结点
void listErase(ListNode* node)
{
struct ListNode* next = node->next;
struct ListNode* prev = node->prev;
free(node);
prev->next = next;
next->prev = prev;
}
//遍历
struct ListNode* listFind(List* lst, LDataType val)
{
struct ListNode* cur = lst->head->next;
while (cur != lst->head)
{
if (cur->val == val)
return cur;
cur = cur->next;
}
return NULL;
}
//打印
void listPrint(List* lst)
{
struct ListNode* cur = lst->head->next;
while (cur != lst->head)
{
printf("%d ", cur->val);
cur = cur->next;
}
printf(" ");
}
//销毁
void listDestory(List* lst)
{
struct ListNode* cur = lst->head->next;
while (cur != lst->head)
{
struct ListNode* tmp = cur->next;
free(cur);
cur = tmp;
}
free(lst->head);
lst->head = NULL;
}

无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。


带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。


3.链表和顺序表的区别和联系

顺序表:


优点:空间连续、支持随机访问,空间利用率高


缺点: 1.中间或前面部分的插入、删除时间复杂度O(N) ; 2.增容的代价比较大。


链表


优点: 1.任意位置插入删除时间复杂度为O(1) 2.没有增容问题,插入一个开辟一个空间,适合频繁的插入和删除


缺点:以节点为单位存储,不支持随机访问,空间利用率低(内存碎片)


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45141313/article/details/112689106

随机推荐

CSS设置表头固定body滚动

tabletbody{display:block;height:500px;overflow-y:scroll;}tablethead,tbodytr{display:table;width:100%...

ak_88 阅读(794)

为什么要使用Maven私服仓库

原因:1.节约外网的带宽,一般私服都是搭建在公司内部局域网,用户需要下载依赖时,先去本地查找,本地没有在去私服获取,...

一片星空~ 阅读(225)

go modules使用

go modules使用

gomodules使用前言gomoudules是Go的一个包管理工具,官方提供的,还是比较靠谱的,最低Go版本要求1.11+。可以理解为Python的...

码农,星期八 阅读(189)

WinServer上安装MySQL

前言需要在一台Windows服务器上安装MySQL5.7版本,特此记录下安装过程软硬件环境腾讯云虚拟机4C16GWinServer2019Mysqlmysql-5.7.29-winx64...

shanzhi7 阅读(401)

各种命令的用法 sort uniq tr

命令sortuniqtrsortsort命令—以行为单位对内容进行排序,也可以根据不同的数据类型进行排序语法格式sort[选项]参数catfile|sort选项常用选项-f:...

朝花夕誓丶 阅读(861)

软件测试之登录测试详解

软件测试之登录测试详解

一、功能测试–登录功能性测试用例包括:1.什么都不输入,点击提交按钮,看提示信息。(非空检查)2.输入已注册的用户名和正确的密码&...

Gina61 阅读(159)

进制转换及回文判断

1、进制转换十进制转二进制、八进制、十六进制思想:辗转相除法//十进制转十六进制privatestaticvoiddecToHex(intnum){Stringhex="...

Naive Kyo 阅读(327)

java继承详解

java继承详解

继承的概念:继承是java面向对象编程技术的一块基石,因为它允许创建分等级层次的类。继承就是子类继承父类的特征和行为,使得子类对象(实例...

光阴不负卿 阅读(223)