Hello, I’m Yui.
Foreword
Speaking of linked lists, we talked about singly linked lists before, but there are more than one types of linked lists, if you want to classify them. Linked lists can be divided into headed or non-headed, one-way or two-way, cyclic or non-cyclic, which means that there should be a total of 8 structures of linked lists. The linked list we talked about last time is a one-way non-cyclic linked list without a leader. It is the simplest structure among linked lists.
Let’s briefly explain the two types of linked lists:
1.Headless one-way non-cyclic linked list: The structure is simple and is generally not used to store data alone. In practice, it is more often used as other data structures.
Structured substructures, such as hash buckets, graph adjacency lists, etc. In addition, this structure appears a lot in written interviews.
2. Headed two-way circular linked list: The structure is the most complex and is generally used to store data separately. The linked list data structures used in practice are all
It is a leading two-way circular linked list. In addition, although this structure is complex, after using the code to implement it, you will find that the structure will bring many advantages, and the implementation will be simpler. We will know it later when we implement the code.
Implementation of linked list
Having said so much before, the most important thing is to be able to implement the linked list yourself. The following is the implementation of the teaching.
Create different files
Create 3 files, the functions to be implemented are function declaration, function definition, and test. The purpose is to facilitate subsequent additions, deletions, checking and modifications.
Creation of structure
prev represents the previous node and next represents the next node.
Declaration of function
It is similar to the function declaration of a singly linked list, including head deletion, head insertion, tail insertion, tail deletion, printing, etc…
We finish writing the function declarations first, and then implement them one by one later.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDataType;
typedef struct ListNode
{<!-- -->
LTDataType data;
struct ListNode* prev;
struct ListNode* next;
}ListNode;
//Create the head node of the returned linked list.
ListNode* ListCreate();
// Destroy doubly linked list
void ListDestory(ListNode* pHead);
//Print doubly linked list
void ListPrint(ListNode* pHead);
//Insert at the end of the doubly linked list
void ListPushBack(ListNode* pHead, LTDataType x);
// Delete the end of the doubly linked list
void ListPopBack(ListNode* pHead);
// Insert the head of the two-way linked list
void ListPushFront(ListNode* pHead, LTDataType x);
// Delete the header of the doubly linked list
void ListPopFront(ListNode* pHead);
//Doubly linked list search
ListNode* ListFind(ListNode* pHead, LTDataType x);
// Doubly linked list is inserted in front of pos
void ListInsert(ListNode* pos, LTDataType x);
// Delete the node at pos position in the doubly linked list
void ListErase(ListNode* pos);
After writing the function declaration, the next step is to implement the function.
Function implementation
The implementation of the function is written in the list.c file
Let’s first talk about the creation of the head node. The head node is the head of the linked list and does not store valid data.
Creation of head node
//Create the head node of the returned linked list.
ListNode* ListCreate()
{<!-- -->
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
head->data = -1;//You can store any data, and the data of the head node will not be used in subsequent operations.
head->prev = head;
head->next = head;//Both prev and next should point to themselves to achieve looping.
return head;
}
After writing the creation of the head node, we also need to write a printing function to make subsequent operations more intuitive.
Implementation of printing function
//Double linked list printing
void ListPrint(ListNode* pHead)
{<!-- -->
ListNode* cur = pHead->next;
printf("phead");
while (cur != pHead)
{<!-- -->
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("phead\\
");
}
cur!=pHead, the purpose is not to print the head node.
Next we have to write an insertion function to observe intuitively. So we next write the tail interpolation function.
Implementation of tail insertion function
Drawing explanation
//Tail insert in doubly linked list
void ListPushBack(ListNode* pHead, LTDataType x)
{<!-- -->
assert(pHead);
ListNode* newnode = CreatNode(x);
ListNode* cur = pHead;
ListNode* tail = pHead->prev;
tail->next = newnode;
newnode->prev = tail;
cur->prev = newnode;
newnode->next = cur;
}
After writing the tail insertion function, we have to write a new node creation function
ListNode* CreatNode(LTDataType x)
{<!-- -->
ListNode* newnode = (ListNode* )malloc(sizeof(ListNode));
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
Oak, after finishing writing, start printing the test.
If it seems to be successful, it means there is no problem. If there is any problem, check again later.
Implementation of header plug-in function
After writing the tail insertion, of course it is time to insert the head insertion.
Drawing explanation
//Two-way linked list head insertion
void ListPushFront(ListNode* pHead, LTDataType x)
{<!-- -->
assert(pHead);
ListNode* newnode = CreatNode(x);
ListNode* cur = pHead;
ListNode* next = pHead->next;
cur->next = newnode;
newnode->prev = cur;
newnode->next = next;
next->prev = newnode;
}
Next, test it and see.
Still no problem.
Implementation of tail deletion function
Remember to free after deletion
//Delete the tail of the doubly linked list
void ListPopBack(ListNode* pHead)
{<!-- -->
assert(pHead->next != pHead);//When there is only the head node, an error is reported
ListNode* cur = pHead;
ListNode* tail = pHead->prev;
cur->prev = tail->prev;
tail->prev->next = cur;
free(tail);
tail = NULL;
}
test
Let’s delete some first, then delete them all, then delete one more and test them separately.
We can also see from these three pictures that there is no problem with the code. (Here I quietly changed the code of the printing function, do you see it?)
Implementation of header deletion function
Remember to be free
//Delete the header of the doubly linked list
void ListPopFront(ListNode* pHead)
{<!-- -->
assert(pHead->next != pHead);
ListNode* first = pHead->next;
pHead->next = first->next;
first->next->prev = pHead;
free(first);
first = NULL;
}
Test again below to see if there is any problem.
There is no problem either.
Implementation of destruction function
Why was it destroyed? Of course, I want to treat the remaining additions, deletions, and modifications at the specified location as homework.
//double linked list destruction
void ListDestory(ListNode* pHead)
{<!-- -->
ListNode* cur = pHead->next;
while (cur != pHead)
{<!-- -->
ListNode* next = cur->next;
free(cur);
cur = NULL;
cur = next;
}
//Finally free pHead
free(pHead);
pHead = NULL;
}
That’s it.
Below we post all the code (including the search function and the addition, deletion, and modification functions at the specified location)
Code
list.h
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDataType;
typedef struct ListNode
{<!-- -->
LTDataType data;
struct ListNode* prev;
struct ListNode* next;
}ListNode;
//Create the head node of the returned linked list.
ListNode* ListCreate();
// Destroy doubly linked list
void ListDestory(ListNode* pHead);
//Print doubly linked list
void ListPrint(ListNode* pHead);
//Insert at the end of the doubly linked list
void ListPushBack(ListNode* pHead, LTDataType x);
// Delete the end of the doubly linked list
void ListPopBack(ListNode* pHead);
// Insert the head of the two-way linked list
void ListPushFront(ListNode* pHead, LTDataType x);
// Delete the header of the doubly linked list
void ListPopFront(ListNode* pHead);
//Doubly linked list search
ListNode* ListFind(ListNode* pHead, LTDataType x);
// Doubly linked list is inserted in front of pos
void ListInsert(ListNode* pos, LTDataType x);
// Delete the node at pos position in the doubly linked list
void ListErase(ListNode* pos);
list.c
#define _CRT_SECURE_NO_WARNINGS
#include "list.h"
ListNode* CreatNode(LTDataType x)
{<!-- -->
ListNode* newnode = (ListNode* )malloc(sizeof(ListNode));
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
//Create the head node of the returned linked list.
ListNode* ListCreate()
{
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
head->data = -1;//You can store any data, and the data of the head node will not be used in subsequent operations.
head->prev = head;
head->next = head;//prev and next must point to themselves to achieve looping.
return head;
}
//Print doubly linked list
void ListPrint(ListNode* pHead)
{
ListNode* cur = pHead->next;
printf("phead<=>");
while (cur != pHead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("phead\\
");
}
//Insert at the end of the doubly linked list
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = CreatNode(x);
ListNode* cur = pHead;
ListNode* tail = pHead->prev;
tail->next = newnode;
newnode->prev = tail;
cur->prev = newnode;
newnode->next = cur;
}
// Insert the head of the two-way linked list
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = CreatNode(x);
ListNode* cur = pHead;
ListNode* next = pHead->next;
cur->next = newnode;
newnode->prev = cur;
newnode->next = next;
next->prev = newnode;
}
// Delete the end of the doubly linked list
void ListPopBack(ListNode* pHead)
{
assert(pHead->next != pHead);//An error is reported when there is only the head node
ListNode* cur = pHead;
ListNode* tail = pHead->prev;
cur->prev = tail->prev;
tail->prev->next = cur;
free(tail);
tail = NULL;
}
// Delete the header of the doubly linked list
void ListPopFront(ListNode* pHead)
{
assert(pHead->next != pHead);
ListNode* first = pHead->next;
pHead->next = first->next;
first->next->prev = pHead;
free(first);
first = NULL;
}
// Destroy doubly linked list
void ListDestory(ListNode* pHead)
{
ListNode* cur = pHead->next;
while (cur != pHead)
{
ListNode* next = cur->next;
free(cur);
cur = NULL;
cur = next;
}
//Finally free pHead
free(pHead);
pHead = NULL;
}
//Doubly linked list search
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
ListNode* cur = pHead->next;
if (x == -1)
{
return NULL;
}
while (cur != pHead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// Doubly linked list is inserted in front of pos
void ListInsert(ListNode* pos, LTDataType x)
{
ListNode* newnode = CreateNode(x);
ListNode* prev = pos->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
// Delete the node at pos position in the doubly linked list
void ListErase(ListNode* pos)
{
ListNode* prev = pos->prev;
ListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include "list.h"
void test1()
{<!-- -->
ListNode* head = ListCreate();//Creation of head node
ListPushBack(head, 1);
ListPushBack(head, 2);
ListPushBack(head, 3);
ListPushBack(head, 4);
ListPrint(head);
ListPushFront(head, 5);
ListPushFront(head, 6);
ListPushFront(head, 7);
ListPrint(head);
}void test2()
{<!-- -->
ListNode* head = ListCreate();//Creation of head node
ListPushBack(head, 1);
ListPushBack(head, 2);
ListPushBack(head, 3);
ListPushBack(head, 4);
ListPrint(head);
ListPopFront(head);
ListPopFront(head);
ListPopFront(head);
ListPopFront(head);
ListPopFront(head);
ListPrint(head);
}
int main()
{<!-- -->
test2();
return 0;
}
over
