The linked list does not require each element to be continuous in the storage space. When creating a new element node, it can be used wherever the space is applied
The purpose of unilateral or mutual connection between nodes is achieved through pointer pointing (single finger: single linked list, mutual finger: double linked list)
Node of single linked list:
struct LNode {
int Data;
struct LNode *next;
};
Node of double linked list:
struct DNode {
int Data;
struct DNode *prior, *next;
};
In the application, typedef can be used to make the code more concise and understandable
Take the single linked list node as an example:
typedef struct LNode {
int Data;
struct LNode *next;
}LNode, *LinkList;
int main () {
LNode testnode; // Define a node
LinkList testlist; // Define a node pointer
return 0;
}
The node pointer defined here can point to the address of the head node. In this way, we only need to record the node pointer, and we can traverse the whole single linked list through the traceability of each node. Similarly, the double linked list is the same
When creating a linked list, there are two ways to write the lead node and the lead node
No leading node: the node pointer testlist points directly to the first node
void init (LinkList &list) { // Initialize linked list: do not take the lead node
list = NULL;
}
void addelem (LinkList &list, LNode *newNode) { // Add a new element node at the end of the table
if(list == NULL) { // The linked list is empty
list = newNode; // The node pointer acting as the linked list points to the new element node
return;
}
LNode *p = list; // If the linked list is not empty, use the temporary pointer p to find its tail node
while(p->next != NULL) p = p->next;
p->next = newNode; // Just connect it
}
int main () {
LinkList testlist;
init(testlist);
LNode *testNode = (LNode*)malloc(sizeof(LNode));
testNode->Data = 1;
testNode->next = NULL;
addelem(testlist, testNode);
return 0;
}
Leading node: the node pointer does not directly point to the first node, but points to a node without actual data (what's the advantage of this?)
void init (LinkList &list) { // Initialize linked list: lead node
list = (LNode*)malloc(sizeof(LNode));
list->next = NULL;
}
void addelem (LinkList &list, LNode *newNode) { // Add a new element node at the end of the table
LNode *p = list;
while(p->next != NULL) p = p->next; // Go back to the last (next is not NULL)
p->next = newNode; // Just connect it
}
void show (LinkList list) { // Output all elements in the linked list
LNode *p = list->next;
while(p != NULL) {
cout << p->Data << " ";
p = p->next;
}
cout << endl;
}
int main () {
LinkList testlist;
init(testlist);
LNode *testNode = (LNode*)malloc(sizeof(LNode));
testNode->Data = 1;
testNode->next = NULL;
addelem(testlist, testNode);
show(testlist);
return 0;
}
In the addelem function, the leading node does not need to judge whether the linked list is empty, while the leading node does not need to, so it can have less code
Looking back at the sequence table, the contents of elements in the sequence table only need to be accessed through subscripts, while the linked list needs to be queried through traversal
Take the lead node as an example:
LNode* findbydata (LinkList list, int data) { // Find by value
LNode *p = list->next; // No, just modify the node here: LNode *p = list;
while(p != NULL) {
if(p->Data == data) return p;
p = p->next;
}
return NULL;
}
LNode* findbysequence (LinkList list, int seq) { // Search by bit
LNode *p = list->next;
while(p != NULL) {
if(--seq == 0) return p;
p = p->next;
}
return NULL;
}
Search by value and search by bit are written in the same way in single linked list and double linked list, but there is a slight difference between the leading node and the non leading node
Compared with the sequence table, the linked list has less time complexity in modifying or deleting intermediate elements. For example, when the sequence table inserts a new element in the middle of the table, all elements after the position need to be moved back to make room for storing new elements. If there are 1000 after the insertion point, the time complexity of inserting a new element will reach O(1000)
The linked list only needs to modify the pointer of the front node and the rear node (the single linked list only needs to modify the next of the front node)
This is the post insertion code of single linked list
void insert (LNode *priorNode, LNode *newNode) { // Back insert
newNode->next = priorNode->next;
priorNode->next = newNode;
}
Logically, after acquiring a node, the single linked list can only perform post insert operation, and cannot be inserted before the node. If you insist on pre insert, you can only obtain the node before the node, and then use post insert... Disguised pre insert, change soup without changing dressing
The double linked list can be inserted either forward or backward due to the addition of a forefinger pointer
For convenience, you can outsource the connection operation between two nodes to make the code clearer
void connect(DNode *a, DNode *b) { // Connect the two nodes passed in
a->next = b;
b->prior = a;
}
// It is possible to modify the header node, and the pointer of the header node needs to be passed in
void frontInsert (DLinkList &list, DNode *rearNode, DNode *newNode) { // Forward insertion
// Judge whether the realnode has a front node. If yes, it should be connected. Otherwise, the prior ity of the newNode should be NULL
if(rearNode->prior != NULL) connect(rearNode->prior, newNode);
else list = newNode; // If there is no front node and you need to insert it, the new node will become the head node
connect(newNode, rearNode); // Connection between new and rear
}
void behindInsert (DNode *priorNode, DNode *newNode) { // Back insert
// Judge whether there is a back node in the priorNode. If yes, connect it
if(priorNode->next != NULL) connect(newNode, priorNode->next);
connect(priorNode, newNode); // Connection between new and prior
}
The basic idea of the linked list is almost clear. Other functions on the linked list, such as deletion, are just the reverse idea of insertion, so I won't repeat it
In the application, when the restricted insertion can only be at the end of the table and the deletion can only be at the head, the linked list is equivalent to a queue. Moreover, when the restricted insertion and deletion can only be at the end of the table, the linked list is a stack
Title Description: some n people form a circle and arrange numbers in sequence. Start counting from the first person (counting from 1 to 3). Those who report to 3 quit the circle and ask the one who left the original number.
In case of this problem, you need to cycle the linked list many times, which leads to the expansion idea of the linked list: circular linked list
The writing method of circular linked list only needs to connect the tail node with the header node
However, when using the circular linked list, the writing method of the leading node is more complex. When traversing to the end of the table and returning to the header, you need to skip the invalid leading node. Therefore, when using the circular linked list idea to solve the problem, it is recommended not to take the lead node circular linked list
Finally, attach the test code:
Non leading node single linked list
#include<iostream>
using namespace std;
typedef struct LNode {
int Data;
struct LNode *next;
}LNode, *LinkList;
void init (LinkList &list) { // Initialize linked list: do not take the lead node
list = NULL;
}
void addelem (LinkList &list, LNode *newNode) { // Add a new element node at the end of the table
if(list == NULL) { // The linked list is empty
list = newNode; // The node pointer acting as the linked list points to the new element node
return;
}
LNode *p = list; // If the linked list is not empty, use the temporary pointer p to find its tail node
while(p->next != NULL) p = p->next;
p->next = newNode; // Just connect it
}
void show (LinkList list) { // Print all element data
LNode *p = list;
while(p != NULL) {
cout << p->Data << " ";
p = p->next;
}
cout << endl;
}
LNode* findbydata (LinkList list, int data) { // Find by value
LNode *p = list;
while(p != NULL) {
if(p->Data == data) return p;
p = p->next;
}
return NULL;
}
LNode* findbysequence (LinkList list, int seq) { // Search by bit
LNode *p = list;
while(p != NULL) {
if(--seq == 0) return p;
p = p->next;
}
return NULL;
}
void insertNode (LNode *priorNode, LNode *newNode) { // Back insert
newNode->next = priorNode->next;
priorNode->next = newNode;
}
void deleteNode (LinkList &list, LNode *delNode) { // Delete Vertex
LNode *p = list;
if(p == delNode) { // If the node is deleted, it will be the first one
list = p->next;
} else { // Otherwise, you need to find out whose next node is the node that should be deleted to connect the front and back
while(p->next != delNode && p->next != NULL) p = p->next;
p->next = delNode->next;
}
free(delNode);
}
int main () {
LinkList testlist;
init(testlist);
// Insert 233, 250, 666 at the end of the table
LNode *testNode = (LNode*)malloc(sizeof(LNode));
testNode->Data = 233;
testNode->next = NULL;
addelem(testlist, testNode);
testNode = (LNode*)malloc(sizeof(LNode));
testNode->Data = 250;
testNode->next = NULL;
addelem(testlist, testNode);
testNode = (LNode*)malloc(sizeof(LNode));
testNode->Data = 666;
testNode->next = NULL;
addelem(testlist, testNode);
show(testlist); // display
// Find by value + insert = = insert by value
testNode = (LNode*)malloc(sizeof(LNode));
testNode->Data = 999;
testNode->next = NULL;
insertNode(findbydata(testlist, 666), testNode);
show(testlist);
// Search by bit + insert = = insert by bit
testNode = (LNode*)malloc(sizeof(LNode));
testNode->Data = 857;
testNode->next = NULL;
insertNode(findbysequence(testlist, 3), testNode);
show(testlist);
// Find by value + delete = = delete by value
deleteNode(testlist, findbydata(testlist, 250));
show(testlist);
// Search by bit + delete = = delete by bit
deleteNode(testlist, findbysequence(testlist, 1));
show(testlist);
// cin.get();
return 0;
}
Single linked list of leading nodes (6 lines less than single linked list of non leading nodes)
#include<iostream>
using namespace std;
typedef struct LNode {
int Data;
struct LNode *next;
}LNode, *LinkList;
void init (LinkList &list) { // Initialize linked list: lead node
list = (LNode*)malloc(sizeof(LNode));
list->next = NULL;
}
void addelem (LinkList &list, LNode *newNode) { // Add a new element node at the end of the table
LNode *p = list; // Tracing tail node
while(p->next != NULL) p = p->next;
p->next = newNode; // Just connect it
}
void show (LinkList list) { // Print all element data
LNode *p = list->next;
while(p != NULL) {
cout << p->Data << " ";
p = p->next;
}
cout << endl;
}
LNode* findbydata (LinkList list, int data) { // Find by value
LNode *p = list->next;
while(p != NULL) {
if(p->Data == data) return p;
p = p->next;
}
return NULL;
}
LNode* findbysequence (LinkList list, int seq) { // Search by bit
LNode *p = list->next;
while(p != NULL) {
if(--seq == 0) return p;
p = p->next;
}
return NULL;
}
void insertNode (LNode *priorNode, LNode *newNode) { // Back insert
newNode->next = priorNode->next;
priorNode->next = newNode;
}
void deleteNode (LinkList &list, LNode *delNode) { // Delete Vertex
LNode *p = list;
// The former node of the node to be deleted is traced from the beginning
while(p->next != delNode && p->next != NULL) p = p->next;
p->next = delNode->next;
free(delNode);
}
int main () {
LinkList testlist;
init(testlist);
// Insert 233, 250, 666 at the end of the table
LNode *testNode = (LNode*)malloc(sizeof(LNode));
testNode->Data = 233;
testNode->next = NULL;
addelem(testlist, testNode);
testNode = (LNode*)malloc(sizeof(LNode));
testNode->Data = 250;
testNode->next = NULL;
addelem(testlist, testNode);
testNode = (LNode*)malloc(sizeof(LNode));
testNode->Data = 666;
testNode->next = NULL;
addelem(testlist, testNode);
show(testlist); // display
// Find by value + insert = = insert by value
testNode = (LNode*)malloc(sizeof(LNode));
testNode->Data = 999;
testNode->next = NULL;
insertNode(findbydata(testlist, 666), testNode);
show(testlist);
// Search by bit + insert = = insert by bit
testNode = (LNode*)malloc(sizeof(LNode));
testNode->Data = 857;
testNode->next = NULL;
insertNode(findbysequence(testlist, 3), testNode);
show(testlist);
// Find by value + delete = = delete by value
deleteNode(testlist, findbydata(testlist, 250));
show(testlist);
// Search by bit + delete = = delete by bit
deleteNode(testlist, findbysequence(testlist, 1));
show(testlist);
// cin.get();
return 0;
}
Non leading node double linked list
#include<iostream>
using namespace std;
typedef struct DNode { // Double linked list
int Data;
struct DNode *next, *prior;
}DNode, *DLinkList;
void init (DLinkList &list) { // Initialize linked list: do not take the lead node
list = NULL;
}
void addelem (DLinkList &list, DNode *newNode) { // Add a new element node at the end of the table
if(list == NULL) { // The linked list is empty
list = newNode; // The node pointer acting as the linked list points to the new element node
return;
}
DNode *p = list; // If the linked list is not empty, use the temporary pointer p to find its tail node
while(p->next != NULL) p = p->next;
p->next = newNode; // Just connect it
newNode->prior = p;
}
void show (DLinkList list) {
DNode *p = list;
while(p != NULL) {
cout << p->Data << " ";
p = p->next;
}
cout << endl;
}
DNode* findbydata (DLinkList list, int data) { // Find by value
DNode *p = list;
while(p != NULL) {
if(p->Data == data) return p;
p = p->next;
}
return NULL;
}
DNode* findbysequence (DLinkList list, int seq) { // Search by bit
DNode *p = list;
while(p != NULL) {
if(--seq == 0) return p;
p = p->next;
}
return NULL;
}
void connect(DNode *a, DNode *b) { // Connect the two nodes passed in
a->next = b;
b->prior = a;
}
// It is possible to modify the header node, and the pointer of the header node needs to be passed in
void frontInsert (DLinkList &list, DNode *rearNode, DNode *newNode) { // Forward insertion
// Judge whether the realnode has a front node. If yes, it should be connected. Otherwise, the prior ity of the newNode should be NULL
if(rearNode->prior != NULL) connect(rearNode->prior, newNode);
else list = newNode; // If there is no front node and you need to insert it, the new node will become the head node
connect(newNode, rearNode); // Connection between new and rear
}
void behindInsert (DNode *priorNode, DNode *newNode) { // Back insert
// Judge whether there is a back node in the priorNode. If yes, connect it
if(priorNode->next != NULL) connect(newNode, priorNode->next);
connect(priorNode, newNode); // Connection between new and prior
}
// It is possible to modify the header node, and the pointer of the header node needs to be passed in
void deleteNode (DLinkList &list, DNode *delNode) { // Delete Vertex
if(delNode->prior != NULL && delNode->next != NULL) { // Both front and rear nodes exist, connecting the front and rear nodes
connect(delNode->prior, delNode->next);
} else if(delNode->prior != NULL && delNode->next != NULL){ // There are only front nodes
delNode->prior->next = NULL; // The next of the front node is NULL
} else if(delNode->prior == NULL && delNode->next != NULL){ // Only post nodes exist
list = delNode->next;
}
free(delNode);
}
int main () {
DLinkList testlist;
init(testlist);
DNode *testNode = (DNode*)malloc(sizeof(DNode));
testNode->Data = 233;
testNode->prior = testNode->next = NULL;
addelem(testlist, testNode);
testNode = (DNode*)malloc(sizeof(DNode));
testNode->Data = 250;
testNode->prior = testNode->next = NULL;
addelem(testlist, testNode);
testNode = (DNode*)malloc(sizeof(DNode));
testNode->Data = 666;
testNode->prior = testNode->next = NULL;
addelem(testlist, testNode);
show(testlist); // display
// Find by value + insert = = insert by value
testNode = (DNode*)malloc(sizeof(DNode));
testNode->Data = 99;
testNode->prior = testNode->next = NULL;
frontInsert(testlist, findbydata(testlist, 666), testNode); // Forward interpolation
testNode = (DNode*)malloc(sizeof(DNode));
testNode->Data = 999;
testNode->prior = testNode->next = NULL;
behindInsert(findbydata(testlist, 666), testNode); // Back interpolation
show(testlist);
// Search by bit + insert = = insert by bit
testNode = (DNode*)malloc(sizeof(DNode));
testNode->Data = 857;
testNode->prior = testNode->next = NULL;
behindInsert(findbysequence(testlist, 3), testNode);
show(testlist);
// Find by value + delete = = delete by value
deleteNode(testlist, findbydata(testlist, 250));
show(testlist);
// //Search by bit + delete = = delete by bit
deleteNode(testlist, findbysequence(testlist, 1));
show(testlist);
// cin.get();
return 0;
}
Double linked list of leading nodes (8 lines less than double linked list of non leading nodes)
#include<iostream>
using namespace std;
typedef struct DNode { // Double linked list
int Data;
struct DNode *next, *prior;
}DNode, *DLinkList;
void init (DLinkList &list) { // Initialize linked list: do not take the lead node
DNode *testNode = (DNode*)malloc(sizeof(DNode));
testNode->prior = testNode->next = NULL;
}
void addelem (DLinkList &list, DNode *newNode) { // Add a new element node at the end of the table
DNode *p = list; // Tracing tail node
while(p->next != NULL) p = p->next;
p->next = newNode; // Just connect it
newNode->prior = p;
}
void show (DLinkList list) {
DNode *p = list->next;
while(p != NULL) {
cout << p->Data << " ";
p = p->next;
}
cout << endl;
}
DNode* findbydata (DLinkList list, int data) { // Find by value
DNode *p = list->next;
while(p != NULL) {
if(p->Data == data) return p;
p = p->next;
}
return NULL;
}
DNode* findbysequence (DLinkList list, int seq) { // Search by bit
DNode *p = list->next;
while(p != NULL) {
if(--seq == 0) return p;
p = p->next;
}
return NULL;
}
void connect(DNode *a, DNode *b) { // Connect the two nodes passed in
a->next = b;
b->prior = a;
}
void frontInsert (DNode *rearNode, DNode *newNode) { // Forward insertion
// The leading node writing method does not need to judge whether there is a front node. There is always the leading but invalid node as the front node
connect(rearNode->prior, newNode);
connect(newNode, rearNode); // Connection between new and rear
}
void behindInsert (DNode *priorNode, DNode *newNode) { // Back insert
// Judge whether there is a back node in the priorNode. If yes, connect it
if(priorNode->next != NULL) connect(newNode, priorNode->next);
connect(priorNode, newNode); // Connection between new and prior
}
void deleteNode (DNode *delNode) { // Delete Vertex
if(delNode->next != NULL) { // Post node exists
connect(delNode->prior, delNode->next);
} else { // No post node exists
delNode->prior->next = NULL; // Just disconnect from the previous node
}
free(delNode);
}
int main () {
DLinkList testlist;
init(testlist);
DNode *testNode = (DNode*)malloc(sizeof(DNode));
testNode->Data = 233;
testNode->prior = testNode->next = NULL;
addelem(testlist, testNode);
testNode = (DNode*)malloc(sizeof(DNode));
testNode->Data = 250;
testNode->prior = testNode->next = NULL;
addelem(testlist, testNode);
testNode = (DNode*)malloc(sizeof(DNode));
testNode->Data = 666;
testNode->prior = testNode->next = NULL;
addelem(testlist, testNode);
show(testlist); // display
// Find by value + insert = = insert by value
testNode = (DNode*)malloc(sizeof(DNode));
testNode->Data = 99;
testNode->prior = testNode->next = NULL;
frontInsert(findbydata(testlist, 666), testNode); // Forward interpolation
testNode = (DNode*)malloc(sizeof(DNode));
testNode->Data = 999;
testNode->prior = testNode->next = NULL;
behindInsert(findbydata(testlist, 666), testNode); // Back interpolation
show(testlist);
// Search by bit + insert = = insert by bit
testNode = (DNode*)malloc(sizeof(DNode));
testNode->Data = 857;
testNode->prior = testNode->next = NULL;
behindInsert(findbysequence(testlist, 3), testNode);
show(testlist);
// Find by value + delete = = delete by value
deleteNode(findbydata(testlist, 250));
show(testlist);
// //Search by bit + delete = = delete by bit
deleteNode(findbysequence(testlist, 1));
show(testlist);
// cin.get();
return 0;
}
Exercise code (circular linked list)
Using the circular single linked list of non leading nodes to do this problem only needs two operations: addition and deletion
#include<iostream>
using namespace std;
typedef struct people {
int number;
struct people *next;
}People, *Crowd;
void out (People *prior, People *del) { // del quit the circle
prior->next = del->next;
free(del);
}
int main () {
Crowd p = (People*)malloc(sizeof(People));
p->number = 1;
p->next = p; // Self reference
int n;
cin >> n;
// In the following for loop, p points to the last bit
for(int i = 2; i <= n; i ++) {
People *temp = (People*)malloc(sizeof(People));
temp->number = i;
temp->next = p->next; // The next of the new last bit points to position 1 (p was originally the last bit, and his next is position 1)
p = p->next = temp; // Update the original last next and the new last
}
p = p->next; // p another step back is position 1 of the circle
int call = 1;
while(p->next != p) {
call++;
if(call == 3) { // Call 3 to quit the circle
call = 1;
out(p, p->next);
}
p = p->next;
}
cout << p->number;
return 0;
}
above.