002-数据结构与算法-线性表

数据结构按照数据存储方式,可以分为线性表和非线性表两大类。

线性表就是数据排列成一条线一样的结构,例如数组、链表、栈、队列。

非线性表自然就是数据按照非线性结构排列了,例如树和图。

数组

描述

数组是一种线性表数据结构,用一组连续的内存空间,来存储具有相同数据类型的数据。

特点

  • 根据下标随机访问。由于每个各元素的数据类型相同,因此元素占用的内存空间是一样的,同时由于数组在内存中是连续的,因此知道了要访问元素的下标,就能够推算出该元素在内存中的位置,达到根据下标快速访问的目的。
  • 插入和删除慢。当我们向数组中间插入或者查出元素时,为了保持数组的连续性,需要移动附近元素。例如向数组头插入一个元素,那么在插入前,要将原数组所有的元素位置都向后移,这样就影响插入和删除的速度。

时间复杂度

插入/删除:O(n) 查询:O(1)

实际应用

Java中ArrayList基于数组实现。

链表

描述

链表是一种线性数据结构,通过指针将不连续的内存空间串联起来使用。

特点

  • 指针。链表除了存储数据之外,还需要额外的空间保存指针,因此相比于数组,链表需要的内存空间更大。
  • 类型。常用链表有单向链表,双向链表,循环链表三种。单向链表只有一个next指针,指向下一个节点。双向链表同时有pre和next两个指针。循环链表则所有节点组成了一个闭环。
  • 查找慢,插入/删除快。链表中查找元素需要遍历整个链表,而插入/删除则只需要修改当前节点附近两个节点的指针。

时间复杂度

插入/删除:O(1) 查询:O(n)

实际应用

Java中LinkedList基于链表实现。

跳表

描述

跳表是一种特殊的链表,在链表基础上,增加了索引层。

特点

  • 数据有序。跳表中所有的数据都是按顺序排列的。
  • 索引层。跳表是多层结构,最低层是基础数据层,基础数据层之上存在多个索引层。
  • 查找比普通链表快。由于索引层的存在,可以快速的在跳表中查找数据。
  • 插入/删除比普通链表慢。为了保证数据的顺序,跳表在插入/删除数据时需要先查找该数据在跳表的位置,同时可能会重新维护索引层,因此比普通链表慢,但是仍然比数组快。

时间复杂度

插入/删除:O(log(n)) 查询:O(log(n))

实际应用

Redis的有序结合set就是基于跳表实现的。与红黑树相比,跳表的查找,插入,删除时间复杂度是一样的。但是跳表支持范围查找,而红黑树不支持。另外,跳表的实现逻辑相比红黑树要简单很多。

不过红黑树也有自己的优势,就是出现时间比较早,很多语言都有基于红黑树的实现,例如Java中的HashMap,程序员不需要自己去开发红黑树。而跳表很少有现成的实现,需要程序员自己去开发。

描述

链表是一种操作受限的线性数据结构,只支持入栈和出栈两个操作。

特点

  • 先进后出。由于入栈操作是将数据压入栈尾,而出栈操作是将数据从栈头取出,因此先进栈的数据反而最后出栈。
  • 即可用数组实现(顺序栈),也可用链表实现(链式栈)。

时间复杂度

入栈:O(1) 出栈:O(1)

实际应用

Java虚拟机栈。

队列

描述

队列是一种操作受限的线性数据结构,只支持入对和出队两个操作。

特点

  • 先进先出。与栈不同,数据从队列尾进入,从队列头弹出,先进的数据先出。也存在双向队列,列头和列尾都可以进出数据。
  • 即可用数组实现(顺序队列),也可用链表实现(链式队列)。

时间复杂度

入队:O(1) 出对:O(1)

实际应用

Java中的BlockingQueue,CocurrentXXXQueue等。

上篇002-数据结构与算法-散列表
下篇002-数据结构与算法-复杂度分析