首页 > 代码库 > 多种数据结构之间比较

多种数据结构之间比较

常见的数据结构有:array,list,stack,deque,binaryTree,hashMap,heap,对于C++而言还有最常用的vector

接着分析每一种的特点:

[1] array

内存分配:在内存中分配一段连续的空间;

特点:需要再定义时就知道分配空间的大小;

使用:用于预先就已知需要的最大储存空间的情况;

[2] vector

内存分配:在内存中分配一段连续的空间;

实现:内部实际通过管理一个数组指针实现;

特点:插入的元素如果超出分配的内存空间,会自动划分一段更大的内存空间,将数据拷贝过去后,释放原空间;

使用:对于C++而言采用vector的情况比较多。对于需要随机访问元素,预先不知道需要分配的内存空间大小情况。但是vector在中间和头部插入比较麻烦,插入时间复杂度是O(N);因此vector适用于只在尾部插入和删除的情况;

[3] list

内存分配:随机分配;

实现:通过一个结构体保存指向前一个元素和后一个节点的指针(双向链表);

特点:在任何地方插入都很方便,但是随机访问时间复杂度是O(N);

[4] stack

实现:通过一个表实现很方便,也可以通过数组实现;

特点:后进先出,在编译器中得到广泛应用,例如编译器实现的函数堆栈;

[5] deque

实现:通过一个数组实现;

特点:先进先出,典型应用是多个对象需要抢占同一个资源时;

[6] binaryTree

内存分配:随机分配

实现:保存左右儿子的指针

特点:插入和访问的时间复杂度都是O(logN),内部操作函数的实现很多靠递归来实现。每个节点儿子的个数可以扩展。在操作系统的编译器中的得到广泛应用;

[7] hashMap

实现:分离链接法通过数组和链表实现,开放地址法通过数组实现;

特点:支持随机访问,可以保存到每个数据的信息,可以访问指定的元素。因此应用于需要知道数据信息的情况,比如实现一个词典,就可以将单词存入一个hash表中;

[8] heap

实现:通过数组实现一个完全二叉树,称为堆

 

多种数据结构之间比较