[Regaining C Language] 13. Dynamic data organization (2) Linked list (creation, traversal retrieval, insertion, deletion, exchange)

Table of Contents

Preface

13. Dynamic data organization

13.1~2 Dynamic data organization, dynamic variables

13.3 Linked list

13.3.1 One-way linked list-creation

13.3.2 One-way linked list-traversal retrieval

13.3.3 One-way linked list-insertion, deletion and exchange

insert

delete

exchange

13.3.4 One-way linked list-example

13.3.5 Stacks and Queues

Foreword

A linked list is a common dynamic data structure that consists of a sequence of nodes, each node containing data and a pointer to the next node. In C language, pointers and dynamic memory allocation functions can be used to implement the creation, traversal, insertion, deletion and exchange operations of linked lists.

Thirteenth, Dynamic Data Organization

13.1~2 Dynamic data organization, dynamic variables

[Regaining C Language] 13. Dynamic Data Organization_QomolangmaH’s Blog-CSDN Blogicon-default.png?t=N7T8https://blog.csdn.net /m0_63834988/article/details/133845135?spm=1001.2014.3001.5501

13.3 Linked List

13.3.1 One-way Linked List-Creation

The basic steps to create a one-way linked list include defining the node structure and allocating node memory using dynamic memory allocation functions. The node structure usually contains two members: data member (used to store data) and pointer member (used to point to the next node). By linking nodes together, the structure of a linked list is formed.

//Define node structure
struct Node {
    int data; // data members
    struct Node* next; // pointer member
};

// Create linked list
struct Node* createLinkedList() {
    struct Node* head = NULL; // Head pointer, pointing to the first node of the linked list
    struct Node* temp = NULL; // Temporary pointer, used to create new nodes
    
    //Create node 1
    struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
    node1->data = 1;
    node1->next = NULL;
    
    // Set node 1 as the head node
    head = node1;
    
    //Create node 2
    struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
    node2->data = 2;
    node2->next = NULL;
    
    // Link node 2 to the back of node 1
    node1->next = node2;
    
    //Create node 3
    struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
    node3->data = 3;
    node3->next = NULL;
    
    // Link node 3 to node 2
    node2->next = node3;
    
    return head; // Return head pointer
}

The process of traversing a linked list is to visit each node in the linked list in sequence and perform corresponding operations. The entire linked list can be traversed by using a pointer to point to the nodes in the linked list.

//Traverse the linked list and print node data
void traverseLinkedList(struct Node* head) {
    struct Node* current = head; // Start traversing from the head node
    
    while (current != NULL) {
        printf("%d ", current->data); // Print node data
        current = current->next; // Move to the next node
    }
}

13.3.3 One-way linked list-Insertion, deletion and exchange

Inserting, deleting, and exchanging nodes in a linked list are common operations and can be accomplished by updating the node’s pointer.

