§ LinkedList
1)? LinkedList是采用雙向循環(huán)鏈表來(lái)實(shí)現(xiàn)的。
2)? 利用LinkedList實(shí)現(xiàn)Stack,queen,double-ended queen。
§ 數(shù)據(jù)結(jié)構(gòu)
?一般將數(shù)據(jù)結(jié)構(gòu)分為為兩大類(lèi)：線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。線(xiàn)性數(shù)據(jù)結(jié)構(gòu)有線(xiàn)性表，棧，隊(duì)列，串，數(shù)組和文件；非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)有樹(shù)和圖。
1) 線(xiàn)性表
a. 線(xiàn)性表的邏輯結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有序隊(duì)列:
???? (a1,a2,a3,a4......an)
n為線(xiàn)性表的長(zhǎng)度(n>>0), n=0 的表稱(chēng)為空表。
b. 數(shù)據(jù)元素呈線(xiàn)性關(guān)系。必存在唯一的稱(chēng)為“第一個(gè)”的數(shù)據(jù)元素；必存在唯一的稱(chēng)為“最后一個(gè)”的數(shù)據(jù)元素；除第一個(gè)?? 元素外，每個(gè)元素都有且只有一個(gè)前驅(qū)元素；除最后一個(gè)元素外，其它的每個(gè)元素都有且只有一個(gè)后繼元素。
c. 所有數(shù)據(jù)元素在同一個(gè)線(xiàn)性表中必須是相同的數(shù)據(jù)類(lèi)型。
d. 線(xiàn)性表按其存儲(chǔ)結(jié)構(gòu)可分為順序表和鏈表。用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線(xiàn)性表稱(chēng)為順序表；用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)的線(xiàn)性表稱(chēng)為鏈表。
e. 將線(xiàn)性表中的數(shù)據(jù)元素依次存放在某個(gè)存儲(chǔ)區(qū)域中,所形成的表稱(chēng)為線(xiàn)性表。一維數(shù)組就是順序方式存儲(chǔ)的線(xiàn)性表。
2) Stack
a.? Stack也是一種特殊的線(xiàn)性表,是一種后進(jìn)先出(LIFO)的結(jié)構(gòu)。
b.? Stack是限定在表尾進(jìn)行插入和刪除的線(xiàn)性表，表尾稱(chēng)為棧頂(top),表頭稱(chēng)為棧底(bottom)。
c.??Stack的物理存儲(chǔ)可以順序存儲(chǔ)結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(即：可以用數(shù)組或鏈表實(shí)現(xiàn))?
actualize Stack:
import java.util.*;
class MyStack
{
?private LinkedList ll = new LinkedList();
?//要實(shí)現(xiàn)LIFO
?public void push(Object o){
??ll.addFirst(o);
?}
?public Object pop(){
??//出棧
??return ll.removeFirst();
?}
?public Object peek(){
??//查看棧頂元素，但是不移走
??return ll.getFirst();
?}
?public boolean empty(){
??//判斷是否為空
??return ll.isEmpty();
?}
?
?public static void main(String[] args){
??MyStack ms = new MyStack();
??ms.push("one");
??ms.push("two");
??ms.push("three");
??ms.push("four");
??
??System.out.println(ms.pop());
??System.out.println(ms.peek());
??System.out.println(ms.empty());
?}
}
3) Queen
a.? queen是限定所有的插入只能在表的一端進(jìn)行，而所有的刪除在表的另一端進(jìn)行的線(xiàn)性表。
b.? queen中允許插入的一端稱(chēng)為隊(duì)尾(Rear)，允許刪除的一端稱(chēng)為隊(duì)頭(Front)。
c.?? queen的操作是按先進(jìn)先出(FIFO)的原則進(jìn)行的。
d.?? queen的物理存儲(chǔ)可以用順序存儲(chǔ)結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
actualize Stack:
import java.util.*;
class MyQueen
{
?? private LinkedList aa = new LinkedList();
?? public void put(Object o){
????? //添加元素
????? aa.addLast(o);
?? }
??
?? public Object get(){
????? //獲得元素
????? return aa.removeFirst();
?? }
??
?? public boolean empty(){
???? return aa.isEmpty();
?? }
??
?? public static void main(String[] args){
????? MyQueen mq = new MyQueen();
????? mq.put("one");
????? mq.put("two");
????? mq.put("three");
?????
????? System.out.println(mq.get());
????? System.out.println(mq.empty());
?? }
}
¤ ArrayList 與 LinkedList
a. ArrayList底層采用數(shù)組完成，而LinkedList則是以一般的雙向鏈表(double-linked list)完成，其內(nèi)每個(gè)對(duì)象，除了數(shù)據(jù)本身外，還有兩個(gè)引用，分別指向前一個(gè)元素和后一個(gè)元素。
b. 如果我們經(jīng)常在List的開(kāi)始處增加元素,或則在List中進(jìn)行插入和刪除操作，我們應(yīng)該使用LinkedList，否則的話(huà)，使用ArrayList則更快。
§ HashSet
1.?? 實(shí)現(xiàn)Set接口的hash table,依靠HashMap來(lái)實(shí)現(xiàn)。
2.?? 應(yīng)該為存放到散列表中的各個(gè)對(duì)象定義hashCode()和equals()。
3.?? 散列表又稱(chēng)哈希表。散列表算法的基本思想:
以節(jié)點(diǎn)的關(guān)鍵字為自變量，通過(guò)一定的函數(shù)關(guān)系(散列函數(shù))計(jì)算出對(duì)應(yīng)的函數(shù)值，以這個(gè)值作為該節(jié)點(diǎn)存儲(chǔ)在散列表中的地址。
4.?? 當(dāng)散列表中元素存放太滿(mǎn)，就必須再散列，將產(chǎn)生一個(gè)新的散列表,所有元素存放到新的散列表中,原先的散列表將被刪除。Jaav語(yǔ)言中，通過(guò)負(fù)載因子(load factor)來(lái)決定何時(shí)對(duì)散列表再進(jìn)行散列。例如：如果負(fù)載因子是0.75,當(dāng)散列表中有75%被存滿(mǎn)，將進(jìn)行再散列。
5.?? 負(fù)載因子越高(離1.0越近)，內(nèi)存的使用效率越高,元素的尋找時(shí)間越長(zhǎng)。負(fù)載因子越低(越接近0.0),元素的尋找時(shí)間越短，內(nèi)存浪費(fèi)越多。
6.?? HashSet的缺省因子是0.75。
HashSet demo:
import java.util.*;
class HashSetTest
{
?public static void main(String[] args){
??HashSet hs = new HashSet();
???
??hs.add(new Student("zhangsan",1));
??hs.add(new Student("lisi",2));
??hs.add(new Student("wangwu",3));
??hs.add(new Student("zhangsan",1));
??
??Iterator it = hs.iterator();
??while(it.hasNext()){
???System.out.println(it.next());
??}
?}
}
class Student
{
? String name;
? int num;
?
?public Student(String name,int num){
??this.name = name;
??this.num = num;
?}
?
?public int hashCode(){
??return num * name.hashCode();
?}
?
?public boolean equals(Object o){
??Student s =(Student)o;
??return num==s.num && name.equals(s.name);
?}
?
?public String toString(){
??return num+":"+name;
?}
}