“This is the 16th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Double linked list

Double linked list structure diagram

Doubly linked list node

typedef int LTDataType;  // in C++, double-linked lists are represented by lists

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;
Copy the code

The double-linked list initialization function ListInit

// Double linked list initializer function
LTNode* ListNodeInit(a)
{
	// Create a double-linked list sentinel header that does not store valid data loops
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
Copy the code

ListPushBack double-linked list tail insert function

// Double linked list tail insert function
void ListNodePushBack(LTNode* phead, LTDataType x)
{
	assert(phead);// Phead can never be NULL
	LTNode* tail = phead->prev;
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
Copy the code

Double linked list printing function ListPrint

// Double linked list print function
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while(cur ! = phead) {printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
Copy the code

ListPopBack is a double-linked tail deletion function

// Double linked list end delete function
void ListPopBack(LTNode* phead)
{ assert(phead && phead->next ! = phead); LTNode* tail = phead->prev; LTNode* cur = phead->prev; tail = tail->prev; tail->next = phead; phead->prev = tail;free(cur);
}
Copy the code

ListPushFront is a double linked list header interpolation function

// Double list header interpolation function
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* next = phead->next;// Insert a node between next and phead
	/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode->data = x; * /
	LTNode* newnode = BuyListNode(x);
	newnode->next = next;
	next->prev = newnode;
	phead->next = newnode;
}
Copy the code

Since we’re dealing with add-nodes at the beginning and end, we’ll take the add-nodes out and repackage them

Get the double-linked list node function BuyListNode

// Get the double-linked list node function
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
Copy the code

Double linked header delete function ListPopFront

// Double linked header delete function
void ListPopFront(LTNode* phead)
{ assert(phead && phead->next ! = phead); LTNode* next = phead->next; phead->next = next->next; next->next->prev = phead;free(next);
}
Copy the code

ListFind double-linked list lookup function

This is usually used in conjunction with insert and delete

// double linked list lookup function
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while(cur ! = phead) {if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
Copy the code

The double linked list insertion function ListInsert (insert before pos because it is inserted before in c++)

// Double linked list insert function
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;
	newnode->data = x;
	pos->prev = newnode;
	newnode->next = pos;
	newnode->prev = posprev;
	posprev->next = newnode;
}
Copy the code

Double-linked list delete function ListErase (delete pos)

// Double linked list delete function
void ListErase(LTNode* pos)
{
	assert(pos && pos->next);
	LTNode* posnext = pos->next;
	LTNode* posprev = pos->prev;
	posnext->prev = posprev;
	posprev->next = posnext;
	free(pos);
}
Copy the code

Double linked ListDestroy function ListDestroy(actually I wrote this error, the previous function was buggy, but found)

// Double linked list destruction function
void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;
	while(tail ! = phead) { LTNode* tailprev = tail->next;free(tail);
		tail = tailprev;
	}
	free(phead);
	phead = NULL;
}
Copy the code

code

DoubleList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;  // in C++, double-linked lists are represented by lists

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

// Double linked list initializer function
extern LTNode* ListInit(a);
// Double linked list destruction function
extern void ListDestroy(LTNode* phead);
// Double linked list tail insert function
extern void ListPushBack(LTNode* phead, LTDataType x);
// Double linked list print function
extern void ListPrint(LTNode* phead);
// Double linked list end delete function
extern void ListPopBack(LTNode* phead);
// Get the double-linked list node function
extern LTNode* BuyListNode(LTDataType x);
// Double list header interpolation function
extern void ListPushFront(LTNode* phead, LTDataType x);
// Double linked header delete function
extern void ListPopFront(LTNode* phead);
// double linked list lookup function
extern LTNode* ListFind(LTNode* phead, LTDataType x);
// Double linked list insert function
extern void ListInsert(LTNode* pos, LTDataType x);
// Double linked list delete function
extern void ListErase(LTNode* pos);

Copy the code

DoubleList.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "DoubleList.h"

// Double linked list initializer function
LTNode* ListInit(a)
{
	// Create a double-linked list sentinel header that does not store valid data loops
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
// Get the double-linked list node function
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
// Double linked list tail insert function
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);// Phead can never be NULL
	LTNode* tail = phead->prev;
	/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode->data = x; * /
	LTNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
// Double linked list print function
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while(cur ! = phead) {printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
// Double linked list end delete function
void ListPopBack(LTNode* phead)
{ assert(phead && phead->next ! = phead); LTNode* tail = phead->prev; LTNode* cur = phead->prev; tail = tail->prev; tail->next = phead; phead->prev = tail;free(cur);
}

// Double list header interpolation function
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* next = phead->next;// Insert a node between next and phead
	/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode->data = x; * /
	LTNode* newnode = BuyListNode(x);
	newnode->next = next;
	next->prev = newnode;
	phead->next = newnode;
}

// Double linked header delete function
void ListPopFront(LTNode* phead)
{ assert(phead && phead->next ! = phead); LTNode* next = phead->next; phead->next = next->next; next->next->prev = phead;free(next);
}

// double linked list lookup function
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while(cur ! = phead) {if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
// Double linked list insert function
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;
	newnode->data = x;
	pos->prev = newnode;
	newnode->next = pos;
	newnode->prev = posprev;
	posprev->next = newnode;
}
// Double linked list delete function
void ListErase(LTNode* pos)
{
	assert(pos && pos->next);
	LTNode* posnext = pos->next;
	LTNode* posprev = pos->prev;
	posnext->prev = posprev;
	posprev->next = posnext;
	free(pos);
}
// Double linked list destruction function
void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;
	while(tail ! = phead) { LTNode* tailprev = tail->next;free(tail);
		tail = tailprev;
	}
	free(phead);
	phead = NULL;
}
Copy the code

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "DoubleList.h"
void TestList1(a)
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
	ListPushFront(plist, 10);
	ListPushFront(plist, 20);
	ListPushFront(plist, 30);
	ListPrint(plist);
	LTNode* p1 = ListFind(plist, 10);
	if (p1)
	{
		ListInsert(p1, 100);
	}
	ListPrint(plist);
	LTNode* p2 = ListFind(plist, 20);
	if (p2)
	{
		ListErase(p2);
	}
	ListPrint(plist);
	ListDestroy(plist);
	plist = NULL;
}


int main(a)
{
	TestList1();
	return 0;
}

Copy the code

Welcome to our friends’ communityHui programming open source club