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 ???
QQ.2186529582
Let's cheer together , Go one step further from success !!!
Well, that's all for today !!!
Technology