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

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

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

一、幾個(gè)常用類(lèi)的區(qū)別

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

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

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

4．HashMap： 元素成對(duì)，元素可為空

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

二、Vector、ArrayList和LinkedList

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

如果能用數(shù)組的時(shí)候（元素類(lèi)型固定，數(shù)組長(zhǎng)度固定），請(qǐng)盡量使用數(shù)組來(lái)代替List；

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

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

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

如果你什么都不知道，用ArrayList沒(méi)錯(cuò)。

三、Collections和Arrays

在Java集合類(lèi)框架里有兩個(gè)類(lèi)叫做Collections（注意，不是Collection！）和Arrays，這是JCF里面功能強(qiáng)大的工具，但初學(xué)者往往會(huì)忽視。按JCF文檔的說(shuō)法，這兩個(gè)類(lèi)提供了封裝器實(shí)現(xiàn)（Wrapper Implementations）、數(shù)據(jù)結(jié)構(gòu)算法和數(shù)組相關(guān)的應(yīng)用。

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

binarySearch：折半查找。

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

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

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

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

……

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

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

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

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

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

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

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

一。鏈表

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

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

當(dāng)需要?jiǎng)討B(tài)的減少或增加數(shù)據(jù)項(xiàng)時(shí)，可以使用鏈表這種數(shù)據(jù)結(jié)構(gòu)。

2.java中用到鏈表舉例

LinkedList linkedList = new LinkedList（）;

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

linkedList.add（“I”）;

linkedList.add（“Iove”）;

linkedList.add（“it”）;

linkedList.add（“so”）;

linkedList.add（“much”）;

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

二。散列表（哈希表）

1.為什么使用散列表？

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

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

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

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

2.對(duì)于隨機(jī)訪問(wèn)get和set，ArrayList覺(jué)得優(yōu)于LinkedList，因?yàn)長(zhǎng)inkedList要移動(dòng)指針。

3.對(duì)于新增和刪除操作add和remove，LinedList比較占優(yōu)勢(shì)，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)。

這一點(diǎn)要看實(shí)際情況的。若只對(duì)單條數(shù)據(jù)插入或刪除，ArrayList的速度反而優(yōu)于LinkedList。但若是批量隨機(jī)的插入刪除數(shù)據(jù)，LinkedList的速度大大優(yōu)于ArrayList. 因?yàn)锳rrayList每插入一條數(shù)據(jù)，要移動(dòng)插入點(diǎn)及之后的所有數(shù)據(jù)。

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

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

Set是最簡(jiǎn)單的一種集合。集合中的對(duì)象不按特定的方式排序，并且沒(méi)有重復(fù)對(duì)象。 Set接口主要實(shí)現(xiàn)了兩個(gè)實(shí)現(xiàn)類(lèi)：

HashSet： HashSet類(lèi)按照哈希算法來(lái)存取集合中的對(duì)象，存取速度比較快

TreeSet ：TreeSet類(lèi)實(shí)現(xiàn)了SortedSet接口，能夠?qū)现械膶?duì)象進(jìn)行排序。

Set 的用法：存放的是對(duì)象的引用，沒(méi)有重復(fù)對(duì)象

List的特征是其元素以線性方式存儲(chǔ)，集合中可以存放重復(fù)對(duì)象。

List接口主要實(shí)現(xiàn)類(lèi)包括：

ArrayList（） ： 代表長(zhǎng)度可以改變得數(shù)組?？梢詫?duì)元素進(jìn)行隨機(jī)的訪問(wèn)，向ArrayList（）中插入與刪除元素的速度慢。

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

對(duì)于List的隨機(jī)訪問(wèn)來(lái)說(shuō)，就是只隨機(jī)來(lái)檢索位于特定位置的元素。 List 的 get（int index） 方法放回集合中由參數(shù)index指定的索引位置的對(duì)象，下標(biāo)從“0” 開(kāi)始。最基本的兩種檢索集合中的所有對(duì)象的方法。