链表

Harshit Jindal 2023年1月30日 2021年3月21日
  1. 链接列表与数组的比较
  2. 链表遍历算法
  3. 链表遍历图解
  4. 链表遍历实现
  5. 链表遍历算法复杂度
链表

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

链表

链表的一个节点包括:

  • 数据项。

  • 下一个节点的地址。

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 指针外不需要其他空间。

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相关文章 - Data Structure

相关文章 - Linked List