当前位置: 首页>后端>正文

一、常用数据结构说明

开篇第一章,介绍一下常见的数据结构,之后的章节介绍常见的算法解题框架

1、数组

? ? ? ? 优点:内存连续,查找效率高,为O(1)

????????缺点:内存连续,因此插入/删除时间复杂度高,为O(n)

2、链表

????????优点:内存不连续,插入/删除时间复杂度低,为O(1)

????????缺点:内存不连续,因此查找时间复杂度高,为O(n)

3、栈Stack

????????先入后出(FILO);可以通过数组/链表实现;两个栈,一个入栈,一个出栈,可以模拟队列操作。

4、队列Queue

????????先入先出(FIFO);可以通过数组/链表实现;常用于消息队列;

5、优先队列PriorityQueue

????????先入按照优先级出(FIFO);可以通过堆Heap(Binary、Binomial、Fibonacci)/二叉搜索树(Binary Search Tree)实现,一般不会考如何实现,现在优先队列都纳入了标准库中,了解实现机制即可;

6、堆Heap

一、常用数据结构说明,第1张
堆各种实现性能对比

7、映射(Map)&集合(Set)

映射(Map)&集合(Set)一般由哈希/二叉树实现,需要先了解HashTable & Hash Function & Hash Collisions。哈希: key经过Hash Function 处理后,O(1)的时间复杂度在HashTable(一般维数组) 找到数据所在的位置。Hash?Collisions的一种解决方式为拉链法:冲突后在HashTable 元素后面挂链表来存放位置冲突的元素。

List & 映射(Map) & 集合(Set)的区别:List 元素可重复,一般用数组/链表实现;?映射(Map)是key/value映射关系,一般用哈希(O(1))/树(O(logn))实现,比数组查找效率高;集合(Set)与List 比,元素不可重复,一般用哈希(O(1))/树(O(logn))实现,比数组查找效率高;

映射(Map)常用实现有两种:HashMap、TreeMap,查找数据时间复杂度为O(1),但是数据是无序存放的;集合(Set)常用实现有两种:HashSet、TreeSet,查找数据时间复杂度为O(logn),但是数据是有序存放的;

一、常用数据结构说明,第2张
各种数据结构时间复杂度对比

8、


https://www.xamrdz.com/backend/3e41936154.html

相关文章: