笔记01 数据结构
数据结构
数据结构，以某种特定的布局方式存储数据的容器。
这种布局方式决定了数据结构对于某些操作是高效的，
而对于其他操作则是低效的。
在处理实际问题时选取最合适的数据结构。
常见数据结构1 数组 (线性)
每个数据元素都关联一个正数值，我们称之为索引，
它表明数组中每个元素所在的位置。
大部分语言将初始索引定义为零。
- 一维数组
- 多维数组 (数组的数组)
—
- insert 在指定索引位置插入一个元素
- get 返回指定索引位置的元素
- delete 删除指定索引位置的元素
- size 得到数组所有元素的数量
常见数据结构2 栈 (线性)
著名的撤销操作几乎遍布任意一个应用。
但你有没有思考过它是如何工作的呢？
这个问题的解决思路是按照将最后的状态排列在先的顺序，
在内存中存储历史工作状态(当然，它会受限于一定的数量)。
可以把栈想象成一个垂直堆放的书。
为了拿到中间的书，你需要移除放置在这上面的所有书。
这就是LIFO(后进先出)的工作原理。
- push 在顶部插入一个元素
- pop 返回并移除栈顶元素
- isEmpty 如果栈为空，则返回true
- top 返回顶部元素，但并不移除它
常见数据结构3 队列 (线性)
队列是FIFO(先进先出)
一个完美的队列现实例子：售票亭排队队伍。
如果有新人加入，他需要到队尾去排队，
而非队首 — 排在前面的人会先拿到票，
然后离开队伍。
- enqueue 在队列尾部插入元素
- dequeue 移除队列头部的元素
- isEmpty 如果队列为空，则返回true
- top 返回队列的第一个元素
常见数据结构4 链表 (线性)
乍一看可能有点像数组，但在内存分配、内部结构
以及数据插入和删除的基本操作方面均有所不同。
链表就像一个节点链，其中每个节点包含着数据和指向后续节点的指针。
链表还包含一个头指针，它指向链表的第一个元素，
但当列表为空时，它指向null或无具体内容。
量表一般用于实现文件系统、哈希表、和邻接表。
- 单链表 (单向)
- 双向链表 (双向)
—
- insertAtEnd 在链表的末尾插入指定元素
- insertAtHead 在链表的开头/头部插入指定元素
- delete 从链表中删除指定元素
- deleteAtHead 删除链表的第一个元素
- search 从链表中返回指定元素
- isEmpty 如果链表为空，则返回true
