§ LinkedList
1)? LinkedList是采用雙向循環(huán)鏈表來實現(xiàn)的。
2)? 利用LinkedList實現(xiàn)Stack,queen,double-ended queen。
§ 數(shù)據(jù)結(jié)構(gòu)
?一般將數(shù)據(jù)結(jié)構(gòu)分為為兩大類：線性數(shù)據(jù)結(jié)構(gòu)，非線性數(shù)據(jù)結(jié)構(gòu)。線性數(shù)據(jù)結(jié)構(gòu)有線性表，棧，隊列，串，數(shù)組和文件；非線性數(shù)據(jù)結(jié)構(gòu)有樹和圖。
1) 線性表
a. 線性表的邏輯結(jié)構(gòu)是n個數(shù)據(jù)元素的有序隊列:
???? (a1,a2,a3,a4......an)
n為線性表的長度(n>>0), n=0 的表稱為空表。
b. 數(shù)據(jù)元素呈線性關(guān)系。必存在唯一的稱為“第一個”的數(shù)據(jù)元素；必存在唯一的稱為“最后一個”的數(shù)據(jù)元素；除第一個?? 元素外，每個元素都有且只有一個前驅(qū)元素；除最后一個元素外，其它的每個元素都有且只有一個后繼元素。
c. 所有數(shù)據(jù)元素在同一個線性表中必須是相同的數(shù)據(jù)類型。
d. 線性表按其存儲結(jié)構(gòu)可分為順序表和鏈表。用順序存儲結(jié)構(gòu)存儲的線性表稱為順序表；用鏈式結(jié)構(gòu)存儲的線性表稱為鏈表。
e. 將線性表中的數(shù)據(jù)元素依次存放在某個存儲區(qū)域中,所形成的表稱為線性表。一維數(shù)組就是順序方式存儲的線性表。
2) Stack
a.? Stack也是一種特殊的線性表,是一種后進先出(LIFO)的結(jié)構(gòu)。
b.? Stack是限定在表尾進行插入和刪除的線性表，表尾稱為棧頂(top),表頭稱為棧底(bottom)。
c.??Stack的物理存儲可以順序存儲結(jié)構(gòu)，也可以用鏈式存儲結(jié)構(gòu)。(即：可以用數(shù)組或鏈表實現(xiàn))?
actualize Stack:
import java.util.*;
class MyStack
{
?private LinkedList ll = new LinkedList();
?//要實現(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是限定所有的插入只能在表的一端進行，而所有的刪除在表的另一端進行的線性表。
b.? queen中允許插入的一端稱為隊尾(Rear)，允許刪除的一端稱為隊頭(Front)。
c.?? queen的操作是按先進先出(FIFO)的原則進行的。
d.?? queen的物理存儲可以用順序存儲結(jié)構(gòu)，也可以用鏈式存儲結(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)每個對象，除了數(shù)據(jù)本身外，還有兩個引用，分別指向前一個元素和后一個元素。
b. 如果我們經(jīng)常在List的開始處增加元素,或則在List中進行插入和刪除操作，我們應該使用LinkedList，否則的話，使用ArrayList則更快。
§ HashSet
1.?? 實現(xiàn)Set接口的hash table,依靠HashMap來實現(xiàn)。
2.?? 應該為存放到散列表中的各個對象定義hashCode()和equals()。
3.?? 散列表又稱哈希表。散列表算法的基本思想:
以節(jié)點的關(guān)鍵字為自變量，通過一定的函數(shù)關(guān)系(散列函數(shù))計算出對應的函數(shù)值，以這個值作為該節(jié)點存儲在散列表中的地址。
4.?? 當散列表中元素存放太滿，就必須再散列，將產(chǎn)生一個新的散列表,所有元素存放到新的散列表中,原先的散列表將被刪除。Jaav語言中，通過負載因子(load factor)來決定何時對散列表再進行散列。例如：如果負載因子是0.75,當散列表中有75%被存滿，將進行再散列。
5.?? 負載因子越高(離1.0越近)，內(nèi)存的使用效率越高,元素的尋找時間越長。負載因子越低(越接近0.0),元素的尋找時間越短，內(nè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;
?}
}