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