数据结构:线性表,栈与队列,树与二叉树,图
对于本次学习的数据结构进行总结整理。
Array:数组,连续内存
LinkedList:链表,非连续内存,节点值+下一节点地址,头节点
Stack:栈,后入先出,Push,Pop,Peek,栈底栈顶
Queue:队列,先入先出,Enqueue,Dequeue,Peek,队首队尾
实现数据结构包括:
名称 | AddFirst | AddLast | Get | Set | Contains | RemoveFirst | RemoveLast |
Array1,动态数组 | O(n) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) |
Array2,循环数组 | O(1) | O(1) | O(1) | ||||
LinkedList1,链表 | O(1) | O(n) | O(n) | O(n) | O(n) | O(1) | O(n) |
LinkedList2,带尾指针的链表 | O(1) | O(1) | O(1) |
Array1Stack:动态数组栈,全部为O(1)。系统提供了Stack
Array1Queue:动态数组队列,使用动态数组的First为队首,Dequeue O(n)
Array2Queue:循环数组队列,全部为O(1)。系统提供了Queue
LinkedList1Queue:链表队列,使用链表的Last为队首,Enqueue O(n)
LinkedList1Set:链表集合,全部为O(n)
LinkedList1Stack:链表栈,全部为O(1)。需要new节点,性能不如Array1Stack
LinkedList2Queue:带尾指针的链表的队列,全部为O(1)。需要new节点,性能不如Array2Queue
LinkedList3:链表键值
LinkedList3Dictionary:链表映射
SortedArray1:有序数组。由于集合需要判断Contain,由连续查找改为二分查找,获得有序数组。
SortedArray1Set:有序数组集合。Contains为O(log n)。系统提供了SortedList
SortedArray2:有序数组键值对。
SortedArray2Dictionary:有序数组映射。Add仍为O(n)
BST1:二叉树,递归,前序遍历中序遍历后序遍历(深度优先),层序遍历(广度优先),支持Min,Max,树高
BST1Set:二叉树集合
BST2:二叉树键值
BST2Dictionary:二叉树映射,二叉树对有序数据的构建不好
RBT1:左倾红黑树,二叉树为了平衡,左旋,右旋,颜色翻转
RBT1Set:红黑树集合。系统提供了SortedSet
RBT2:红黑树键值对
RBT2Dictionary:红黑树映射。系统提供了SortedDictionary
HashST1:哈希表,哈希函数,哈希冲突
HashST1Set:哈希表集合,不支持最大最小等。系统提供了HashSet
HashST2:哈希表键值对
HashST2Dictionary:哈希表字典。系统提供了Dictionary