链表数据结构

本文介绍了链表数据结构并使用 C、C++、Java 和 Python 实现了链表。

链表是一种线性数据结构,包括一系列连接的节点。在这里,每个节点存储数据并指向下一个节点的地址。例如,

链表数据结构
链表数据结构

你必须从某个地方开始,所以我们给第一个节点的地址一个特殊的名字叫做 HEAD。 此外,可以识别链表中的最后一个节点,因为它没有后置节点。

链表可以有多种类型: 单链表、 双链表和循环链表。在本文中,我们将重点介绍单向链表。要了解其他类型,请访问链接列表的类型

**注意:**您可能玩过寻宝游戏,其中每条线索都包含有关下一条线索的信息。这就是链表的运作方式。

链表的表示

让我们看看链表的每个节点是如何表示的。每个节点包括:

  • 一个数据项
  • 另一个节点的地址

我们将数据项和下一个节点引用包装在一个结构体中,如下所示:

struct node
{
  int data;
  struct node *next;
};

理解链表节点的结构是掌握它的关键。

每个结构节点都有一个数据项和一个指向另一个节点的指针。让我们创建一个包含三个项目的简单链表,以了解其工作原理。

/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data=3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;

/* Save address of first node in head */
head = one;

如果你不理解上面的任何一行,你需要的只是复习一下 C 语言结构体和指针

只需几步,我们就创建了一个包含三个节点的简单链表。

通过使用下一个节点的地址将每个节点与下一个节点连接来表示链表
链表表示

链表的威力来自打破链并重新加入链的能力。例如,如果您想将元素 4 放在 1 和 2 之间,步骤将是:

  • 创建一个新的结构节点并为其分配内存。
  • 将其数据值添加为 4
  • 将其 next 指针指向包含 2 作为数据值的节点
  • 1 节点的 next 指针更改为我们刚刚创建的节点

在数组中做类似的事情需要移动所有后续元素的位置。

在 python 和 Java 中,链表可以使用类来实现。

Python、Java、C 和 C++ 示例中的链表实现

链表是最流行和最高效的数据结构之一,在 C、C++、Python、Java 和 C# 等每种编程语言中都有实现。

除此之外,链表是学习指针如何工作的好方法。通过练习如何操作链表,您可以准备好学习更高级的数据结构,如图形和树。

使用 Python 实现链表

class Node:
    # Creating a node
    def __init__(self, item):
        self.item = item
        self.next = None

class LinkedList:

    def __init__(self):
        self.head = None

if __name__ == '__main__':

    linked_list = LinkedList()

    # Assign item values
    linked_list.head = Node(1)
    second = Node(2)
    third = Node(3)

    # Connect nodes
    linked_list.head.next = second
    second.next = third

    # Print the linked list item
    while linked_list.head != None:
        print(linked_list.head.item, end=" ")
        linked_list.head = linked_list.head.next

使用 Java 实现链表

class LinkedList {
  // Creating a node
  Node head;

  static class Node {
    int value;
    Node next;

    Node(int d) {
      value = d;
      next = null;
    }
  }

  public static void main(String[] args) {
    LinkedList linkedList = new LinkedList();

    // Assign value values
    linkedList.head = new Node(1);
    Node second = new Node(2);
    Node third = new Node(3);

    // Connect nodess
    linkedList.head.next = second;
    second.next = third;

    // printing node-value
    while (linkedList.head != null) {
      System.out.print(linkedList.head.value + " ");
      linkedList.head = linkedList.head.next;
    }
  }
}

使用 C 语言实现链表

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

// Creating a node
struct node {
  int value;
  struct node *next;
};

// print the linked list value
void printLinkedlist(struct node *p) {
  while (p != NULL) {
    printf("%d ", p->value);
    p = p->next;
  }
}

int main() {
  // Initialize nodes
  struct node *head;
  struct node *one = NULL;
  struct node *two = NULL;
  struct node *three = NULL;

  // Allocate memory
  one = malloc(sizeof(struct node));
  two = malloc(sizeof(struct node));
  three = malloc(sizeof(struct node));

  // Assign value values
  one->value = 1;
  two->value = 2;
  three->value = 3;

  // Connect nodes
  one->next = two;
  two->next = three;
  three->next = NULL;

  // printing node-value
  head = one;
  printLinkedlist(head);
}

使用 C++ 实现链表

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

// Creating a node
class Node {
   public:
  int value;
  Node* next;
};

int main() {
  Node* head;
  Node* one = NULL;
  Node* two = NULL;
  Node* three = NULL;

  // allocate 3 nodes in the heap
  one = new Node();
  two = new Node();
  three = new Node();

  // Assign value values
  one->value = 1;
  two->value = 2;
  three->value = 3;

  // Connect nodes
  one->next = two;
  two->next = three;
  three->next = NULL;

  // print the linked list value
  head = one;
  while (head != NULL) {
    cout << head->value;
    head = head->next;
  }
}

链表复杂性

链表的时间复杂度

最差的情况 平均情况
搜索 O(n) O(n)
插入 O(1) O(1)
删除 O(1) O(1)

链表的空间复杂度: O(n)

链表应用

  • 动态内存分配
  • 在堆栈和队列中实现
  • 在软件的撤销功能中
  • 哈希表、图表

相关教程

编程实例

  • 单次迭代获取链表的中间元素
  • 将链表转换为数组,反之亦然
  • 检测链表中的循环