I. 第一部分：常見數(shù)據(jù)結(jié)構(gòu)
首先簡(jiǎn)單說下數(shù)據(jù)結(jié)構(gòu).
什么是數(shù)據(jù)結(jié)構(gòu)畦攘？數(shù)據(jù)結(jié)構(gòu)就是組織數(shù)據(jù)的方式.
常見的數(shù)據(jù)結(jié)構(gòu)：棧霸妹，堆，樹知押，圖叹螟，數(shù)組，隊(duì)列台盯，鏈表.
這里主要介紹與java集合體系相關(guān)的棧首妖、數(shù)組和鏈表.
棧
特點(diǎn)：壓棧彈棧，先進(jìn)后出.
如：手槍彈夾裝彈過程爷恳，最先壓入的子彈在最下面有缆；而在射擊時(shí)，最先彈入槍膛的是最上面的子彈，即最后壓入彈夾的子彈.
隊(duì)列
特點(diǎn)：先進(jìn)先出.
如：子彈射出的過程棚壁，先進(jìn)入槍膛的子彈最先被射出.
數(shù)組
概述：用來存儲(chǔ)同一種類型元素的容器杯矩。
特點(diǎn)：在內(nèi)存中是連續(xù)的，每個(gè)元素都有編號(hào)（從0開始的）袖外，方便獲取史隆。但增刪就比較麻煩，需要將目標(biāo)位置后的所有數(shù)據(jù)前移動(dòng)或后移.
查詢快曼验，增刪慢.
鏈表
概述：把一些結(jié)點(diǎn)通過鏈子連接起來的數(shù)據(jù)結(jié)構(gòu)泌射。每個(gè)結(jié)點(diǎn)由地址域和數(shù)值域組成.
特點(diǎn)：增刪快，查詢慢. 增刪時(shí)鬓照，只需要把所插入處的前后節(jié)點(diǎn)鏈條斷開熔酷，增加或移除目標(biāo)節(jié)點(diǎn)，速度很快豺裆。反之拒秘，查詢時(shí)則需要遍歷所有節(jié)點(diǎn)，直到找到目標(biāo)節(jié)點(diǎn)臭猜，速度自然要慢躺酒。
II. 第二部分：Java中的Collection(集合)體系
2.1 集合體系概覽：
集合體系分為4大塊：
Collection接口:
Collection是最基本集合接口，它定義了一組允許重復(fù)的對(duì)象.
它有兩個(gè)子接口：List和Set.
1. List下3個(gè)實(shí)現(xiàn)類：ArrayList, LinkedList, Vector. List是有序的蔑歌。
1.1 List接口的三個(gè)兒子的特點(diǎn)：
1.1.1 ArrayList：底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組羹应，查詢快，增刪慢次屠。線程不安全（不同步）园匹，效率高。
1.1.2 Vector：底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組帅矗，查詢快偎肃，增刪慢。線程安全浑此，效率低累颂。
1.1.3 LinkedList：底層數(shù)據(jù)結(jié)構(gòu)是鏈表，增刪快凛俱，查詢慢紊馏。 線程不安全的，效率高蒲犬。
1.2 如何來選擇使用哪個(gè)仔呢朱监？
keywords: 看需求!
step1: 看是否考慮安全? 安全, 則Vector.
step2: 如果不考慮安全，那么是查詢多還是增刪多?
查詢多, 則ArrayList; 增刪多原叮，則LinkedList.
什么都不知道赫编，用ArrayList巡蘸。
2. Set下2個(gè)實(shí)現(xiàn)類：HashSet, TreeSet. Set是無序的。
Map接口：
該接口描述了從不重復(fù)的鍵到值的映射擂送。Map接口用于維護(hù)鍵/值對(duì).
特征：它描述了從不重復(fù)的鍵到值的映射.
兩個(gè)重要的實(shí)現(xiàn)類：HashMap和TreeMap.
1.HashMap悦荒，中文叫散列表，基于哈希表實(shí)現(xiàn)嘹吨，特點(diǎn)就是鍵值對(duì)的映射關(guān)系搬味。一個(gè)key對(duì)應(yīng)一個(gè)Value。
HashMap中元素的排列順序是不固定的蟀拷。更加適合于對(duì)元素進(jìn)行插入碰纬、刪除和定位。
2.TreeMap问芬，基于紅黑樹實(shí)現(xiàn)悦析。TreeMap中的元素保持著某種固定的順序。更加適合于對(duì)元素的順序遍歷愈诚。
Comaprable接口：
Comparable可以用于比較的實(shí)現(xiàn)她按，實(shí)現(xiàn)了Comparable接口的類可以通過實(shí)現(xiàn)comparaTo方法從而確定該類對(duì)象的排序方式牛隅。
Iterator接口：
用于循環(huán)訪問集合中的對(duì)象炕柔。
所有實(shí)現(xiàn)了Collection接口的容器類都有iterator方法，用于返回一個(gè)實(shí)Iterator接口的對(duì)象媒佣。
Iterator對(duì)象稱作迭代器匕累，Iterator接口方法能以迭代方式逐個(gè)訪問集合中各個(gè)元素，并可以從Collection中除去適當(dāng)?shù)脑亍?2.2 Collection的接口概覽(List 和 Set)
2.2.1 List接口
三個(gè)子類：
ArrayList
底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組默伍，查詢快欢嘿，增刪慢。
線程不安全（不同步）也糊，效率高炼蹦。
-Vector
底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，查詢快狸剃，增刪慢掐隐。
線程安全，效率低钞馁。
特有功能:
添加：
void addElement(Object obj);
獲嚷鞘 ：
Object elementAt(int index);
Enumeration elements(); //它返回此向量的組件的枚舉,類似于迭代器Iterator
boolean hasMoreElements() //類似于hasNext()
Object nextElement(); //類似于next();
-LinkedList
底層數(shù)據(jù)結(jié)構(gòu)是鏈表，增刪快僧凰，查詢慢探颈。
線程不安全的，效率高训措。
特有方法：
添加：
void addFirst(Object obj);//頭部添加元素
void addLast(Object obj);//尾部添加元素
獲任苯凇：
Object getFirst();//獲取頭部元素
Object getLast();//獲取尾部元素
刪除：
Object removeFirst();//移除頭部元素
Object removeLast();//移除尾部元素
#問：以后用List體系的那個(gè)子類光羞？
看是否考慮安全。
安全：用Vector
不安全：繼續(xù)考慮是查詢多還是增刪多
查詢多：ArrayList
增刪多：LinkedList
什么都不知道怀大，用ArrayList狞山。
#練習(xí)題：
1.一個(gè)字符串集合ArrayList中含有如下元素：hello, world, java, hello, .net, java, php, ios, java, android，world叉寂。要求編寫程序萍启，獲得一個(gè)沒有重復(fù)元素的新集合。
#思路：
1屏鳍、創(chuàng)建兩個(gè)集合對(duì)象勘纯，A，B钓瞭。
2驳遵、把字符串添加到集合A中。
3山涡、遍歷集合A堤结，并且判斷集合B中是否包含A集合當(dāng)前遍歷到的元素。
4鸭丛、如果包含竞穷，不添加，如果不包含鳞溉，就將該元素添加到集合B中瘾带。
5、迭代結(jié)束后熟菲，集合B中存的就是去重后的元素看政。
練習(xí)題
#請(qǐng)用LinkedList來模擬棧的數(shù)據(jù)結(jié)構(gòu)。
剛我們知道棧的結(jié)構(gòu)為：先進(jìn)后出.
咱們可以使用LinkedList集合抄罕，對(duì)這個(gè)類進(jìn)行包裝來實(shí)現(xiàn)先進(jìn)先出的效果允蚣，但不能直接使用它。
具體實(shí)現(xiàn)時(shí)呆贿，先往集合里添加一個(gè)新數(shù)據(jù)嚷兔，add(); 取自己寫類，對(duì)LinkedList進(jìn)行封裝：
1榨崩、需要提供添加元素的方法add() //內(nèi)部封裝的是：addFirst()
2谴垫、需要提供獲取元素的方法get(int index) //內(nèi)部封裝的是：List體系的get(int index)方法
3、需要提供獲取集合長(zhǎng)度的方法size() //內(nèi)部分裝的是：LinkedList的size()方法
以后遇到類似的題母蛛，怎么做翩剪？
解題思路：
1、分析要模擬的數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)彩郊。
2前弯、對(duì)可用的類進(jìn)行包裝蚪缀，然后提供對(duì)應(yīng)的方法就可以了。
2.2 Set集合
set集合的特點(diǎn): 無序,唯一
2.2.1 HashSet集合
A:底層數(shù)據(jù)結(jié)構(gòu)是哈希表(是一個(gè)元素為鏈表的數(shù)組)
B:哈希表底層依賴兩個(gè)方法：hashCode()和equals()
如何保證元素唯一性?
由hashCode()和equals()保證的恕出，先調(diào)用hashCode()在調(diào)用equals().
執(zhí)行順序：
首先比較哈希值是否相同:
若相同：
繼續(xù)執(zhí)行equals()方法询枚；
-返回true：元素重復(fù)了，不添加浙巫；
-返回false：直接把元素添加到集合金蜀；
若不同：
就直接把元素添加到集合；
2.2.2 TreeSet集合
A:底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹(是一個(gè)自平衡的二叉樹)
B:保證元素的排序方式
排序方法：
a:自然排序(元素具備比較性)：讓元素所屬的類實(shí)現(xiàn)Comparable接口.
b:比較器排序(集合具備比較性)：讓集合構(gòu)造方法接收Comparator的實(shí)現(xiàn)類對(duì)象
2.3 Map接口概覽
Map也是接口的畴，但沒有繼承Collection接口渊抄。該接口描述了從不重復(fù)的鍵到值的映射。Map接口用于維護(hù)鍵/值對(duì)（key/value pairs）丧裁。
特征：它描述了從不重復(fù)的鍵到值的映射护桦。
兩個(gè)重要的實(shí)現(xiàn)類：HashMap和TreeMap
1.HashMap，中文叫散列表煎娇，基于哈希表實(shí)現(xiàn)二庵，特點(diǎn)就是鍵值對(duì)的映射關(guān)系。一個(gè)key對(duì)應(yīng)一個(gè)Value缓呛。HashMap中元素的排列順序是不固定的催享。更加適合于對(duì)元素進(jìn)行插入、刪除和定位强经。
2.TreeMap睡陪，基于紅黑書實(shí)現(xiàn)寺渗。TreeMap中的元素保持著某種固定的順序匿情。更加適合于對(duì)元素的順序遍歷。
總結(jié)
|-List
有序,可重復(fù)
|--ArrayList
底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組信殊，查詢快炬称，增刪慢.
線程不安全，效率高.
|--Vector
底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組涡拘，查詢快玲躯，增刪慢.
線程安全，效率低.
|--LinkedList
底層數(shù)據(jù)結(jié)構(gòu)是鏈表鳄乏，查詢慢跷车，增刪快.
線程不安全，效率高.
|-Set
無序,唯一
|--HashSet
底層數(shù)據(jù)結(jié)構(gòu)是哈希表.
保證元素唯一性: 依賴兩個(gè)方法：hashCode()和equals().
|--LinkedHashSet
底層數(shù)據(jù)結(jié)構(gòu)是鏈表和哈希表
由鏈表保證元素有序
由哈希表保證元素唯一
|--TreeSet
底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹橱野。
如何保證元素排序? 自然排序; 比較器排序.
如何保證元素唯一性的呢? 根據(jù)比較的返回值是否是0來決定.
4:針對(duì)Collection集合我們到底使用誰?
唯一么? 是：Set; 否：List.
若用Set： 排序么? 是：TreeSet; 否：HashSet. 如果知道是Set朽缴，但是不知道是哪個(gè)Set，就用HashSet. 要安全嗎?是：Vector; 否：ArrayList或者LinkedList.
若用List: 查詢多：ArrayList 增刪多：LinkedList 如果你知道是List水援，但是不知道是哪個(gè)List密强，就用ArrayList.
如果你知道是Collection集合茅郎，但是不知道使用誰，就用ArrayList或渤。
如果你知道用集合系冗，就用ArrayList。
5:在集合中常見的數(shù)據(jù)結(jié)構(gòu)(掌握)
ArrayXxx:底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組薪鹦，查詢快掌敬，增刪慢； LinkedXxx:底層數(shù)據(jù)結(jié)構(gòu)是鏈表池磁，查詢慢涝开，增刪快； HashXxx:底層數(shù)據(jù)結(jié)構(gòu)是哈希表框仔。依賴兩個(gè)方法：hashCode()和equals()舀武； TreeXxx:底層數(shù)據(jù)結(jié)構(gòu)是二叉樹。兩種方式排序：自然排序和比較器排序离斩；
