【数据结构】双向链表

链表

双向链表

List.h

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

typedef int LTDataType;

typedef struct ListNode {
	struct ListNode* next;
	struct ListNode* prev;

	LTDataType data;
}LTNode;

void LTInit(LTNode** pphead);
//LTNode* LTInit();
void LTDestroy(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);

void LTPushBack(LTNode* phead,LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);

LTNode* LTFind(LTNode* phead, LTDataType x);

//在pos位置之前插入一个值
void LTInsert(LTNode* pos, LTDataType x);

void LTErase(LTNode* pos);

List.c

#include "List.h"

LTNode* BuyListNode(LTDataType x) {
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL) {
		perror("malloc fail");
		return NULL;
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;

	return node;
}

void LTInit(LTNode** pphead) {
	*pphead = BuyListNode(-1);
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
}
//LTNode*  LTInit() {
//	LTNode* phead = BuyListNode(-1);
//	phead->next = phead;
//	phead->prev = phead;
//
//	return phead;
//}

void LTDestroy(LTNode* phead) {
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead) {
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}


void LTPrint(LTNode* phead) {
	assert(phead);

	printf("<-head->");
	LTNode* cur = phead->next;
	while (cur != phead) {
		printf("%d<->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

bool LTEmpty(LTNode* phead) {
	assert(phead);
	return phead->next == phead;
}

void LTPushBack(LTNode* phead, LTDataType x) {
	assert(phead);

	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
	//LTInsert(phead, x);
}
void LTPopBack(LTNode* phead) {
	assert(phead);
	assert(!LTEmpty(phead));

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	tailPrev->next = phead;
	phead->prev = tailPrev;

	free(tail);
	tail = NULL;
	//LTErase(phead->prev);
}
}
void LTPushFront(LTNode* phead, LTDataType x) {
	assert(phead);

	LTNode* newnode = BuyListNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
}
void LTPopFront(LTNode* phead) {
	assert(phead);
	assert(!LTEmpty(phead));

	LTNode* tmp = phead->next;
	phead->next = tmp->next;
	tmp->next->prev = phead;
	//LTErase(phead->next);
}

LTNode* LTFind(LTNode* phead, LTDataType x) {
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead) {
		if (cur->data == x)
			return cur;
		
		cur = cur->next;
	}
	return NULL;
}
void LTInsert(LTNode* pos, LTDataType x) {
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	//prev newnode pos
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

void LTErase(LTNode* pos) {
	assert(pos);

	LTNode* prev = pos->prev;
	prev->next = pos->next;
	pos->next->prev = prev;

	free(pos);
}

Test.c

#include "List.h"

void TestList1() {
	LTNode* plist = NULL;
	LTInit(&plist);
	//LTNode* plist=LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);

	LTPushFront(plist, 1);
	LTPrint(plist);
}
void TestList2() {
	LTNode* plist = NULL;
	LTInit(&plist);
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTNode* pos = LTFind(plist, 3);
	if (pos) {
		LTErase(pos);
		pos = NULL;
	}
	LTPopFront(plist);
	LTPrint(plist);
}

int main() {
	TestList2();
	return 0;
}

例1

方法：
拷贝节点链接在原节点的后面
拷贝原节点的random，原节点的random->next
拷贝链表解下来，链接成一个新链表，原链表恢复

顺序表与链表区别

顺序表，链表储存在堆上
对顺序表/链表每个位置数据遍历访问/修改 cpu
cpu不能直接访问内存->cpu高速缓存
cpu->缓存，命中，直接访问；不命中，把内存中的数据加载到缓存中再进行访问，但不能把所有数据都加载过去，会将一些数据挤出去，会使用一些算法

为什么顺序表缓存利用高而链表缓存利用低：
当内存中的数据向缓存中加载时，假如要访问顺序表中的四个字节，不会只加载四个字节进去，会多加载一些，因为根据局部性原理，访问当前位置后，大概率会访问接下来的位置，且由于总线等一部分原因，只加载四个字节不划算，好比说出租车有四个座位，一次只坐一个人不划算，不同的硬件加载多少不同

假设最开始顺序表数据都不在缓存，访问第一个数据不命中，将内存中的数据加载到缓存中，访问下一个位置会命中，如果是链表，访问下一个位置不一定命中，且有可能造成缓存污染