Headless one-way non-circular singly linked list, headed two-way circular linked list

Article content

1. The concept and structure of linked list

2. Classification of linked lists

3. Linked list implementation

4. Code

Article directory

1. The concept and structure of linked list

Concept: Linked list is a non-sequential, non-sequential storage structure on a physical storage structure. The logical order of data elements is through the linked list
The pointer link sequence in the .

In reality, in the data structure

Difference between linked list and sequential list

2. Classification of linked lists

In practice, the structure of the linked list is very diverse. There are 8 linked list structures when the following situations are combined:

2.1 One-way or two-way

2.2 Leading or not leading

2.3 Circular or non-cyclic

Although there are so many linked list structures, two structures are most commonly used in practice:

1. Headless one-way acyclic linked list: Simple structure, generally not used to store data alone. In practice, it is more used as other data structures
The substructure of the structure, such as hash bucket, graph adjacency list and so on. In addition, this structure appears a lot in written test interviews.

2. Leading two-way circular linked list: The most complex structure, generally used to store data separately. The linked list data structure used in practice is
Is the lead doubly linked list. In addition, although this structure is complex, after using the code to implement, you will find that the structure will bring
There are many advantages, but the implementation is simple, and we will know when we implement the code later.

3. Linked list implementation

3.1 Headless one-way acyclic singly linked list

1. Main functions

2. Interface implementation

The above is the implementation of each interface of the linked list! ! ! !

3.2 Take the lead in bidirectional circular linked list

1. Main functions

On the basis of understanding the singly linked list, it is much easier to understand the leading bidirectional circular linked list;

2. Interface implementation

4. Code

1. Singly linked list

#pragma once

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



typedef int SLDataType;
typedef struct SListNode
{
SLDataType data;
struct SListNode* next;
}SLTNode;


// print linked list
void SLTPrint(SLTNode* phead);


//Create a new node
SLTNode* BuySListNode(SLDataType x);

// tail plug
void SLTPushBack(SLTNode** pphead, SLDataType x);

//head plug
void SLTPushFront(SLTNode** pphead, SLDataType x);

//Tail delete
void SLTPopBack(SLTNode** pphead);

// header delete
void SLTPopFront(SLTNode** pphead);

//Look for
SLTNode* SLTFind(SLTNode* phead, SLDataType x);

// insert x before pos
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);

// insert x after pos
void SLTInsertAfter(SLTNode* pos, SLDataType x);

// delete pos position
void SLTErase(SLTNode** pphead, SLTNode* pos);

// Delete the last position of pos
void SLTEraseAfter(SLTNode* pos);

//destroy linked list
void SLTDestroy(SLTNode** pphead);

#define _CRT_SECURE_NO_WARNINGS 1

#include "SList.h"



// print linked list
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;

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


//Create a new node
SLTNode* BuySListNode(SLDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("BuySListNode fail");
exit(-1);
}

newnode->data = x;
newnode->next = NULL;

return newnode;
}


// tail plug
void SLTPushBack(SLTNode** pphead, SLDataType x)
{
SLTNode* newnode = BuySListNode(x);

if (*pphead == NULL)
{
//Change the pointer to the structure, so use a secondary pointer
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
//Change the structure, use the structure pointer
tail->next = newnode;
}
}

//head plug
void SLTPushFront(SLTNode** pphead, SLDataType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;

}

//Tail delete
void SLTPopBack(SLTNode** pphead)
{
\t//null
assert(*pphead);

// a node
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}

// more than one node
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;

}


// header delete
void SLTPopFront(SLTNode** pphead)
{
//kong
assert(*pphead);

\t//non empty
SLTNode* newnode = (*pphead)->next;
free(*pphead);
*pphead = newnode;

}


//Look for
SLTNode* SLTFind(SLTNode* phead, SLDataType x)
{
assert(phead);

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

// insert x before pos
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
assert(pphead);
assert(pos);

//head plug
if (*pphead == pos)
{
SLTPushFront(pphead,x);
return;
}
SLTNode* prev = *pphead;
SLTNode* newnode = BuySListNode(x);
while(prev)
{
if (prev->next == pos)
{
prev->next = newnode;
newnode->next = pos;
return;
}
else
{
prev = prev->next;
}
}
}

// insert x after pos
void SLTInsertAfter(SLTNode* pos, SLDataType x)
{
assert(pos);

SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;

}

//SLTNode* posafter = pos->next;
//pos->next = newnode;
//newnode->next = posafter;


// delete pos position
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead);
assert(pos);

if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
    {
prev = prev->next;
    }
prev->next = pos->next;
free(pos);
}

}

// Delete the last position of pos
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);

// check tail node
assert(pos->next);

SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}

//destroy linked list
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;

while (cur)
{
SLTNode* next = cur;
next = cur->next;
free(cur);
cur = next;
}

*pphead = NULL;
}

2. Doubly linked list

#pragma once

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

typedef int LTDataTpye;

typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
\t
LTDataTpye data;

}LTNode;

//Create a new node
LTNode* BuyLTnode(LTDataTpye x);

//initialization
LTNode* LTInit();

// print linked list
void LTPrint(LTNode* phead);

//head plug
void LTPushFront(LTNode* phead, LTDataTpye x);

// header delete
void LTPopFront(LTNode* phead);

// tail plug
void LTPushBack(LTNode* phead, LTDataTpye x);

//Tail delete
void LTPopBack(LTNode* phead);

//Look for
LTNode* LTFind(LTNode* phead, LTDataTpye x);

//insert before pos
void LTInsert(LTNode* pos, LTDataTpye x);

//Eliminate the element at position pos
void LTErase(LTNode* pos);

//destroy linked list
void LTDDestroy(LTNode* phead);

#define _CRT_SECURE_NO_WARNINGS 1
#include "DList.h"


//Create a new node
LTNode* BuyLTnode(LTDataTpye x)
{
LTNode* node = (LTNode *)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("BuyLTNode");
exit(-1);
}
node->data = x;
node->prev = NULL;
node->next= NULL;

return node;
}


//initialization
LTNode* LTInit()
{
LTNode* phead = BuyLTnode(0);

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

return phead;
}

// print linked list
void LTPrint(LTNode* phead)
{
assert(phead);


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

printf("\\
");
}

//head plug
void LTPushFront(LTNode* phead, LTDataTpye x)
{
assert(phead);
    LTNode* newnode = BuyLTnode( x);
LTNode* after = phead->next;

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

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

}


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

LTNode* first = phead->next;
LTNode* second = first->next;

free(first);

phead->next = second;
second->prev = phead;

}

// tail plug
void LTPushBack(LTNode* phead, LTDataTpye x)
{
assert(phead);

LTNode* newnode = BuyLTnode(x);

LTNode* tail = phead->prev;

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

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

}

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

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

free(tail);
first->next = phead;
phead->prev = first;

}

//Look for
LTNode* LTFind(LTNode* phead, LTDataTpye x)
{
assert(phead);

LTNode* cur = phead->next;

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

//insert before pos
void LTInsert(LTNode* pos, LTDataTpye x)
{
assert(pos);

LTNode* first = pos->prev;
LTNode* newnode = BuyLTnode(x);

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

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

}

//Eliminate the element at position pos
void LTErase(LTNode* pos)
{
assert(pos);

LTNode* posprev = pos->prev;
LTNode* posafter = pos->next;
free(pos);

posprev->next = posafter;
posafter->prev = posprev;

}

//destroy linked list
void LTDDestroy(LTNode* phead)
{
assert(phead);

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

}