迹忆客 专注技术分享

链表是线性数据结构。它是定义为节点的对象的集合。但是在链接列表中，节点存储在内存中的随机位置中，而不存储在连续位置中。

链表的一个节点包括：

• 数据项。

• 下一个节点的地址。

class Node
{
    int data;
    Node *next;
};

节点的这种表示形式用于创建列表中的每个节点。数据字段存储元素，而*next 是存储下一个节点地址的指针。

第一个节点的地址称为头，最后一个节点的地址称为尾。链接列表中的最后一个节点指向 NULL。因此，当列表为空时，头节点指向 NULL 节点。链接列表不需要事先声明大小，并且可以动态增加大小。在链表中插入和删除元素非常容易。我们不需要移动所有要素；仅更改上一个和下一个元素的指针就足够了。

链接列表与数组的比较

链接列表比数组具有自然的优势，因为我们不必事先分配大量的内存，但是由于内存不是连续分配的，因此链接列表缓存起来也不友好。它们允许在指针的帮助下轻松地插入和删除元素，但由于指针所需的空间，每个节点的存储空间也要加倍。链接列表也不提供对元素的随机访问。因此，很明显，没有一个赢家，而且链表和数组都有各自的优缺点。

当我们有一个小列表并且知道我们可能存储的最大元素数量时，应该使用数组，而当有一个大列表定期更改时，应该使用链接列表。

链表遍历算法

令 head 成为链接列表的第一个节点。

• 初始化指向链接列表的 head 节点的 curr。
• 虽然 curr 尚未到达列表的末尾，即 curr！=NULL，但请执行以下操作：
  • 打印存储在当前节点内的数据。
  • curr=curr->next;

链表遍历图解

• 初始化指向 head 节点的指针 curr，数据值等于 2。打印值 2。

• 将指针 curr 移动到下一个节点，数值为 4。打印值 4。

• 将指针 curr 移动到下一个节点，数值为 6。打印数值 6。

• 将指针 curr 移动到下一个节点，数值为 8。打印值 8。

• 将指针 curr 移动到下一个节点，该节点的值等于 NULL。达到 while 循环终止条件。因此，我们已经访问了所有的节点。

链表遍历实现

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int x) {
        this->data = x;
        this->next = NULL;
    }
};

void printList(Node* head)
{
    Node*curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
}

int main()
{
    Node* head = new Node(1);
    head -> next = new Node(2);
    head -> next-> next = new Node(3);
    head -> next-> next-> next = new Node(4);
    head -> next-> next-> next-> next = new Node(5);
    head -> next-> next-> next-> next-> next = new Node(6);
    printList(head);
    return 0;
}

链表遍历算法复杂度

时间复杂度

• 平均情况

要遍历完整的链表，我们必须访问每个节点。因此，如果一个链表具有 n 个节点，则遍历的平均情况下时间复杂度约为 O(n)。时间复杂度约为 O(n)。

• 最佳情况

最佳情况下的时间复杂度是 O(n)。它与平均情况下的时间复杂度相同。

• 最坏情况

最坏情况下的时间复杂度是 O(n)。它与最佳情况下的时间复杂度相同。

空间复杂度

该遍历算法的空间复杂度为 O(1)，因为除 curr 指针外不需要其他空间。