双向链表的讲解与实现

一、双向链表的结构

在这里插入图片描述

带头”跟前面我们说的“头节点”是两个概念,带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨的”。

“哨兵位”存在的意义:遍历循环链表避免死循环。

二、顺序表和双向链表的优缺点分析

不同点 顺序表 链表
存储空间上 物理上一定连续 逻辑上连续,但物理上不一定连续
随机访问(时间复杂度) 支持 O(1) 不支持且为 O(N)
任意位置插入或者删除元素 可能需要移动元素,效率为 O(N) 只需修改指针指向
插入 动态顺序表,空间不够时需要扩容 没有容量的概念
应用场景 元素高效存储 + 频繁访问 任意位置插入和频繁删除

三、双向链表的实现(使用VS2022)

这里用VS2022的C语言来实现双向链表。

这个结构虽然复杂,但是其中特殊的结构会带来很多优势,代码实现很简单。

双向链表常用的增删改查等接口包括:

1.初始化、销毁、打印、判空

2.尾插尾删、头插头删

3.查找、指定插入、指定删除

在 List.h 中:

#pragma once

#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int LTDataType;

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
} ListNode, * pListNode;

// 初始化、销毁、打印、判空
pListNode ListInit();

void ListDestroy(pListNode phead);

void ListPrint(pListNode phead);

bool ListEmpty(pListNode phead);

// 尾插尾删、头插头删
void ListPushBack(pListNode phead, LTDataType x);

void ListPopBack(pListNode phead);

void ListPushFront(pListNode phead, LTDataType x);

void ListPopFront(pListNode phead);

// 查找、指定插入、指定删除
pListNode ListFind(pListNode phead, LTDataType x);

void ListInsert(pListNode pos, LTDataType x);

void ListErase(pListNode pos);

1.初始化、销毁、打印、判空

// 创建节点封装成函数
pListNode CreateNode(LTDataType x)
{
	pListNode temp = (pListNode)malloc(sizeof(ListNode));
	if (temp == NULL)
	{
		perror("malloc failed");
		return NULL;
	}
	temp->data = x;
	temp->prev = NULL;
	temp->next = NULL;

	return temp;
}

// 初始化、销毁、打印、判空
pListNode ListInit()
{
	pListNode temp = CreateNode(-1);
	temp->next = temp;
	temp->prev = temp;

	return temp;
}

void ListDestroy(pListNode phead)
{
	assert(phead);

	pListNode temp = phead->next;
	while (temp != phead)
	{
		pListNode dest = temp->next;
		free(temp);
		temp = dest;
	}
	free(temp);
	temp = phead = NULL;
}

void ListPrint(pListNode phead)
{
	assert(phead);

	for (pListNode temp = phead->next; temp != phead; temp = temp->next)
	{
		printf("%d ", temp->data);
	}
	printf("\n");
}


bool ListEmpty(pListNode phead)
{
	assert(phead);

	return phead == phead->next;
}

2.尾插尾删、头插头删

// 尾插尾删、头插头删
void ListPushBack(pListNode phead, LTDataType x)
{
	assert(phead);

	pListNode tail = phead->prev;
	pListNode newNode = CreateNode(x);

	newNode->prev = tail;
	newNode->next = phead;
	tail->next = newNode;
	phead->prev = newNode;
}

void ListPopBack(pListNode phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	pListNode tail = phead->prev;

	phead->prev = tail->prev;
	tail->prev->next = phead;
	free(tail);
	tail = NULL;
}

void ListPushFront(pListNode phead, LTDataType x)
{
	assert(phead);

	pListNode newNode = CreateNode(x);
	pListNode first = phead->next;

	newNode->next = first;
	newNode->prev = phead;
	first->prev = newNode;
	phead->next = newNode;
}

void ListPopFront(pListNode phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	pListNode first = phead->next;

	phead->next = first->next;
	first->next->prev = phead;
	free(first);
	first = NULL;
}

3.查找、指定插入、指定删除

// 查找、指定插入、指定删除
pListNode ListFind(pListNode phead, LTDataType x)
{
	assert(phead);

	for (pListNode find = phead->next; find != phead; find = find->next)
	{
		if (find->data == x)
		{
			return find;
		}
	}
	return NULL;
}

void ListInsert(pListNode pos, LTDataType x)
{
	assert(pos);

	pListNode newNode = CreateNode(x);
	pListNode prev = pos->prev;

	newNode->next = pos;
	newNode->prev = prev;
	pos->prev = newNode;
	prev->next = newNode;
}

