A solution to double linked list (0 basic view) (C language) data structure and algorithm

First of all, this article is related to the previous single linked list. The previous article has explained the concept and classification of linked list in detail. I won't repeat it here. Let's briefly explain it. The link is below. A single linked list (0 basic view) (C language) data structure and algorithm_ Original 45 blog - CSDN blog

Above, we talked about the two most important categories of the linked list. One is one-way non leading non circulation. This article will talk about another important leading two-way circular linked list. Ha, don't talk more nonsense, just look at the code.

By the way, the author's qq: 2777137742 is attached here. If you have any questions, you can ask me on qq, or there are mistakes in the article. I look forward to discussing with you, because the csdn message may be omitted. Finally, thank you for your support.

Lead two-way circular linked list

1. Concept

Lead two-way circular linked list: the structure is the most complex. It is generally used to store data separately. The linked list data structures used in practice are

It is a two-way circular linked list. In addition, although the structure of this structure is complex, it will be found that the structure will take a long time after it is implemented in code

For many advantages, the implementation is simple. We will know when we implement the code later.

Here we will slowly reveal the simpler implementation mentioned above and the disadvantages of single linked list. The disadvantages are direct. We can intuitively find two great disadvantages of single linked lists. One is that tail insertion and tail deletion need to be traversed, that is, the time complexity is O (N), but double linked lists correspond to o (1), which is very efficient. Another disadvantage is that the single linked list cannot find its previous node, which is a big defect. Then we look at the advantages of double linked list.

2. Effect display diagram

3. Interface implementation

As an old saying, for the implementation of the interface, we first need to know what to implement. This paper is the basic use of the double linked list, so we only realize the addition, deletion, query and modification of the sequential list, as well as the insertion and deletion of specific location values before a specific location. Of course, the code does not have to be written by the author. Here is just an idea. Don't talk more nonsense. Look at the code.

3.01. The interface to be implemented in this article

3.02. Implementation of double linked list

This is the name of ListNode, which corresponds to c + +. You can also name DListnode corresponding to the single linked list SListNode, but the author named it ListNode in order to develop a good habit.

3.03. Initialization of double linked list

Note that the initialization here points to itself because it is a loop. Then this article does not use a secondary pointer (no address). Here, a return value is used.

3.04. Print linked list

3.05. Dynamically apply for a node

3.06. Head insert

3.07. Tail insertion

3.08. Header deletion

3.09. Tail deletion

3.10. Check a value and return the address

3.11. Insert data before a location

3.12. Delete a location data

3.13. Change a value

3.14. Destroy

summary

We can find that the implementation of the leading two-way circular linked list does not need to judge whether there is no or a node like the single linked list. The structure is very perfect. We can use the head node to make various changes. The implementation is also very simple, and there is no need to pass the address.

Here, I'd like to explain why we can't pass the address again, because our header hasn't changed, and we don't need to change the header. This change refers to the parameter plist we passed at the beginning. It always points to our header, but the direction hasn't changed. The content can be changed, that is, the direction and date of the predecessor prev and subsequent next of plist can be changed. This understanding is very important!

4. Source code

test.c

#include"List.h"


int main()
{
	printf("initialization\n");
	ListNode* plist = ListInit();
	printf("Insert head 1, 2, 3 and print\n");
	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPrint(plist);
	printf("Tail insert 4 5 6 and print\n");
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPushBack(plist, 6);
	ListPrint(plist);
	printf("Header delete and print\n");
	ListPopFront(plist);
	ListPrint(plist);
	printf("Delete and print\n");
	ListPopBack(plist);
	ListPrint(plist);
	printf("1 Insert 3 before printing\n");
	ListNode* pos = ListFind(plist, 1);
	ListInsert(plist, pos, 3);
	ListPrint(plist);
	printf("2 Insert 8 before printing\n");
	pos = ListFind(plist, 2);
	ListInsert(plist, pos, 8);
	ListPrint(plist);
	printf("Delete 4 and print\n");
	pos = ListFind(plist, 4);
	ListErase(plist, pos);
	ListPrint(plist);
	printf("Change 1 to 9 and print\n");
	ListChange(plist, 1, 9);
	ListPrint(plist);
	printf("Destroy linked list\n");
	ListDestory(plist);
	return 0;
}

List.h

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<malloc.h>
#include<assert.h>

typedef int ListDateType;

typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	ListDateType date;
}ListNode;

//Add, delete, check and modify

//initialization
ListNode* ListInit();
//Destroy
void ListDestory(ListNode* phead);
//Get a node
ListNode* BuyListNode(ListDateType x);
//Print
void ListPrint(ListNode* phead);

//Head insert
void ListPushFront(ListNode* phead, ListDateType x);
//Tail insertion
void ListPushBack(ListNode* phead, ListDateType x);
//Header deletion
void ListPopFront(ListNode* phead);
//Tail deletion
void ListPopBack(ListNode* phead);

//Check a value and return the address
ListNode* ListFind(ListNode* phead, ListDateType x);
//Change a value
void ListChange(ListNode* phead, ListDateType source, ListDateType destination);

//Insert data before a location
void ListInsert(ListNode* phead, ListNode* pos, ListDateType x);
//Delete a location data
void ListErase(ListNode* phead, ListNode* pos);

List.c

#include"List.h"


//initialization
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->prev = phead;
	phead->next = phead;
	phead->date = 0;
	return phead;
}

//Get a node
ListNode* BuyListNode(ListDateType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->prev = NULL;
	newnode->next = NULL;
	newnode->date = x;
	return newnode;
}

//Head insert
void ListPushFront(ListNode* phead, ListDateType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* first = phead->next;

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

//Tail insertion
void ListPushBack(ListNode* phead, ListDateType x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyListNode(x);

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

//Print
void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
	printf("\n");
}

//Header deletion
void ListPopFront(ListNode* phead)
{
	assert(phead);
	//Don't delete the head
	assert(phead->next != phead);
	ListNode* first = phead->next;
	phead->next = first->next;
	first->next->prev = phead;

	free(first);
	first = NULL;
}

//Tail deletion
void ListPopBack(ListNode* phead)
{
	assert(phead);
	//Don't delete the head
	assert(phead->next != phead);
	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;

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

//Check a value and return the address
ListNode* ListFind(ListNode* phead, ListDateType x) 
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->date == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

//Insert data before a location   
void ListInsert(ListNode* phead, ListNode* pos, ListDateType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* prev = pos->prev;
	
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

//Delete a location data
void ListErase(ListNode* phead, ListNode* pos)
{
	assert(phead);
	//Don't delete the head
	assert(phead->next != phead);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;

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

//Change a value
void ListChange(ListNode* phead, ListDateType source, ListDateType destination)
{
	assert(phead);
	ListNode* pos = ListFind(phead, source);
	pos->date = destination;
}

//Destroy
void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	ListNode* tail = cur->next;
	while (tail != phead)
	{
		free(cur);
		cur = NULL;
		cur = tail;
		tail = tail->next;
	}
	free(cur);
	cur = NULL;
	if (cur != tail)
	{
		free(tail);
		tail = NULL;
	}
}

That's all for today!!!

If you think the author is a little helpful to you!

Just pay attention!!! Of course, subscription is even more desirable!

Give someone a rose, the hand has a lingering fragrance =. =!

Finally, thank you for watching!!!

Your support is the greatest driving force for the author to write!!!

See you next time!!!

Keywords: C Algorithm data structure Back-end linked list

Added by tbaink2000 on Sat, 15 Jan 2022 12:29:43 +0200

Programming VIP