Hello , Today, sister a Zi called all Wulin heroes , What's the matter ???

Everyone answered : Of course, sister a Zi has come to lead us to learn new Kung Fu !!!

first , You have to warm up before practicing kung fu ( Tell you in a low voice , Sister a Zi said warming up is soul chicken soup )

* perseverance prevails , Whenever we can't hold on , We all have to tell ourselves , Victory is not far away , If you give up your previous efforts, you will fall short of success .
* We must insist , insist , Hold on !!!
* Persistence is the secret of doing anything .
review :

First, let's take a look at the shortcomings of the single linked list ???

Main disadvantages of single linked list :① Cannot traverse from back to front ② No precursors found

Single linked list defect solution -》 Double linked list :

There are eight linked list structures :

  Code implementation of two-way circular linked list :

list.h: Header file
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h>
#include<assert.h> #pragma once typedef int LTDataType;
// Lead two-way cycle --- Most linked list structure , Inserting and deleting data anywhere is O(1) typedef struct ListNode { struct ListNode*
next; struct ListNode* prev; LTDataType data; }ListNode; // initialization ListNode*
ListInit(ListNode* phead); // Tail insertion void ListPushBack(ListNode* phead,LTDataType
x); // Head insert void ListPushFront(ListNode* phead, LTDataType x); // Print void
ListPrint(ListNode* phead); // Header deletion void ListPopFront(ListNode* phead); // Tail deletion void
ListPopBack(ListNode* phead); // lookup ListNode* ListFind(ListNode* phead,
LTDataType x); //pos Insert before position x void ListInsert(ListNode* pos, LTDataType x);
// delete pos Value of position void ListErase(ListNode* pos); // Destroy linked list void ListDestory(ListNode*
phead);
The header file of the library function is included in the header file , Structure declaration , Type redefinition , Custom function declaration

test.c: Test file
#define _CRT_SECURE_NO_WARNINGS 1 #include"list.h" void TestList1() {
ListNode* plist = NULL; plist = ListInit(plist); ListPushBack(plist, 1);
ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4);
ListPushBack(plist, 5); ListPushBack(plist, 6); ListPrint(plist);
ListPushFront(plist, 0); ListPrint(plist); ListPopFront(plist);
ListPrint(plist); ListPopBack(plist); ListPrint(plist); ListNode* pos =
ListFind(plist, 3); if (pos) { // Find incidental modifications pos->data *= 10;
printf(" eureka , also *10\n"); } else { printf(" Can't find \n"); } ListPrint(plist);
ListInsert(pos, 300); ListPrint(plist); ListErase(pos); ListPrint(plist);
ListDestory(plist); } int main() { TestList1(); return 0; }
It mainly tests the function of our double linked list

Next, let's look at the implementation of custom functions one by one :

Linked list initialization :
ListNode* BuyListNode(LTDataType x) { ListNode* newnode =
(ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { return; }
newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode;
} ListNode* ListInit(ListNode* phead) { phead = BuyListNode(0); phead->next =
phead; phead->prev = phead; return phead; }

Tail insertion
ListNode* BuyListNode(LTDataType x) { ListNode* newnode =
(ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { return; }
newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode;
} void ListPushBack(ListNode* phead, LTDataType x) { ListNode* tail =
phead->prev; ListNode* newnode = BuyListNode(x); tail->next = newnode;
newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }

  Tail deletion
void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next !=
phead); ListNode* tail = phead->prev; ListNode* prev = tail->prev; prev->next =
phead; phead->prev = prev; free(tail); tail = NULL; }

  Head insert :
ListNode* BuyListNode(LTDataType x) { ListNode* newnode =
(ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { return; }
newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode;
} void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode*
first = phead->next; ListNode* newnode = BuyListNode(x); phead->next = newnode;
newnode->prev = phead; newnode->next = first; first->prev = newnode; }

  Header deletion :
void ListPopFront(ListNode* phead) { assert(phead); assert(phead->next !=
phead); ListNode* first = phead->next; ListNode* second = first->next;
phead->next = second; second->prev = phead; free(first); first = NULL; }

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

  lookup :
ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); ListNode*
cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; }
cur = cur->next; } return NULL; }
cur Point to the first node , When the data field of the node is not equal to x, Just look at the next node , If you finally find it phead Didn't find it , That means No .

Insert a node before a node :
void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode
= BuyListNode(x); ListNode* prev = pos->prev; prev->next = newnode;
newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }

  Delete a node :
void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->prev;
ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos);
pos = NULL; }

  Destroy linked list :
void ListDestory(ListNode* phead) { assert(phead); ListNode* cur =
phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur
= next; } free(phead); phead = NULL; }

Have you learned today's double linked list martial arts ???

Well, that's all for today !!!

Technology
©2019-2020 Toolsou All rights reserved,
【C++ Must see for entry 】C++ from 0 reach 1 Introductory programming axios Interceptor packaging and use Spring Boot Interview must ask : Automatic configuration principle VMware 16 install centos 7 Detailed tutorial C Language data structure - Sequence table delete duplicates V2.0.0 The 12th Blue Bridge Cup c++b Group personal problem solving On sending data from serial port single chip microcomputer to upper computer centos7 install RabbitMqjava Polymorphic array of opencv-python Fourier transform and inverse transform