数据结构学习笔记之链表

  • 时间:
  • 浏览:
  • 来源:互联网

声明:这个系列为学习极客时间的《数据结构与算法之美》的学习笔记。图大多数都是此系列文章内的图,非原创。

链表

定义:链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

下面分别讲述常见的链表:

单链表

为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址。
在这里插入图片描述
链表也支持数据的查找、插入和删除操作。

插入和删除:

在这里插入图片描述
显然复杂度都为O(1)

有利有弊,相对数组来说。链表要想随机访问第 k 个元素,就没有数组那么高效了。复杂度为O(n)。

这里我们总结一下数组和链表的区别:

底层存储:

数组需要一块连续的内存空间来存储,对内存的要求比较高。链表恰恰相反,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用。如图:
在这里插入图片描述

常见操作复杂度比较:

在这里插入图片描述

循环链表:

循环链表是一种特殊的单链表。实际上,循环链表也很简单。它跟单链表唯一的区别就在尾结点。(即尾结点.next = head)

双向链表:

双向链表,顾名思义,它支持两个方向,每个结点不止有一个后继指针 next 指向后面的结点,还有一个前驱指针 prev 指向前面的结点。
在这里插入图片描述
双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点,正是这样的特点,也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

实际上里面蕴涵着用空间换时间的设计思想。

Java有关容器类:

LinkedList:

LinkedList内部是用双向链表实现的:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

本文链接http://element-ui.cn/article/show-20561.aspx