java 中幾種常用數據結構

Java中有幾種常用的數據結構，主要分為Collection和map兩個主要接口（接口只提供方法，并不提供實現），而程序中最終使用的數據結構是繼承自這些接口的數據結構類。

一、幾個常用類的區別

1．ArrayList： 元素單個，效率高，多用于查詢

2．Vector： 元素單個，線程安全，多用于查詢

3．LinkedList：元素單個，多用于插入和刪除

4．HashMap： 元素成對，元素可為空

5．HashTable： 元素成對，線程安全，元素不可為空

二、Vector、ArrayList和LinkedList

大多數情況下，從性能上來說ArrayList最好，但是當集合內的元素需要頻繁插入、刪除時LinkedList會有比較好的表現，但是它們三個性能都比不上數組，另外Vector是線程同步的。所以：

如果能用數組的時候（元素類型固定，數組長度固定），請盡量使用數組來代替List；

如果沒有頻繁的刪除插入操作，又不用考慮多線程問題，優先選擇ArrayList；

如果在多線程條件下使用，可以考慮Vector；

如果需要頻繁地刪除插入，LinkedList就有了用武之地；

如果你什么都不知道，用ArrayList沒錯。

三、Collections和Arrays

在Java集合類框架里有兩個類叫做Collections（注意，不是Collection！）和Arrays，這是JCF里面功能強大的工具，但初學者往往會忽視。按JCF文檔的說法，這兩個類提供了封裝器實現（Wrapper Implementations）、數據結構算法和數組相關的應用。

想必大家不會忘記上面談到的“折半查找”、“排序”等經典算法吧，Collections類提供了豐富的靜態方法幫助我們輕松完成這些在數據結構課上煩人的工作：

binarySearch：折半查找。

sort：排序，這里是一種類似于快速排序的方法，效率仍然是O（n * log n），但卻是一種穩定的排序方法。

reverse：將線性表進行逆序操作，這個可是從前數據結構的經典考題哦！

rotate：以某個元素為軸心將線性表“旋轉”。

swap：交換一個線性表中兩個元素的位置。

……

Collections還有一個重要功能就是“封裝器”（Wrapper），它提供了一些方法可以把一個集合轉換成一個特殊的集合，如下：

unmodifiableXXX：轉換成只讀集合，這里XXX代表六種基本集合接口：Collection、List、Map、Set、SortedMap和SortedSet。如果你對只讀集合進行插入刪除操作，將會拋出UnsupportedOperationException異常。

synchronizedXXX：轉換成同步集合。

singleton：創建一個僅有一個元素的集合，這里singleton生成的是單元素Set，

singletonList和singletonMap分別生成單元素的List和Map。

空集：由Collections的靜態屬性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表示。

數據結構：

一。鏈表

1.鏈表與數組的區別

數組在使用之前必須定義大小，而且不能動態定義大小，會造成給數組分配了太多的單元而浪費了寶貴的資源，糟糕的一面是，程序運行時需要處理的數據可能多于數組的單元。

當需要動態的減少或增加數據項時，可以使用鏈表這種數據結構。

2.java中用到鏈表舉例

LinkedList linkedList = new LinkedList（）;

創建一個空鏈表，然后linkedList 鏈表可以使用add（）方法向這個鏈表依次增加節點。例如：

linkedList.add（“I”）;

linkedList.add（“Iove”）;

linkedList.add（“it”）;

linkedList.add（“so”）;

linkedList.add（“much”）;

linkedList可以使用方法public Object get（index i）獲取第i個節點存儲的數據。

二。散列表（哈希表）

1.為什么使用散列表？

對于數組和鏈表這兩種數據結構，如果要查找它們存儲的某個特定元素卻不知道它的位置，就需要從頭開始訪問元素直到找到匹配的為止；如果數據結構中包含很多的元素，就會浪費時間。這時最好使用散列表來存儲要查找的數據。

JAVA里幾種數據結構的優點和缺點

一般大家都知道ArrayList和LinkedList的大致區別：

1.ArrayList是實現了基于動態數組的數據結構，LinkedList基于鏈表的數據結構。

2.對于隨機訪問get和set，ArrayList覺得優于LinkedList，因為LinkedList要移動指針。

3.對于新增和刪除操作add和remove，LinedList比較占優勢，因為ArrayList要移動數據。

這一點要看實際情況的。若只對單條數據插入或刪除，ArrayList的速度反而優于LinkedList。但若是批量隨機的插入刪除數據，LinkedList的速度大大優于ArrayList. 因為ArrayList每插入一條數據，要移動插入點及之后的所有數據。

4.查找操作indexOf，lastIndexOf，contains等，兩者差不多。

5.隨機查找指定節點的操作get，ArrayList速度要快于LinkedList.

Set是最簡單的一種集合。集合中的對象不按特定的方式排序，并且沒有重復對象。 Set接口主要實現了兩個實現類：

HashSet： HashSet類按照哈希算法來存取集合中的對象，存取速度比較快

TreeSet ：TreeSet類實現了SortedSet接口，能夠對集合中的對象進行排序。

Set 的用法：存放的是對象的引用，沒有重復對象

List的特征是其元素以線性方式存儲，集合中可以存放重復對象。

List接口主要實現類包括：

ArrayList（） ： 代表長度可以改變得數組。可以對元素進行隨機的訪問，向ArrayList（）中插入與刪除元素的速度慢。

LinkedList（）： 在實現中采用鏈表數據結構。插入和刪除速度快，訪問速度慢。

對于List的隨機訪問來說，就是只隨機來檢索位于特定位置的元素。 List 的 get（int index） 方法放回集合中由參數index指定的索引位置的對象，下標從“0” 開始。最基本的兩種檢索集合中的所有對象的方法。