java技术从入门到精通(孙鑫)学习笔记Lesson 6（数据结构）

java技术从入门到精通(孙鑫)学习笔记Lesson 6（数据结构） LinkedList , LinkedList是采用双向循环链实现的。 , 利用工作之便LinkedList实现栈（stack）、队列（queue）、双向队列 （double-ended queue）。 import java.util.*; class MyStack { private LinkedList ll=new LinkedList(); 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"); System.out.println(ms.pop()); System.out.println(ms.peek()); System.out.println(ms.pop()); System.out.println(ms.empty()); } } 运行结果为： three two two false import java.util.*; class MyQueue { private LinkedList ll=new LinkedList(); public void put(Object o) { ll.addLast(o); } public Object get() { return ll.removeFirst(); } public boolean empty() { return ll.isEmpty(); } public static void main(String[] args) { MyQueue mq=new MyQueue(); mq.put("one"); mq.put("two"); mq.put("three"); System.out.println(mq.get()); System.out.println(mq.get()); System.out.println(mq.get()); System.out.println(mq.empty()); } } 运行结果为： one two three ArrayListLinkedList , ArrayList底层采用数组完成，而LinkedList则是以一般的双向链表 (double-linked list)完成，其内每个对象除了数据本身外，还有两个引用，分 别指向前一个元素和后一个元素。 , 如果我们经常在List的开始处增加元素，或者在 List中进行插入和删除操作， 我们应该使用LinkedList，否则的话，使用ArrayList将更加快速。 HashSet , 实现Set接口（）的hash table（哈希表），依靠HashMap来 实现的。 import java.util.*; class HashSetTest { public static void main(String[] args) { HashSet hs=new HashSet(); hs.add("one"); hs.add("two"); hs.add("three"); hs.add("one"); Iterator it=hs.iterator(); while(it.hasNext()) { System.out.println(it.next()); } } } 运行结果为： one two three import java.util.*; class HashSetTest { public static void main(String[] args) { HashSet hs=new HashSet(); hs.add(new Student(1,"zhangsan")); hs.add(new Student(2,"lisi")); hs.add(new Student(3,"wangwu")); hs.add(new Student(1,"zhangsan")); Iterator it=hs.iterator(); while(it.hasNext()) { System.out.println(it.next()); } } } class Student { int num; String name; Student(int num,String name) { this.num=num; this.name=name; } public String toString() { return num+":"+name; } } 运行结果为： 3：wangwu 2：lisi 1：zhangsan 1：zhangsan , 我们应该为要存放到散列表的各个对象定义hashCode()和equals()。 import java.util.*; class HashSetTest { public static void main(String[] args) { HashSet hs=new HashSet(); hs.add(new Student(1,"zhangsan")); hs.add(new Student(2,"lisi")); hs.add(new Student(3,"wangwu")); hs.add(new Student(1,"zhangsan")); Iterator it=hs.iterator(); while(it.hasNext()) { System.out.println(it.next()); } } } class Student { int num; String name; Student(int num,String name) { this.num=num; this.name=name; } 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; } } 运行结果为： 1：zhangsan 3：wangwu 2：lisi , 散列表又称为哈希表。散列表算法的基本思想是：以结点的关键字为自变量， 通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为该结 点存储在散列表中的地址。 , 当散列表中的元素存放太满，就必须进行再散列，将产生一个新的散列表， 所有元素存放到新的散列表中，原先的散列表将被删除。在Java语言中，通 过负载因子（load factor）来决定何时对散列表再散列。例如：如果负载因子 是0.75,当散列表中已经有75%的位置已经放满，那么将进行再散列。 , 负载因子越高（越接近1.0），内存的使用效率越高，元素的寻找时间越长。 负载因子越低（越接近0.0），元素的寻找时间越短，内存浪费越多。 , HashSet类的缺省负载因子是0.75。 TreeSet , TreeSet是依靠TreeMap来实现的。 , TreeSet是一个有序集合，TreeSet中元素将按照升序排列，缺省是按照自然 顺序进行排列，意味着TreeSet中元素要实现Comparable接口。 , 我们可以在构造TreeSet对象时，传递实现了Comparator接口的比较器对象。 import java.util.*; class TreeSetTest { public static void main(String[] args) { TreeSet ts=new TreeSet(); ts.add("winsun"); ts.add("weixin"); ts.add("mybole"); Iterator it=ts.iterator(); while(it.hasNext()) { System.out.println(it.next()); } } } 运行结果为： mybole weixin winsun HashSetTreeSet , HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。我们通常都 应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。