链表实现解析：结构体与数组两种方式

链表实现解析：结构体与数组两种方式

一、链表的基本概念

链表是一种线性的、动态的数据结构，由一系列节点（Node）通过指针（或引用）连接而成。与数组不同，链表中的元素在内存中不是连续存储的，而是通过每个节点中的指针域来维护逻辑上的连续性。

链表的主要特点包括：

• 动态大小：可以随时增加或删除节点，无需预先分配固定空间
• 高效插入/删除：在已知位置插入或删除节点的时间复杂度为 O(1)
• 顺序访问：只能从头节点开始顺序访问，不支持随机访问

二、结构体实现链表

2.1 节点结构定义

在 C/C++ 中，我们通常使用结构体来定义链表节点：

struct Node {
    int data; // 数据域，存储节点值
    Node* next; // 指针域，指向下一个节点
};

类比说明：这个结构体定义类似于 JavaScript 中的类或 Java 中的对象。Node* next 相当于 Java 中的引用，指向下一个节点对象。

2.2 链表构建与遍历

让我们构建一个包含四个节点（数据分别为 1、2、3、4）的链表：

头节点 -> 1 -> 2 -> 3 -> 4 -> NULL

// 创建节点函数
Node* createNode(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = nullptr;
    return newNode;
}

// 构建链表
Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);

// 遍历链表
void traverseList(Node* head) {
    Node* p = head;
    while (p != nullptr) {
        cout << p->data << ;
        p = p->next;
    }
}