catalogue
4, Bidirectional circular linked list
3. Forward traversal and reverse traversal
1, Single linked list
Each data is stored in nodes, and the single linked list is responsible for connecting these nodes. (mainly using * next pointer)
1. Storage mode
Starting from the root node (the root node may not store elements), use the * next pointer to point to the address of the following element, and the * next of the following element continues to point to the later element, and so on. (the malloc function is used to dynamically allocate memory space when adding or inserting elements) the head pointer points to the root and the tail pointer points to the last node for easy insertion and deletion.
//Node structure
typedef struct Node
{
int data; //Data domain
struct Node* next; //Pointer field
}Node;
Node* head;
Node* tail;2. Insert
The * next of the previous element is disconnected and points to the inserted element, and the * next of the inserted element points to the subsequent element to complete the "squeeze in" insertion.
//Insert element
void Insert(int index, int num)
{
int i = 0;
if (index < getLength() && index >= 0) //Insert subscript valid
{
Node* s = (Node*)malloc(sizeof(Node)), * p = head;
for (i = 0; i < index; i++)
p = p->next;
s->data = num; //Inserted element value
s->next = p->next; //S - > back
p->next = s; //Front - > s
}
else
printf("Not in interpolation range!");
}3. Delete
The * next of the element in front of the element to be deleted is disconnected, pointing to the element behind the element to be deleted to free up the space of the element to be deleted. (the memory allocated by malloc needs to be released)
//Delete Vertex (there must be external variables to temporarily save the node to be deleted)
//If you delete a head node, you can directly point the head to the following node
void Delete_Node(int index)
{
int i = 0;
Node* p = head, * s = NULL;
if (index < getLength() && index >= 0) //Delete subscript valid
{
for (i = 0; i < index; i++)
p = p->next; //Move to previous
s = p->next; //Node to delete
p->next = p->next->next; //Front node next - > rear node (skip the node to be deleted)
free(s);
}
else
printf("There is no node with this subscript!\n");
}Total code:
//Single linked list
//Dynamic memory allocation malloc function: (specified pointer type) malloc (number of bytes to allocate)
//The head node saves the head of the linked list and can perform a series of operations (such as adding) at the tail node. p represents a dynamic pointer
#include <stdio.h>
#include <malloc.h>
int i = 0;
//Node structure
typedef struct Node
{
int data; //Data domain
struct Node* next; //Pointer field
}Node;
Node* head;
Node* tail;
//Initialize linked list
void Init_List()
{
//Initialize linked list
head = (Node*)malloc(sizeof(Node));
tail = (Node*)malloc(sizeof(Node));
head = tail;
}
//Create node
void Add_Node(int Data)
{
Node* p = (Node*)malloc(sizeof(Node));
p->data = Data;
p->next = NULL;
//Pointer backward
tail->next = p;
tail = p;
}
//Get linked list length
int getLength()
{
int num = 0;
Node* p = head->next; //The first data is stored in head - > next
while (p)
{
num++;
p = p->next;
}
return num;
}
//Traversal linked list
void Print()
{
Node* p = head->next; //The first data is stored in head - > next
while (p)
{
printf("%d\n", p->data);
p = p->next;
}
}
//Insert element
void Insert(int index, int num)
{
int i = 0;
if (index < getLength() && index >= 0) //Insert subscript valid
{
Node* s = (Node*)malloc(sizeof(Node)), * p = head;
for (i = 0; i < index; i++)
p = p->next;
s->data = num; //Inserted element value
s->next = p->next; //S - > back
p->next = s; //Front - > s
}
else
printf("Not in interpolation range!");
}
//Delete Vertex (there must be external variables to temporarily save the node to be deleted)
//If you delete a head node, you can directly point the head to the following node
void Delete_Node(int index)
{
int i = 0;
Node* p = head, * s = NULL;
if (index < getLength() && index >= 0) //Delete subscript valid
{
for (i = 0; i < index; i++)
p = p->next; //Move to previous
s = p->next; //Node to delete
p->next = p->next->next; //Front node next - > rear node (skip the node to be deleted)
free(s);
}
else
printf("There is no node with this subscript!\n");
}
//Empty linked list
void Clear_List()
{
Node* p = head->next, * q;
while (p)
{
q = p->next;
free(p);
p = q;
}
head->next = NULL;
}
int main()
{
//Initialize linked list
Init_List();
//Create linked list
for (i = 0; i < 5; i++)
{
Add_Node(i);
}
//Insert Knot
Insert(0, 5);
//Delete node (second deletion note: position change)
Delete_Node(0);
//Empty linked list
Clear_List();
//ergodic
Print();
return 0;
}
II. Static linked list
Although large memory space needs to be allocated for storage in the form of array, it is easy to insert / delete. There is no need to move the array elements, and only change the cursor (cur) point.
1. Storage mode
Create an array (index is the subscript and cur is the cursor)
Cur (cursor): store the index of the previous element and connect through it.
The whole linked list is divided into two parts: 1. Value linked list (storing elements) 2. Standby linked list (not storing elements)
cur of the first element (index=0): stores the first element of the standby linked list.
cur of tail element (index=MAXSIZE-1): the first element of the value linked list.
Linked list composition: 1. Standby linked list headed by the first element; 2. A value linked list headed by tail elements.
//Static linked list structure
typedef struct
{
int data; //data
int cur; //cursor
}StaticList;
StaticList L[MAXSIZE];2. Insert
Move only cursors, not elements.
//Insert linked list
void Insert(int index, int num)
{
int pre = MAXSIZE - 1;
if (index <= 0 || index > L[0].cur) //Invalid insertion range (the first and last elements do not store data)
{
printf("%d Insert Error!\n", num);
return;
}
//Move to previous element (valid element)
for (i = 1; i < index; i++)
pre = L[pre].cur;
L[0].cur = L[index].cur; //The cursor of the first element of the linked list points to the first element of the standby linked list
L[index].data = num;
}3. Delete
The deleted element is used as the first element of the standby list. Its cursor connects the first element of the original standby list, and the first element of the original standby list becomes the second element (moving backward).
//Delete the linked list (demote the element to be deleted to become the first element of the standby linked list)
void Delete(int index)
{
int pre = MAXSIZE - 1, j;
if (index < 1 || index >= L[0].cur)
{
printf("Invalid subscript to delete!\n");
return;
}
for (i = 1; i <= index - 1; i++)
pre = L[pre].cur; //Move to the previous position to be deleted (with element bits)
L[index].cur = L[0].cur; //1. The cursor points to the original standby element (the deleted element is the first of the standby element)
L[0].cur = index; //2. Update the first element of the standby linked list (deleted element)
L[pre].cur = index; //3. Connect the previous element and the next element (cursor)
}4. Traversal
Start traversal from index = maxsize-1 (from the tail element), because the cur of the tail element contains the first element of the valid linked list.
//Traversal linked list
void Traverse()
{
int cur;
cur = L[MAXSIZE - 1].cur; //Points to the first element of a valid linked list
for (i = 1; i < L[0].cur; i++) //From the first to the last (the first element of the standby linked list is the next element of the last element)
{
printf("%d\n", L[cur].data);
cur = L[cur].cur; //Continue to move backward in the valid linked list
}
}Total code:
//Static linked list
//During insertion / deletion, only cursors are modified and nodes are not moved
//The cursor stores the subscript. The previous element cursor stores the subscript of the next element
//First element cursor: Store the subscript of the first element of the standby linked list
//Last element cursor: the subscript of the first element in the element list
//Take the valid element as a loop and start with the pre=MAXSIZE-1 flag because l [maxsize-1] Cur points to the first element of the valid linked list, which is equivalent to a loop in the valid linked list
#include <stdio.h>
#define MAXSIZE 20
int i = 0;
typedef struct
{
int data;
int cur;
}StaticList;
StaticList L[MAXSIZE];
//Linked list initialization
void List_Init()
{
//Initialize cursor
for (i = 0; i < MAXSIZE; i++)
{
L[i].cur = i + 1; //The cursor points to the next
}
L[MAXSIZE - 1].cur = 1; //Cursor of the last element (valid element)
}
//Obtain the subscript according to the cursor (not used here)
int getIndex(int Cur)
{
for (i = 0; i < MAXSIZE; i++)
{
if (L[i].cur == Cur) //Find the element corresponding to the cursor
return i; //Return subscript
}
return -1; //Can't find
}
//Get length
int getLength()
{
int num = 0;
i = L[MAXSIZE - 1].cur;
if (L[0].cur == L[MAXSIZE - 1].cur) //No element
return 0;
while (i < L[0].cur)
{
i = L[i].cur;
num++;
}
return num;
}
//Insert linked list
void Insert(int index, int num)
{
int pre = MAXSIZE - 1;
if (index <= 0 || index > L[0].cur) //Invalid insertion range (the first and last elements do not store data)
{
printf("%d Insert Error!\n", num);
return;
}
//Move to previous element (valid element)
for (i = 1; i < index; i++)
pre = L[pre].cur;
L[0].cur = L[index].cur; //The cursor of the first element of the linked list points to the first element of the standby linked list
L[index].data = num;
L[0].cur = L[index].cur; //Update alternate linked list
}
//Delete the linked list (demote the element to be deleted to become the first element of the standby linked list)
void Delete(int index)
{
int pre = MAXSIZE - 1, j;
if (index < 1 || index >= L[0].cur)
{
printf("Invalid subscript to delete!\n");
return;
}
for (i = 1; i <= index - 1; i++)
pre = L[pre].cur; //Move to the previous position to be deleted (with element bits)
L[index].cur = L[0].cur; //1. The cursor points to the original standby element (the deleted element is the first of the standby element)
L[0].cur = index; //2. Update the first element of the standby linked list (deleted element)
L[pre].cur = index; //3. Connect the previous element and the next element (cursor)
}
//Traversal linked list
void Traverse()
{
int cur;
cur = L[MAXSIZE - 1].cur; //Points to the first element of a valid linked list
for (i = 1; i < L[0].cur; i++) //From the first to the last (the first element of the standby linked list is the next element of the last element)
{
printf("%d\n", L[cur].data);
cur = L[cur].cur; //Continue to move backward in the valid linked list
}
}
int main()
{
List_Init(); //Linked list initialization
printf("Total number of elements before insertion:%d\n", getLength());
Insert(1, 6); //Insert linked list
Insert(2, 8);
Insert(3, 10);
printf("Total number of elements before deletion:%d\n", getLength());
Delete(3);
Delete(2); //Delete linked list
Insert(2, 8);
printf("Total number of elements after deletion:%d\n", getLength());
Traverse();
return 0;
}3, Circular linked list
Circular linked list, as the name suggests, tail connector to realize circulation.
The storage structure is similar to a linked list, with one more head to tail to complete the cycle.
Total code:
//Circular linked list
//With two pointers, one pointing to the head and one pointing to the tail, the tail connects the head to complete the circular linked list
#include <stdio.h>
#include <malloc.h>
int i = 0;
//structural morphology
typedef struct Node
{
int data;
struct Node* next;
}Node;
Node* head; //Head node
Node* tail; //Tail node
Node* t; //Traversal node
//Linked list initialization
void List_Init()
{
head = (Node*)malloc(sizeof(Node)); //Assign address
tail = (Node*)malloc(sizeof(Node)); //Assign address
head->next = tail;
tail->next = head;
}
//Get linked list length
int getLength() {
int num = 0;
Node* L = head;
while (L->next != tail)
{
L = L->next;
num++;
}
return num;
}
//Insert linked list
void Insert(int index, int num)
{
if (index<0 || index>getLength())
{
printf("%d Serial number is out of range\n", num);
return;
}
Node* p = (Node*)malloc(sizeof(Node)), * L;
p->next = NULL;
L = head; //Pointing head
while (L->next != tail) //Move to the front of the tail node (the last valid node)
L = L->next;
L->next = p;
p->data = num;
tail = p->next; //Update tail node
}
//Delete linked list
void Delete(int index)
{
if (index < 0 || index >= getLength())
{
printf("No such serial number\n");
return;
}
Node* L = head, * t;
for (i = 0; i < index; i++)
L = L->next;
t = L->next;
L->next = L->next->next;
free(t);
}
//Traversal linked list
void Traverse()
{
Node* L = head;
while (L->next != tail) //Head tail circulation
{
L = L->next;
printf("%d\n", L->data);
}
}
int main()
{
List_Init(); //Linked list initialization
Insert(0, 0); //Insert linked list
Insert(1, 1);
Insert(2, 2);
Delete(2); //Delete linked list
Delete(1); //Second deletion position change
Traverse(); //Traversal linked list
return 0;
}
4, Bidirectional circular linked list
Advantages of two-way circular linked list: it can complete two-way traversal.
1. Storage method:
Bidirectional: * prior pointer and * next pointer point to the front and rear elements respectively.
Loop: the * prior of the head node points to the tail node, and the * next of the tail node points to the head node.
//Bidirectional circular linked list
typedef struct Node
{
int data;
struct Node* prior;
struct Node* next;
}Node;2. Insert and delete
Insert: one traverses the linked list and the other inserts it (don't enter the linked list at the beginning, scatter it, otherwise it will cycle all the time).
Delete: the next and prior pointers should also be considered.
3. Forward traversal and reverse traversal
Forward traversal: start from the head node and traverse to the tail until it meets the tail node.
Reverse traversal: start from the tail node to the head until it meets the head.
//Forward traversal list
void Traverse()
{
Node* p = head;
printf("Forward traversal:\n");
while (p->next != tail)
{
p = p->next;
printf("%d\n", p->data);
}
}
//Reverse traversal of linked list
void AntiTraverse()
{
Node* p = tail;
printf("Reverse traversal:\n");
while (p->prior != head)
{
p = p->prior;
printf("%d\n", p->data);
}
}Total code:
//Bidirectional circular linked list
//The front and rear pointers connect the front and rear elements, respectively
//Insert: one traverses the linked list and the other inserts it (don't enter the linked list at first, scatter it, otherwise it will cycle all the time)
//Delete: the next and prior pointers should also be considered
#include <stdio.h>
#include <malloc.h>
//Bidirectional circular linked list
typedef struct Node
{
int data;
struct Node* prior;
struct Node* next;
}Node;
Node* head; //head
Node* tail; //tail
int i = 0;
//Linked list initialization
void Init_List()
{
head = (Node*)malloc(sizeof(Node));
tail = (Node*)malloc(sizeof(Node));
head->prior = tail;
head->next = tail;
tail->next = head;
tail->prior = head;
//Assign a value for debugging
tail->data = -2;
head->data = -1;
}
//Get the number of elements
int getLength()
{
int num = 0;
Node* p = head;
while (p->next != tail)
{
p = p->next;
num++;
}
return num;
}
//Linked list insertion
void Insert(int index, int num)
{
if (index<0 || index>getLength())
{
printf("Incorrect subscript insertion!\n");
return;
}
Node* t = (Node*)malloc(sizeof(Node)), * p;
p = head;
for (i = 0; i < index; i++)
{
p = p->next; //Move to previous element
}
t->prior = p;
t->next = p->next;
p->next->prior = t; //This step should be ahead
p->next = t; //This step should be later. The responsible p - > next has changed, and the previous one is meaningless
t->data = num;
}
//Delete linked list
void Delete(int index)
{
if (index < 0 || index >= getLength())
{
printf("Delete subscript incorrect!\n");
return;
}
Node* p = head, * s;
for (i = 0; i < index; i++)
p = p->next;
s = p->next;
p->next->next->prior = p;
p->next = p->next->next;
free(s);
}
//Forward traversal list
void Traverse()
{
Node* p = head;
printf("Forward traversal:\n");
while (p->next != tail)
{
p = p->next;
printf("%d\n", p->data);
}
}
//Reverse traversal of linked list
void AntiTraverse()
{
Node* p = tail;
printf("Reverse traversal:\n");
while (p->prior != head)
{
p = p->prior;
printf("%d\n", p->data);
}
}
int main()
{
Init_List(); //Linked list initialization
Insert(0, 0); //Insert element
Insert(1, 1);
Insert(2, 2);
Delete(2); //Delete element
Traverse(); //forward traversal
AntiTraverse(); //reverse traversal
return 0;
}