Giter VIP home page Giter VIP logo

datastructure's Introduction

DataStructure

数据结构:线性表,栈与队列,树与二叉树,图

对于本次学习的数据结构进行总结整理。

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

datastructure's People

Contributors

09221027 avatar

Watchers

 avatar

Forkers

xyt556

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.