C++实现链表：原理、代码与解析_C/C++

C++实现链表：原理、代码与解析

2023-12-23 15:01鲨鱼编程 C/C++

本文我们将深入探讨如何使用 C++ 实现链表，包括创建、插入、删除和遍历等操作。

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表不是连续的内存空间，而是通过指针链接在一起。下面我们将深入探讨如何使用C++实现链表，包括创建、插入、删除和遍历等操作。

C++实现链表：原理、代码与解析

一、链表的基本原理

链表由多个节点（Node）组成，每个节点至少包含两部分：存储的数据和指向下一个节点的指针。链表的起始节点称为头节点（Head），终止节点称为尾节点（Tail），尾节点的指针通常指向空（NULL）。

链表的主要优势在于动态分配内存，这使得在插入和删除节点时比数组更加高效。然而，访问链表中的元素通常需要从头节点开始遍历，因此不如数组直接访问元素快。

二、C++实现链表

1. 定义节点类

首先，我们需要定义一个节点类，它包含数据和指向下一个节点的指针。

class Node {  
public:  
    int data;           // 节点存储的数据  
    Node* next;         // 指向下一个节点的指针  
  
    // 构造函数  
    Node(int data) {  
        this->data = data;  
        this->next = NULL;  
    }  
};

2. 创建链表

我们可以通过连续创建新的节点，并将它们链接在一起来构建链表。

// 创建链表函数  
Node* createLinkedList(int arr[], int n) {  
    Node* head = NULL;  // 初始化头节点为空  
    Node* tail = NULL;  // 初始化尾节点为空  
    for (int i = 0; i < n; i++) {  
        // 创建新节点  
        Node* newNode = new Node(arr[i]);  
        if (head == NULL) {  // 如果链表为空，新节点即为头节点  
            head = newNode;  
            tail = newNode;  // 头节点同时也是尾节点  
        } else {            // 否则将新节点添加到尾节点的后面  
            tail->next = newNode;  // 将尾节点的next指向新节点  
            tail = newNode;        // 更新尾节点为新节点  
        }  
    }  
    return head;  // 返回头节点指针，代表整个链表  
}

3. 遍历链表

要遍历链表中的所有节点，我们需要从头节点开始，通过每个节点的next指针访问下一个节点，直到next为空（即达到尾节点）。

void traverseLinkedList(Node* head) {  
    Node* current = head;  // 从头节点开始遍历  
    while (current != NULL) {  // 当当前节点不为空时继续遍历  
        cout << current->data << " ";  // 输出当前节点的数据  
        current = current->next;  // 移动到下一个节点  
    }  
    cout << endl;  // 输出换行符，使结果更清晰  
}