preface
As mentioned in the previous article, data structures consist of four logical structures and two physical structures, as follows:
- Logical structure
- The collection structure
- Linear structure
- A tree structure
- Graph structure
- The physical structure
- Sequential storage structure
- Chain storage structure
There’s not too much about the collection structure, but I’ll just mention it later when I need it. We know that linear structures have arrays, linked lists, queues, etc., so this article will explain for linked lists.
The list
Linked lists are logically linear, but physically chained. So it’s called linear list chain storage. As the name suggests, the creature should be linked like a chain, which it is.
Without further ado, there are four main types of linked lists:
- Unidirectional linked lists.
- Unidirectional cyclic linked lists. A one-way list is joined end to end.
- Bidirectional linked lists.
- Bidirectional circular linked lists.
node
Nodes are places where data is stored in a linked list. They can be regarded as rings in an iron chain. Nodes are mainly divided into two parts: data domain and pointer domain.
Singly linked list
#import <Foundation/Foundation.h>
#define ERROR 0
#define SUCCESS 1
typedef int hyStatus;
// Define the node structure type
typedef struct Node {
int data; / / data domain
struct Node *next; / / pointer field
}Node;
// Define the list type
typedef Node* LinkList;
// Create a linked list
LinkList InitLinkList(void);
// Add a node
hyStatus addNodeToHeader(LinkList *ll, int data);
// Add a node
hyStatus addNodeToFooter(LinkList ll, int data);
// Insert a node at the specified location
hyStatus addNodeToCustom(LinkList *ll, int data, int index);
// Delete the node at the specified location
hyStatus delNodeWithIndex(int index, LinkList *ll);
// Find the node where some data first appears
int checkIndexInLinkList(LinkList ll, int data);
// Find the data value of the node at index
int checkDataInLinkList(LinkList ll, int index);
// Print the data through the list
void foreachLinkList(LinkList ll);
// Destroy a node variable
hyStatus freeNode(Node *node);
// Destroy a linked list
hyStatus freeLinkList(LinkList *ll);
Copy the code.m file (for convenience, use.m file to write, anyway, OC fully supports C language)
#import "LinkList.h"
// Create a node
Node * InitNode(int data) {
Node *node = malloc(sizeof(Node));
if(! node) {printf("Failed to create Node \n");
return NULL;
}
node->data = data;
node->next = NULL;
return node;
}
// Add a node
hyStatus addToHeader(LinkList *ll, Node *node)
{
node->next = *ll;
*ll = node;
return SUCCESS;
}
// Add a node
hyStatus addToFooter(LinkList ll, Node *node)
{
LinkList p = ll;
while (p->next) {
p = p->next;
}
p->next = node;
return SUCCESS;
}
// Insert a node at the specified location
hyStatus addToCustom(LinkList *ll, Node *node, int index)
{
if (index < 1) {
printf("Index must be at least 1 to indicate insertion into the first position \n");
return ERROR;
}
// If the position to be inserted is the first
if (index == 1) {
node->next = *ll;
*ll = node;
}
else {
LinkList p = *ll;
// The position to insert is the second to last
for (int i = 1; i < index - 1; i++) {
if (p->next) {
// 2----length - 1
p = p->next;
}
else {
// other
printf("Insert position larger than list length \n");
return ERROR;
}
}
node->next = p->next;
p->next = node;
}
return SUCCESS;
}
// Create a linked list
LinkList InitLinkList(a) {
// Create heap space that can hold a Node variable and return the address of this heap space
LinkList ll = malloc(sizeof(Node));
if(! ll) {printf("Failed to create Node space \n");
return NULL;
}
ll->data = 0;
ll->next = NULL;
return ll;
}
// Add a node
hyStatus addNodeToHeader(LinkList *ll, int data)
{
Node *node = InitNode(data);
if (node) {
return addToHeader(ll, node);
}
return ERROR;
}
// Add a node
hyStatus addNodeToFooter(LinkList ll, int data)
{
Node *node = InitNode(data);
if (node) {
return addToFooter(ll, node);
}
return ERROR;
}
// Insert a node at the specified location
hyStatus addNodeToCustom(LinkList *ll, int data, int index)
{
Node *node = InitNode(data);
if (node) {
return addToCustom(ll, node, index);
}
return ERROR;
}
// Delete the node at the specified location
hyStatus delNodeWithIndex(int index, LinkList *ll)
{
if (index < 1) {
printf("The minimum position of the node is 1, index < 1");
return ERROR;
}
Node *node;
if (index == 1) {
if ((*ll)->next) {
node = *ll;
*ll = (*ll)->next;
return freeNode(node);
}
else {
returnfreeNode(*ll); }}else {
// Do not change the first node, do not use *ll
/* node\*ll-->1-->2-->3 */
node = *ll;
Node *p = NULL;
for (int i = 1; i < index; i++) {
if (node->next) {
p = node;
node = node->next;
}
else {
printf("Index to be deleted is larger than the length of the list \n");
returnERROR; }}// Delete the intermediate node
p->next = node->next;
returnfreeNode(node); }}// Find the node where some data first appears
int checkDataInLinkList(LinkList ll, int data)
{
int i = 1;
do {
if (ll->data == data) {
return i;
}
ll = ll->next;
i++;
} while (ll);
return ERROR;
}
int checkIndexInLinkList(LinkList ll, int index)
{
if (index < 1) {
printf("Index cannot be less than 1\n");
return ERROR;
}
/* ll-->1-->2-->3-->4 */
for (int i = 1; i < index; i++) {
if (ll->next) {
ll = ll->next;
}
else {
printf("Index cannot be greater than the total length of the list \n");
returnERROR; }}return ll->data;
}
// Prints data through the list
void foreachLinkList(LinkList ll)
{
do {
printf("--------%d---------\n", ll->data);
ll = ll->next;
} while (ll);
}
// Destroy a node variable
hyStatus freeNode(Node *node) {
node->data = 0;
node->next = NULL;
free(node);
node = NULL;
return SUCCESS;
}
// Destroy a linked list
hyStatus freeLinkList(LinkList *ll) {
Node *node;
while ((*ll)->next) {
// node holds the current node, *ll points to the next node
node = *ll;
*ll = (*ll)->next;
// Release the node
freeNode(node);
}
// Release the last node in *ll where next is empty
return freeNode(*ll);
}
Copy the codeCalled in main.m.
#import "LinkList.h"
int main(int argc, const char * argv[]) {
@autoreleasepool {
// Create a linked list
LinkList ll = InitLinkList();
// Loop to add several nodes
for (int i = 1; i <= 10; i++) {
/ / head interpolation
// addNodeToHeader(&ll, i);
/ / stern interpolation
addNodeToFooter(ll, i);
}
// Iterate over the list
foreachLinkList(ll);
// Insert arbitrarily
printf("=========================\n");
addNodeToCustom(&ll, 28.12);
foreachLinkList(ll);
// Delete the node at the specified location
printf("++++++++++++++++++++++++++\n");
delNodeWithIndex(5, &ll);
foreachLinkList(ll);
// Query a node
int index = checkDataInLinkList(ll, 4);
printf("Location found: %d\n", index);
int data = checkIndexInLinkList(ll, 5);
printf("%d\n = %d\n", data);
}
return 0;
}
Copy the codeThe comments are clearly written and should not require much explanation. Note that the head node is not used in both one-way and circular lists.
Unidirectional cyclic linked lists
As I said, a one-way list is a one-way list that is connected end to end. The diagram below:
Code implementation: a file to write a little trouble, all write main.m file.
#import <Foundation/Foundation.h>
#define ERROR 0
#define SUCCESS 1
typedef int hyStatus;
// Define the node structure type
typedef struct Node {
int data; / / data domain
struct Node *next; / / pointer field
}Node;
// Define the list type
typedef Node* LinkList;
// Create a circular linked list
LinkList createLoopLinkList(void) {
LinkList ll = NULL; // Always point to the list header
LinkList r = NULL; // Always point to the end of the list
int data;
printf("Enter a non-negative integer to create node data to the linked list, enter a negative integer to end the creation \ nlinkList =");
while (1) {
scanf("%d", &data);
if (data < 0) {
break;
}
// Enter the first time
if (ll == NULL) {
ll = malloc(sizeof(Node));
// Increase program robustness
if (ll == NULL) {
exit(0);
}
// Change the pointer
ll->data = data;
ll->next = ll;
r = ll;
}
else {
Node *node = malloc(sizeof(Node));
if (node == NULL) {
break;
}
node->data = data; / / data
node->next = r->next; // r is the tail node, r->next points to the head node, r->next points to the head node
r->next = node; // Add the address of node to r->next. This step connects node to the end of the list, where node is the last node and r is the next-to-last node
r = r->next; // change r back to the last node}}return ll;
}
// Insert a node at the specified location
hyStatus insertNode(LinkList *ll, int data, int index) {
if (index < 1) {
printf("Insert position illegal \n");
return ERROR;
}
// The node to insert
Node *node = malloc(sizeof(Node));
if (node == NULL) {
exit(0);
}
node->data = data;
// Insert in the first position and insert in the last position, the structure of the list is the same, but the meaning is different
// When the last position is inserted, the *ll pointer still points to the head node
/ / insert in the first position, * ll points to be modified for the current insert node, is the newly inserted node at this time, the head of the original node is now the second, and this is why the cause of the parameters to pass * ll
if (index == 1) {
// First, find the last node
Node *lastNode = *ll;
while(lastNode->next ! = *ll) { lastNode = lastNode->next; }// The last node is found and the insert is started
node->next = *ll;
lastNode->next = node;
// Change the position of the head node to the newly inserted node
*ll = node;
}
else {
// If you want to insert a third position, you need to find a second position
// Since tNode defaults to the first position, you only need to loop through index-2 times to find the position before index
Node *tNode = *ll;
for (int i = 1; i < index - 1; i++) {
if (tNode->next == *ll) {
printf("Insert position larger than list length \n");
return ERROR;
}
tNode = tNode->next;
}
node->next = tNode->next;
tNode->next = node;
}
return SUCCESS;
}
// Delete the node at the specified location
hyStatus deleteNode(LinkList *ll, int index) {
if (index < 1) {
printf("Delete location illegal \n");
return ERROR;
}
// Delete the first node
if (index == 1) {
// First, find the last node
Node *lastNode = *ll;
while(lastNode->next ! = *ll) { lastNode = lastNode->next; }// The last node is found and the first node is deleted
lastNode->next = (*ll)->next;
(*ll)->data = 0;
(*ll)->next = NULL;
free(*ll);
// Change the position of the head node to the original second node
*ll = lastNode->next;
}
else {
// If you want to delete the third location, you need to find the second location
// Since tNode defaults to the first position, you only need to loop through index-2 times to find the position before index
Node *tNode = *ll;
for (int i = 1; i < index - 1; i++) {
tNode = tNode->next;
if (tNode->next == *ll) {
printf("Deleted position larger than list length \n");
returnERROR; }}// Start deleting
Node *delNode = tNode->next;
tNode->next = delNode->next;
delNode->data = 0;
delNode->next = NULL;
free(delNode);
}
return SUCCESS;
}
// Query the position of a value in the list
int findNode(LinkList ll, int data) {
Node *p = ll;
int index = 1;
do {
if (p->data == data) {
return index;
}
p = p->next;
index++;
} while(p ! = ll);printf("This node \n was not found");
return ERROR;
}
// Loop through the list
void foreachLinkList(LinkList ll) {
Node *p = ll;
do {
printf("%-5d", p->data);
p = p->next;
} while(p ! = ll);printf("\n");
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
// Create a linked list
LinkList ll = createLoopLinkList();
foreachLinkList(ll);
// Insert the node
printf("++++++++++++++++++++++++++\n");
insertNode(&ll, 0.1);
foreachLinkList(ll);
// Delete a node
printf("--------------------------\n");
deleteNode(&ll, 1);
foreachLinkList(ll);
// Query a node
printf("==========================\n");
printf("Location found: %d\n", findNode(ll, 10));
}
return 0;
}
Copy the codeTwo-way linked list
A problem can be found in the above one-way linked list, that is, if you want to know the address of a node, you must first find the previous node, and then obtain the address of the node through the next of the previous node. At the same time, we can not get the address of the previous node through the current node, which will feel very troublesome during the operation.
And then to talk about the bidirectional linked list is a good solution to this problem, the node of the one-way linked list is only to save the data and the address of the next node, so can we save the address of the previous node? The answer is yes. The specific style is shown below:
- Data domains are used to store data.
- The precursor saves the address of the previous node.
- Then save the address of the next node.
The head node
Before Posting the code, let’s talk about the head node. From the above unidirectional linked list code, we can know that whether the node is inserted or deleted, it is inevitable to determine whether the position to be inserted is the first one. Is the node to be deleted the first node? This is because the first node needs to perform different operations than the other nodes when inserting and deleting.
So how do you make the first node behave the same as the others? This is where the concept of a head node is introduced. The head node should be created by default when the list is created, but it should not store data. In this case, the first node is essentially the second node, because the real first node is the head node, which ensures that the first node performs the same operation as the other nodes when inserting and removing nodes.
Just say not practice false handle, look at the code:
#import <Foundation/Foundation.h>
#define ERROR 0
#define SUCCESS 1
typedef int hyStatus;
typedef struct _Node {
int data;
struct _Node *frontNode; / / precursor
struct _Node *nextNode; / / the subsequent
} Node;
typedef Node* LinkList; // Two-way linked list
// The head node is not used in the one-way list, so use the head node once in the two-way list
// Create a linked list
LinkList createLinkList(a) {
// The newly created node is the 'head' node
LinkList ll = malloc(sizeof(Node));
// Create space successfully by default, do not consider the failure to create space 😄
ll->data = 0; // Save the number of nodes
ll->frontNode = NULL;
ll->nextNode = NULL;
// Add a node
Node *lastNode = ll; // Record the last node
int data = 0;
printf("Please enter node data, negative number indicates end of input :\n");
while (1) {
scanf("%d", &data);
if (data < 0) {
break;
}
// Create a node
Node *node = malloc(sizeof(Node));
node->data = data;
node->nextNode = NULL;
// Add nodes to the end of the list
node->frontNode = lastNode;
lastNode->nextNode = node;
lastNode = node;
// Number of nodes in the list ++
ll->data++;
}
return ll;
}
// Insert a node
hyStatus insertNode(LinkList *ll, int data, int index) {
if (index < 1 || index > (*ll)->data + 1) {
printf("Insert in illegal position \n");
return ERROR;
}
// Create a node
Node *node = malloc(sizeof(Node));
node->data = data;
node->frontNode = NULL;
node->nextNode = NULL;
// Start the insert, because the head node exists, insert the first position is not much different from the other positions
Node *p = *ll;
for (int i = 1; i < index; i++) {
// To be on the safe side, add this judgment
if(p->nextNode) { p = p->nextNode; }}// Start inserting nodes
if (p->nextNode) {
node->nextNode = p->nextNode;
p->nextNode->frontNode = node;
}
p->nextNode = node;
node->frontNode = p;
// List length ++
(*ll)->data++;
return SUCCESS;
}
// Delete a node
hyStatus deleteNode(LinkList *ll, int index) {
if (index < 1 || index > (*ll)->data) {
printf("Deleted location is illegal \n");
return ERROR;
}
Node *p = *ll;
for (int i = 1; i < index; i++) {
if(p->nextNode) { p = p->nextNode; }}// Start deleting
Node *delNode = p->nextNode; // Save the node to be deleted
p->nextNode = delNode->nextNode;
// Delete the last node that does not have nextNode
if (delNode->nextNode) {
delNode->nextNode->frontNode = p;
}
// Start releasing the node to be deleted
delNode->data = 0;
delNode->nextNode = NULL;
delNode->frontNode = NULL;
// List length --
(*ll)->data--;
return SUCCESS;
}
// Query a node
int findNode(LinkList ll, int data) {
Node *p = ll;
for (int i = 1; i <= ll->data; i++) {
// Since p initially refers to the header node, it moves back one node
if((p = p->nextNode)) {
// Check if it is found
if (p->data == data) {
returni; }}else {
printf("Not found \n");
return 0; }}printf("Not found \n");
return 0;
}
// Iterate over the list
void foreachLinkList(LinkList ll) {
Node *p = ll->nextNode; // The first node
while (p) {
printf("%-5d", p->data);
p = p->nextNode;
}
printf("\n");
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
// Create a linked list
LinkList ll = createLinkList();
foreachLinkList(ll); // Iterate over the list
// Insert the node
printf("+++++++++++++++++++++++++++++++++++\n");
insertNode(&ll, 0.4);
foreachLinkList(ll);
// Delete a node
printf("-----------------------------------\n");
deleteNode(&ll, 4);
foreachLinkList(ll);
// Query a node
printf("===================================\n");
printf("Query location: %d\n", findNode(ll, 7));
}
return 0;
}
Copy the codeBidirectional circular linked lists
It’s a little ugly, but I’m sure it’s pretty easy to understand after looking at the above.
For head nodes, the first node in the figure above is the head node, and the second node is the first node that needs to be used on demand.
Bidirectional circular linked list code implementation:
#import <Foundation/Foundation.h>
#define ERROR 0
#define SUCCESS 1
typedef int hyStatus;
typedef struct _Node {
int data;
struct _Node *frontNode; / / precursor
struct _Node *nextNode; / / the subsequent
} Node;
typedef Node* LinkList; // Two-way linked list
// MARK: - Head is not used in both lists, so use head in both lists, 😂
// Create a linked list
LinkList createLinkList(a) {
// MARK: - Copy everything, end to end
// The newly created node is the 'head' node
LinkList ll = malloc(sizeof(Node));
// Create space successfully by default, do not consider the failure to create space 😄
ll->data = 0; // Save the number of nodes
ll->frontNode = NULL;
ll->nextNode = NULL;
// Add a node
Node *lastNode = ll; // Record the last node
int data = 0;
printf("Please enter node data, negative number indicates end of input :\n");
while (1) {
scanf("%d", &data);
if (data < 0) {
break;
}
// Create a node
Node *node = malloc(sizeof(Node));
node->data = data;
node->nextNode = NULL;
// Add nodes to the end of the list
node->frontNode = lastNode;
lastNode->nextNode = node;
lastNode = node;
// Number of nodes in the list ++
ll->data++;
}
// end to end
lastNode->nextNode = ll;
ll->frontNode = lastNode;
return ll;
}
// Insert a node
hyStatus insertNode(LinkList *ll) {
int data = 0, index = 0;
// Input position
printf("Please enter the location to insert the node:");
scanf("%d", &index);
printf("\n");
// Check whether the input position is valid
if (index < 1 || index > (*ll)->data + 1) {
printf("Insert in illegal position \n");
return ERROR;
}
// Enter data
printf("Please enter data for inserting node:");
scanf("%d", &data);
printf("\n");
// Create a node
Node *node = malloc(sizeof(Node));
node->data = data;
node->nextNode = NULL;
node->frontNode = NULL;
/ / position
Node *p = *ll;
for (int i = 1; i < index; i++) {
// Since index is judged to be valid, there is no need to worry about the p->nextNode loop
p = p->nextNode;
}
// Start inserting
node->nextNode = p->nextNode;
p->nextNode->frontNode = node;
p->nextNode = node;
node->frontNode = p;
/ / + + length
(*ll)->data++;
return SUCCESS;
}
// Delete a node
hyStatus deleteNode(LinkList *ll) {
int index = 0;
printf("Please enter the location of the node to be deleted:");
scanf("%d", &index);
printf("\n");
// Check whether the input position is valid
if (index < 1 || index > (*ll)->data) {
printf("Deleted location is illegal \n");
return ERROR;
}
// The node is deleted
Node *p = *ll;
for (int i = 1; i < index; i++) {
// Since index is judged to be valid, there is no need to worry about the p->nextNode loop
p = p->nextNode;
}
// Start deleting
Node *delNode = p->nextNode;
p->nextNode = delNode->nextNode;
delNode->nextNode->frontNode = p;
// Release the deleted node
delNode->data = 0;
delNode->frontNode = NULL;
delNode->nextNode = NULL;
free(delNode);
// List length --
(*ll)->data--;
return SUCCESS;
}
// Query the circular list
int findNode(LinkList ll) {
int data = 0;
printf("Please enter the data to query:");
scanf("%d", &data);
printf("\n");
// Start query
Node *p = ll->nextNode;
int index = 1;
while(p ! = ll) {if (p->data == data) {
return index;
}
p = p->nextNode;
index++;
}
printf("This node \n was not found");
return ERROR;
}
// Loop through the list
void foreachLinkList(LinkList ll) {
Node *p = ll->nextNode;
int index = 1;
while(p ! = ll) {printf("%-5d", p->data);
p = p->nextNode;
index++;
}
printf("\n");
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
// Create a linked list
LinkList ll = createLinkList();
foreachLinkList(ll);
// Insert the node
printf("++++++++++++++++++++++++++++\n");
insertNode(&ll);
foreachLinkList(ll);
// Delete a node
printf("----------------------------\n");
deleteNode(&ll);
foreachLinkList(ll);
// Find the node
printf("============================\n");
printf("Search data location is: %d\n", findNode(ll));
}
return 0;
}
Copy the codeOk, two-way circular lists have been said, it may feel that this article is done hastily, but I really feel that these are nothing, careful thinking should be able to achieve these functions. So most words are used to explain nouns, concepts, etc.
As for logic, it’s all in the code, it’s all in the comments.
conclusion
This article mainly talks about linear list chain storage structure —— linked list. Including unidirectional linked list, unidirectional circular linked list, bidirectional linked list, bidirectional circular linked list and their corresponding create linked list, insert node, delete node, query data and other functions.
C language function —— pass value and address
I say this because IT occurs to me that the code uses some places to pass addresses, which may be a little confusing for some readers who are not familiar with C language.
First of all, I believe you all know that C functions pass parameters, essentially a copy of the variable space into the function implementation. Such as:
// Pass in the argument +1
void sumOne(int a) {
a = a + 1;
}
int x = 10;
// When we call this method, we essentially make a copy of x and pass the copied variables into the function implementation
sumOne(x);
Copy the codeThis is because a copy of the variable is passed to the method implementation, and the scope of the copied variable is only in the sumOne function. So a = a + 1 in the sunOne function; It doesn’t change the value of x outside of the function.
What if I want the function to change the value of an external variable? It’s simple. Pass the address. As follows:
// Pass in the argument +1
void sumOne(int *a) {
// a is the address, *a means to find the corresponding space through address A
*a = *a + 1;
}
int x = 10;
int *x1 = &x; // Assign the address of x to pointer variable x1
// a copy of the pointer variable x1 is passed to the implementation when the method is called
// Copy the address of x into the function implementation
sumOne(x1);
Copy the codeThis allows you to modify the values of external variables inside the function.
We know that there are blocks in OC to handle callbacks, but what about C callback functions? Yes, just use this address, but pass the address of the callback function, simple as that.
This paper addresses https://juejin.cn/post/6844904118130065422