void ListErase(pListNode pos)
{
	assert(pos);			// 非空时pos不能传入哨兵位,不然删除后会丢失整个链表
	assert(!ListEmpty(pos));

	pListNode prev = pos->prev;
	pListNode next = pos->next;

	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}

四、代码优化

指定插入 包含 尾插头插,指定删除 包含 尾删头删。可以复用两者,提高代码复用率

// 尾插尾删、头插头删
void ListPushBack(pListNode phead, LTDataType x)
{
	assert(phead);

	ListInsert(phead, x);
}

void ListPopBack(pListNode phead)
{
	assert(phead);

	ListErase(phead->prev);
}

void ListPushFront(pListNode phead, LTDataType x)
{
	assert(phead);

	ListInsert(phead->next, x);
}

void ListPopFront(pListNode phead)
{
	assert(phead);

	ListErase(phead->next);
}

五、完整 List.c 源代码

#include "List.h"

// 创建节点封装成函数
pListNode CreateNode(LTDataType x)
{
	pListNode temp = (pListNode)malloc(sizeof(ListNode));
	if (temp == NULL)
	{
		perror("malloc failed");
		return NULL;
	}
	temp->data = x;
	temp->prev = NULL;
	temp->next = NULL;

	return temp;
}

// 初始化、销毁、打印
pListNode ListInit()
{
	pListNode temp = CreateNode(-1);
	temp->next = temp;
	temp->prev = temp;

	return temp;
}

void ListDestroy(pListNode phead)
{
	assert(phead);

	pListNode temp = phead->next;
	while (temp != phead)
	{
		pListNode dest = temp->next;
		free(temp);
		temp = dest;
	}
	free(temp);
	temp = phead = NULL;
}

void ListPrint(pListNode phead)
{
	assert(phead);

	for (pListNode temp = phead->next; temp != phead; temp = temp->next)
	{
		printf("%d ", temp->data);
	}
	printf("\n");
}

bool ListEmpty(pListNode phead)
{
	assert(phead);

	return phead == phead->next;
}

// 尾插尾删、头插头删
void ListPushBack(pListNode phead, LTDataType x)
{
	assert(phead);

	ListInsert(phead, x);
}

void ListPopBack(pListNode phead)
{
	assert(phead);

	ListErase(phead->prev);
}

void ListPushFront(pListNode phead, LTDataType x)
{
	assert(phead);

	ListInsert(phead->next, x);
}

void ListPopFront(pListNode phead)
{
	assert(phead);

	ListErase(phead->next);
}

// 查找、指定插入、指定删除
pListNode ListFind(pListNode phead, LTDataType x)
{
	assert(phead);

	for (pListNode find = phead->next; find != phead; find = find->next)
	{
		if (find->data == x)
		{
			return find;
		}
	}
	return NULL;
}

void ListInsert(pListNode pos, LTDataType x)
{
	assert(pos);

	pListNode newNode = CreateNode(x);
	pListNode prev = pos->prev;

	newNode->next = pos;
	newNode->prev = prev;
	pos->prev = newNode;
	prev->next = newNode;
}

void ListErase(pListNode pos)
{
	assert(pos);				// 非空时pos不能传入哨兵位,不然删除后会丢失整个链表
	assert(!ListEmpty(pos));

	pListNode prev = pos->prev;
	pListNode next = pos->next;

	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}

相关推荐

  1. 双向实现

    2024-06-09 01:46:01       14 阅读
  2. 双向实现

    2024-06-09 01:46:01       15 阅读
  3. C实现双向队列

    2024-06-09 01:46:01       34 阅读
  4. 带头循环双向实现

    2024-06-09 01:46:01       19 阅读
  5. python实现循环双向

    2024-06-09 01:46:01       7 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-06-09 01:46:01       8 阅读
  2. 【Python教程】压缩PDF文件大小

    2024-06-09 01:46:01       9 阅读
  3. 通过文章id递归查询所有评论(xml)

    2024-06-09 01:46:01       10 阅读

热门阅读

  1. 【C/C++】相机标定

    2024-06-09 01:46:01       8 阅读
  2. ffmpeg视频编码原理和实战-(4)H264原始码流分析

    2024-06-09 01:46:01       7 阅读
  3. MATLAB 匿名函数

    2024-06-09 01:46:01       5 阅读
  4. GPT-4o的崛起:人工智能新纪元的开端

    2024-06-09 01:46:01       5 阅读
  5. 一千题,No.0049(跟奥巴马一起编程)

    2024-06-09 01:46:01       9 阅读
  6. 一些关于机器学习的思路和猜测

    2024-06-09 01:46:01       7 阅读