§ 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;
}
}