insert
//Insert node into linked list
void insertNode(struct Node* prevNode, int newData) {
    if (prevNode == NULL) {
        printf("Error: Previous node cannot be NULL.\\
");
        return;
    }
    
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}
  • Receives a pointer to the previous node prevNode and the new data to be inserted newData as parameters.
  • First check whether prevNode is NULL
    • If so, print an error message and return.
    • Otherwise, it creates a new node
      • Assign newData to the data member of the new node.
      • Set the new node’s next pointer to the next node of prevNode, and set the next pointer of prevNode to point to the new node node to complete the insertion operation.
Delete
//Delete nodes in the linked list
void deleteNode(struct Node* prevNode) {
    if (prevNode == NULL || prevNode->next == NULL) {
        printf("Error: Node to be deleted cannot be NULL.\\
");
        return;
    }
    
    struct Node* nodeToDelete = prevNode->next;
    prevNode->next = nodeToDelete->next;
    free(nodeToDelete); // Release memory
}
  • Receives a pointer to the previous node prevNode as a parameter.
  • First check whether prevNode is NULL or whether the next node of prevNode is NULL
    • If so, print an error message and return.
    • Otherwise, it gets the pointer nodeToDelete of the node to be deleted and points the next pointer of prevNode to the next of nodeToDelete node, and then release the memory of nodeToDelete to complete the deletion operation.
Exchange
//Exchange the positions of two nodes in the linked list
void swapNodes(struct Node* head, int data1, int data2) {
    if (data1 == data2) {
        printf("Error: Data values are the same.\\
");
        return;
    }
    
    struct Node* prevNode1 = NULL;
    struct Node* prevNode2 = NULL;
    struct Node* currentNode = head;
    
    while (currentNode != NULL) {
        if (currentNode->next != NULL & amp; & amp; currentNode->next->data == data1)
            prevNode1 = currentNode;
        if (currentNode->next != NULL & amp; & amp; currentNode->next->data == data2)
            prevNode2 = currentNode;
        
        currentNode = currentNode->next;
    }
    
    if (prevNode1 == NULL || prevNode2 == NULL) {
        printf("Error: Data values not found in the list.\\
");
        return;
    }
    
    struct Node* node1 = prevNode1->next;
    struct Node* node2 = prevNode2->next;
    
    if (prevNode1 != NULL)
        prevNode1->next = node2;
    else
        head = node2;
    
    if (prevNode2 != NULL)
        prevNode2->next = node1;
    else
        head = node1;
    
    struct Node* temp = node1->next;
    node1->next = node2->next;
    node2->next = temp;
}
  • Receives the head node pointer head of the linked list and the data values of the two nodes to be exchanged data1 and data2 as parameters.
  • First check whether data1 and data2 are equal. If they are equal, print an error message and return. Ran
  • Use three pointer variables prevNode1, prevNode2 and currentNode to traverse the linked list and find the list containing data1 and data2 The previous node of the node.
  • It checks whether prevNode1 and prevNode2 are NULL, and if so, prints an error message and returns.
  • Get the pointers node1 and node2 of the two nodes to be swapped.
  • Update the next pointer of the previous node, point the next of the previous node of node1 to node2, and set the next pointer of the previous node to node2. The next of the previous node of >node2 points to node1 to realize the exchange of node positions.
  • It exchanges the next pointers of the two nodes to complete the exchange operation.

13.3.4 One-way Linked List-Example

Here is an example that demonstrates how to use a one-way linked list to implement a simple task list:

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

struct Task {
    char name[100];
    struct Task* next;
};

struct Task* createTask(const char* name) {
    struct Task* task = (struct Task*)malloc(sizeof(struct Task));
    strcpy(task->name, name);
    task->next = NULL;
    return task;
}

void addTask(struct Task** head, const char* name) {
    struct Task* newTask = createTask(name);
    if (*head == NULL) {
        *head = newTask;
    } else {
        struct Task* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newTask;
    }
}

void printTasks(struct Task* head) {
    struct Task* current = head;
    while (current != NULL) {
        printf("%s\\
", current->name);
        current = current->next;
    }
}

int main() {
    struct Task* taskList = NULL;
    
    addTask( & amp;taskList, "Task 1");
    addTask( & amp;taskList, "Task 2");
    addTask( & amp;taskList, "Task 3");
    
    printTasks(taskList);
    
    return 0;
}

Task list struct Task structure contains a character array named name and a pointer next pointing to the next task.

  • The createTask(const char* name) function is used to create a new task node:
    • Receives a string name as a parameter, dynamically allocates memory to create a struct Task structure, and copies the incoming name to the name member. Finally, it sets the next pointer to NULL and returns the created task node.
  • The addTask(struct Task** head, const char* name) function is used to add a new task to the task list:
    • Receives a pointer head pointing to the head of the task list and a string name as parameters.
    • First call the createTask function to create a new task node.
    • It then checks if the task list is empty, and if so, sets the new node as the head node. Otherwise, it walks through the task list, finds the last node, and adds the new node as the next node of the last node.
  • The printTasks(struct Task* head) function is used to print all tasks in the task list:
    • Traverse the task list, starting from the head node, and print the name of each task one by one.
  • In the main function, first create an empty task list taskList. Then, three tasks were added to the task list using the addTask function. Finally, call the printTasks function to print the names of all tasks in the task list.

Output:

Task 1
Task 2
Task 3

13.3.5 Stack and Queue

In addition to linked lists, stacks and queues are also common dynamic data structures. The stack is a last-in-first-out (LIFO) data structure that can be implemented using an array or a linked list. A queue is a first-in-first-out (FIFO) data structure that can also be implemented using an array or linked list. For more information on stacks and queues, see below.