数组、链表、跳表
数组、链表、跳表基本实现和特性
Array(数组)
- java,c++: int a[100];//初始化的时候先定义好容量
- Python： list=[]//直接定义一个数组
- JavaScript: let x=[1,2,3]
时间复杂度
| prepend |
O(n) |
| append |
O(1) |
| lookup |
O(1) |
| insert |
O(n) |
| delete |
O(n) |
成员函数
- 元素访问
- at?访问指定元素，同时进行越界检查
- operator[]?访问指定的元素
- front?访问第一个元素
- back?访问最后一个元素
- data?返回指向内存中数组第一个元素的指针
- 迭代器
- begin?返回容器第一个元素的迭代器
- end?返回指向容器尾端的迭代器
- rbegin?返回指向容器最后元素的逆向迭代器
- rend?返回指向前端的逆向迭代器
- 容量
- empty?检查容器是否为空
- size?返回容纳元素数
- max_size?返回可容纳的最大元素数
- 操作
链表
class Node {
int data;
Node next;
}
class LinkedList {
Node head; /
Node (int d) { data = d;}
}
时间复杂度
| prepend |
O(1) |
| append |
O(1) |
| lookup |
O(n) |
| insert |
O(1) |
| delete |
O(1) |
成员函数
- 元素访问
- front?访问第一个元素
- back?访问最后一个元素
- 迭代器
- begin?返回指向容器第一元素的迭代器
- end?返回指向容器尾端的迭代器
- rbegin?返回指向容器尾端的迭代器
- rend?返回指向前端的逆向迭代器
- 容量
- empty?检查容器是否为空
- size?返回容纳的元素数
- max_size?返回可容纳的最大元素数
- 修改器
- clear?清除内容
- insert?插入元素
- emplace?原位构造元素
- erase?擦除元素
- push_back?将元素添加到容器末尾
- emplace_back?在容器末尾就地构造元素
- pop_back?移除末元素
- push_front?插入元素到容器起始
- emplace_front?在容器头部就地构造元素
- pop_front?移除首元素
- resize?改变容器中可存储元素的个数
- swap?交换内容
- 操作
- merge?合并二个已经排序列表
- splice?从另一个list中移动元素
- remove/remove_if?移除满足特定标准的元素
- reverse?将该链表的所有元素的顺序反转
- unique?删除连续的重复元素
- sort?对元素进行排序
跳表
时间复杂度
队列
1.Queue：先入先出；添加、删除皆为O(1)
2.查询为 O(n)
时间复杂度
| Access |
O(n) |
| Search |
O(n) |
| Insertion |
O(1) |
| Deletion |
O(1) |
成员函数
- 元素访问
- front?访问第一个元素
- back?访问最后一个元素
- 容量
- empty?检查底层的容器是否为空
- size?返回容纳的元素数
- 修改器
- push?像队列尾部插入元素
- emplace?于尾部原位构造元素
- pop?删除栈顶元素
swap?交换内容
扩展
- 双端队列
- 简单理解：两端可以进出的
- 插入和删除都是O(1)操作
- QueueDeque - double ended queue
- 优先队列
- 插入操作：O(1)
- 取出操作：O(logN) - 按照元素的优先级取出
- 底层具体实现的数据结构较为多样和复杂：heap、bst(二叉搜索树)、treap
数组、链表、跳表
原文：https://www.cnblogs.com/liugangjiayou/p/12369998.html
