java中幾種常用數(shù)據(jù)結(jié)構(gòu)

java 中幾種常用數(shù)據(jù)結(jié)構(gòu)

Java中有幾種常用的數(shù)據(jù)結(jié)構(gòu)，主要分為Collection和map兩個主要接口（接口只提供方法，并不提供實現(xiàn)），而程序中最終使用的數(shù)據(jù)結(jié)構(gòu)是繼承自這些接口的數(shù)據(jù)結(jié)構(gòu)類。

一、幾個常用類的區(qū)別

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

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

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

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

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

二、Vector、ArrayList和LinkedList

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

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

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

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

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

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

三、Collections和Arrays

在Java集合類框架里有兩個類叫做Collections（注意，不是Collection?。┖虯rrays，這是JCF里面功能強大的工具，但初學者往往會忽視。按JCF文檔的說法，這兩個類提供了封裝器實現(xiàn)（Wrapper Implementations）、數(shù)據(jù)結(jié)構(gòu)算法和數(shù)組相關的應用。

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

binarySearch：折半查找。

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

reverse：將線性表進行逆序操作，這個可是從前數(shù)據(jù)結(jié)構(gòu)的經(jīng)典考題哦！

rotate：以某個元素為軸心將線性表“旋轉(zhuǎn)”。

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

……

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

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

synchronizedXXX：轉(zhuǎn)換成同步集合。

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

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

空集：由Collections的靜態(tài)屬性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表示。

數(shù)據(jù)結(jié)構(gòu)：

一。鏈表

1.鏈表與數(shù)組的區(qū)別

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

當需要動態(tài)的減少或增加數(shù)據(jù)項時，可以使用鏈表這種數(shù)據(jù)結(jié)構(gòu)。

2.java中用到鏈表舉例

LinkedList linkedList = new LinkedList（）;

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

linkedList.add（“I”）;

linkedList.add（“Iove”）;

linkedList.add（“it”）;

linkedList.add（“so”）;

linkedList.add（“much”）;

linkedList可以使用方法public Object get（index i）獲取第i個節(jié)點存儲的數(shù)據(jù)。

二。散列表（哈希表）

1.為什么使用散列表？

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

JAVA里幾種數(shù)據(jù)結(jié)構(gòu)的優(yōu)點和缺點

一般大家都知道ArrayList和LinkedList的大致區(qū)別：

1.ArrayList是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)。

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

3.對于新增和刪除操作add和remove，LinedList比較占優(yōu)勢，因為ArrayList要移動數(shù)據(jù)。

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

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

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

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

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

TreeSet ：TreeSet類實現(xiàn)了SortedSet接口，能夠?qū)现械膶ο筮M行排序。

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

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

List接口主要實現(xiàn)類包括：

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

LinkedList（）： 在實現(xiàn)中采用鏈表數(shù)據(jù)結(jié)構(gòu)。插入和刪除速度快，訪問速度慢。

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