优缺点分析

笨蛋

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表等。而今天我们就再来了解一下，数据结构的常见类型与优缺点分析。
数据结构的常见类型与优缺点分析


　　1.列表(List)


　　元素有放入顺序，元素可重复。


　　数组实现(Vector类)


　　同样基于数组实现，会在内存中开辟一块连续的空间来存储。ArrayList是非线程安全的，效率高;Vector是基于线程安全的，但效率低，并且是方法级别的同步，不是绝对的线程安全。


　　初始容量10，每次数组扩展到原来容量的2倍(每次扩充的容量大小是可以设置的，而ArrayList类不支持设定)。


　　链表实现(LinkedList类)


　　每一个元素存储本身数据的同时还存储上、下两个元素的地址(双向链表)。


　　优点：


　　新项的插入和现有项的删除平均开销很小O(1)(假设变动项的位置已知)，因此提供了addFirst和removeFirst,addLast和removeLast,getFirst和getLast等有效添加、删除和访问两端的项的方法;


　　可以在非连续的内存空间里面存储一个集合的元素;


　　缺点：


　　根据索引的访问时间复杂度为O(n);


　　存放相同多的数据，一般情况下，数组占用较小的内存，而链表还需要存放其前驱和后继的空间。


　　2.栈(Stack)


　　栈，在计算机中运用广泛，比如说JVM，它就是基于栈来执行指令的。栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫作栈顶，对栈的基本操作有push(进栈)和pop(出栈)，前者相当于插入，后者相当于删除后一个元素。栈有时又叫作LIFO(LastInFirstOut)表，即后进先出。


　　栈一般有两种实现，所有操作时间复杂度O(1)：


　　栈的链表实现：利用LinkedList类，通过表顶端的元素插入和删除。


　　栈的数组实现：模仿ArrayList类，和栈相关的有两个元素，arrayList数组和topOfStack索引，初始状态topOfStack==-1，每次进栈一个元素x，topOfStack增1并令arrayList[topOfStack]=x;每次出栈一个元素，我们置返回值arrayList[topOfStack]，并令topOfStack减1。


　　3.队列(Queue)


　　对于队列来说，元素只能从队列尾插入，从队列头访问和删除。普通的队列是一种先进先出(FirstInFirstOut，FIFO)的数据结构，而优先队列中，元素被赋予优先级。当访问元素的时候，具有高优先级的元素先被删除。


　　队列也是表，一般有两种实现，所有操作时间复杂度O(1)(优先队列是通过大顶堆或者小顶堆实现)：


　　队列的链表实现：利用LinkedList类，通过表尾端插入元素，前端删除元素，并记录队列中元素个数currentSize。


　　队列的数组实现：保留一个数组theArray以及位置front和back，代表队列的两端;同时还要记录队列中元素个数currentSize。要使一个元素x入队，则currentSize和back增1，theArray[back]=x;要使一个元素出队，我们置返回值theArray[front]，且currentSize减1,、front增1。采用循环数组的方式，当front和back到达数组的尾端，他们又绕回开头。


　　4.集合(Set)


　　元素无放入顺序，元素不可重复(注意：元素虽然无放入顺序，但是元素在set中的位置是由该元素的HashCode决定的，其位置其实是固定的)


　　Set接口有两个实现类：HashSet和LinkedHashSet


　　HashSet：(底层由HashMap实现)，HashSet类按照哈希算法来存取集合中的对象，存取速度比较快，存入HashSet的对象必须定义hashCode()和equals()来确保对象的性。


　　LinkedHashSet：具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。


　　SortedSet接口有一个实现类：TreeSet底层是通过TreeMap来实现的(如同HashSet底层是是通过HashMap来实现的一样)，因此二者的实现方式几乎完全一样。