Creation of headless one-way non-circular linked list and headed two-way circular linked list

Lei Bao: Personal Homepage

May all good things come to you unexpectedly

Foreword:

Next we will understand the most basic linked list—>single linked list

And the most convenient and coolest linked list —> take the lead in bidirectional circular linked list.

If there is something you don’t understand, you can draw a picture or refer to it here: Inverting a single linked list, for the data structure, it is nothing more than adding, deleting, checking and modifying. When we can skillfully apply and draw pictures, the OJ questions and the following codes are all small karaoke rice.

Headless one-way non-circular linked list

Singly linked list diagram:

Header:

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

typedef int DataType;

typedef struct STLNode
{
DataType data;
struct STLNode* next;
}STLNode;

void STL_Print(STLNode* phead);
void STL_PushBack(STLNode** pphead, DataType x);
void STL_PushFront(STLNode** pphead, DataType x);
void STL_PopBack(STLNode** pphead);
void STL_PopFront(STLNode** pphead);
STLNode* STL_Find(STLNode* phead, DataType x);
void STL_InsertAfter(STLNode* pos, DataType x);
void STL_EraseAfter(STLNode* pos);
void STL_Destroy(STLNode** pphead);

Test file:

#include "STLNode.h"

void Test1(STLNode* phead);

int main()
{
\t
STLNode* plist = NULL;

Test1(plist);
return 0;
}

void Test1(STLNode* phead)
{
\t
STL_PushBack( &phead, 1);
STL_PushBack( &phead, 2);
STL_PushBack( &phead, 3);
STL_Print(phead);

STL_PushFront( &phead, 11);
STL_PushFront( &phead, 22);
STL_PushFront( &phead, 33);
STL_Print(phead);

STLNode* ret = STL_Find(phead, 1);
STL_InsertAfter(ret, 666);
STL_Print(phead);

STL_EraseAfter(ret);
STL_Print(phead);

STL_Destroy( &phead);
STL_Print(phead);
//STL_PopBack( &phead);
//STL_PopBack( &phead);
//STL_Print(phead);

//STL_PopFront( &phead);
//STL_PopFront( &phead);
//STL_Print(phead);


}

Function source file:

Some of the following functions have checks for phead and pphead, and some do not. The reason is this:

As for whether it needs to be asserted, we need to see whether it is reasonable when it is NULL. If it is reasonable, it will not be asserted, and if it is unreasonable, it will be asserted. For example, in the STL_Printf function, when phead is NULL, it means that the linked list is empty. Print directly NULL is fine, which makes sense. For the STL_PushBack function, it is also reasonable for phead to be NULL, because phead is NULL, and our tail insertion is actually equivalent to head insertion, which is very reasonable, but for pphead, it is the address of the plist, even if the plist is NULL, pphead is It should not be NULL, so it is very unreasonable for him to be NULL, we need to check the assertion.

#include "STLNode.h"

