数据结构

数据结构

什么是数据结构？

数据结构用于展现数据之间的逻辑关系，存储关系，操作关系。

数据结构主要有哪些？

栈，队列，链表，集合，哈希表，树，字典，图。

链表

链表和数组的区别？

数组必须要一整块内存（静态分配内存，先确定数组的长度），链表是内存和指针，也就是说不需要一整块的内存

数组元素在栈区，链表元素在堆区

添加的时候要带上指针，如果删除中间的一个内容，只需要更改指针即可

• 单向链表
• 双向链表
• 循环链表

循环链表：一个应用场景就是操作系统的分时问题,比如有一台计算机,但是有多个用户使用,CPU要处理多个用户的请求很可能会出现抢占资源的情况,这个时候计算机会采取分时策略来保证每个用户的使用体验.

数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n); 数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1);