void STL_Print(STLNode* phead)
{

while (phead)
{
printf("%d->", phead->data);
phead = phead->next;
}
printf("NULL\\
");

}

STLNode* Malloc(DataType x)
{
STLNode* temp = (STLNode*)malloc(sizeof(STLNode));
if (temp == NULL)
{
perror("malloc fail");
exit(-1);
}
temp->data = x;
temp->next = NULL;

return temp;
}

void STL_PushBack(STLNode** pphead, DataType x)
{
assert(pphead);

STLNode* temp = Malloc(x);

if (*pphead == NULL)
{
*pphead = temp;
}
else
{
STLNode* cur = *pphead;
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = temp;
}
}

void STL_PushFront(STLNode** pphead, DataType x)
{
assert(pphead);

STLNode* temp = Malloc(x);
temp->next = *pphead;
*pphead = temp;

}

void STL_PopBack(STLNode** pphead)
{
assert(pphead);
assert(*pphead);

STLNode* cur = *pphead;
STLNode* temp = *pphead;
\t
if (cur->next == NULL)
{
free(cur);
*pphead = NULL;
}
else
{
while (cur->next)
{
temp = cur;
cur = cur->next;
}
free(cur);
temp->next = NULL;
}
\t
}

void STL_PopFront(STLNode** pphead)
{
assert(pphead);
assert(*pphead);

STLNode* cur = *pphead;
*pphead = (*pphead)->next;
free(cur);

}

STLNode* STL_Find(STLNode* phead, DataType x)
{
if (phead == NULL)
{
printf("NULL\\
");
return;
}

while (phead != NULL)
{
if (phead->data == x)
{
return phead;
}
phead = phead->next;
}

printf("Can not find\\
");
return;
}

void STL_InsertAfter(STLNode* pos, DataType x)
{
assert(pos);

STLNode* temp = Malloc(x);
temp->next = pos->next;
pos->next = temp;

}

void STL_EraseAfter(STLNode* pos)
{
assert(pos);
assert(pos->next);

STLNode* cur = pos->next;
pos->next = pos->next->next;

free(cur);
}

void STL_Destroy(STLNode** pphead)
{
assert(pphead);
if (*pphead == NULL)
{
return;
}

STLNode* temp = *pphead;
STLNode* cur = *pphead;
while (temp)
{
cur = temp->next;
free(temp);
temp = cur;
}
*pphead = NULL;
}

Take the lead in bidirectional circular linked list

picture:

Header file:

The coolest thing about this linked list is that he can easily find the tail, whether it is a tail plug or a head plug, it is very cool and very convenient. If we want to finish writing this linked list within half an hour, then we can match the tail plug and the head plug. The LTInsert function is used for insertion and multiplexing, and the LTErase function is used for tail deletion and head deletion. That is to say, these two functions are core functions. With them, it becomes a reality to quickly write the linked list.

Tail insertion multiplexing: LTInsert(phead,x);

The multiplexing of header: LTInsert(phead->next,x);

Reuse of tail deletion: LTErase(phead->prev);

Reuse of header deletion: LTErase(phead->next);

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

typedef int DataType;

typedef struct LTNode
{
DataType data;
struct LTNode* prev;
struct LTNode* next;
}LTNode;

LTNode* Init();
LTNode* Malloc(DataType x);
LTNode* LTFind(LTNode* phead, DataType x);
void LTPrintf(LTNode* phead);
void LTPushBack(LTNode* phead, DataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, DataType x);
void LTPopFront(LTNode* phead);
void LTInsert(LTNode* pos, DataType x); //Insert node before pos position
void LTErase(LTNode* pos); //Delete pos position node
void LTDDestroy(LTNode* phead);

Test file:

#define _CRT_SECURE_NO_WARNINGS 1
#include "LTNode.h"

void Test1();

int main()
{
Test1();
return 0;
}

void Test1()
{
LTNode* plist = NULL;
plist = Init();

LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPushBack(plist, 5);
LTPushBack(plist, 6);
LTPrintf(plist);

LTPopBack(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPrintf(plist);

LTPushFront(plist, 10);
LTPushFront(plist, 20);
LTPushFront(plist, 30);
LTPrintf(plist);

LTPopFront(plist);
LTPrintf(plist);

LTNode *pos = LTFind(plist, 10);
LTInsert(pos, 66);
LTPrintf(plist);
LTErase(pos);
LTPrintf(plist);

LTDDestroy(plist);
plist = NULL;

}

Function source file:

#define _CRT_SECURE_NO_WARNINGS 1
#include "LTNode.h"

LTNode* Malloc(DataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
return newnode;
}

LTNode* Init()
{
LTNode* newnode = Malloc(0);

newnode->next = newnode;
newnode->prev = newnode;

return newnode;
}

void LTPrintf(LTNode* phead)
{
assert(phead);

printf("phead<=>");
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
putchar('\\
');
}

void LTPushBack(LTNode* phead, DataType x)
{
assert(phead);

LTNode *newnode = Malloc(x);
LTNode* tail = phead->prev;

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

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

}

void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);

LTNode* tail = phead->prev;
LTNode* newtail = tail->prev;

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

void LTPushFront(LTNode* phead, DataType x)
{
assert(phead);

LTNode* newnode = Malloc(x);
LTNode* old_next = phead->next;

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

newnode->next = old_next;
old_next->prev = newnode;

}

void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);

LTNode* del = phead->next;

phead->next = del->next;
del->next->prev = phead;

free(del);
}

LTNode* LTFind(LTNode* phead, DataType x)
{
assert(phead);
\t
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}

printf("nothing!\\
");
return NULL;
}

void LTInsert(LTNode* pos, DataType x)
{
assert(pos);

LTNode* newnode = Malloc(x);
LTNode* posprev = pos->prev;

posprev->next = newnode;
newnode->prev = posprev;

newnode->next = pos;
pos->prev = newnode;
}

void LTErase(LTNode* pos)
{
assert(pos);

LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;

posprev->next = posnext;
posnext->prev = posprev;
free(pos);
}

void LTDDestroy(LTNode* phead)
{
assert(phead);

LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}

free(cur);
}