java之路，LinkedList, Hash, Tree

 

一般将数据结构分为两大类：线性数据结构和非线性数据结构。线性数据结构有线性表、栈、队列、串、数组和文件；非线性数据结构有树和图。

线性表的逻辑结构是n个数据元素的有限序列:(a₁, a₂ ,a₃,…a_n) n为线性表的长度(n≥0)，n=0的表称为空表。

数据元素呈线性关系。必存在唯一的称为“第一个”的数据元素；必存在唯一的称为“最后一个”的数据元素；除第一个元素外，每个元素都有且只有一个前驱元素； 除最后一个元素外，每个元素都有且只有一个后继元素。

所有数据元素在同一个线性表中必须是相同的数据类型。

线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表；用链式存储结构存储的线性表称为链表。将线性表中的数据元素依次存放在某个存储区域中,所形成的表称为顺序表。一维数组就是用顺序方式存储的线性表。
 

LinkedList类：
LinkedList是采用双向循环链表实现的。
利用LinkedList实现栈(stack)、队列(queue)、双向队列(double-ended queue )。
数据结构：
一般将数据结构分为两大类：线性数据结构和非线性数据结构。线性数据结构有线性表、栈、队列、串、数组和文件；
非线性数据结构有树和图。
线性表：
线性表的逻辑结构是n个数据元素的有限序列:(a1, a2 ,a3,…an) n为线性表的长度(n≥0)，n=0的表称为空表。
数据元素呈线性关系。必存在唯一的称为“第一个”的数据元素；必存在唯一的称为“最后一个”的数据元素；除第一个元素外，每个元素都有且只有一个前驱元素； 除最后一个元素外，每个元素都有且只有一个后继元素。所有数据元素在同一个线性表中必须是相同的数据类型。
线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表；用链式存储结构存储的线性表称为链表。将线性表中的数据元素依次存放在某个存储区域中,所形成的表称为顺序表。一维数组就是用顺序方式存储的线性表。
栈：
栈(Stack)也是一种特殊的线性表，是一种后进先出(LIFO)的结构。
栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom)。
栈的物理存储可以用顺序存储结构，也可以用链式存储结构。

import java.util.*;
class MyStack
{
 private LinkedList li = new LinkedList();
 public void push(Object o)
 {
  li.addFirst(o);
 }
 public Object pop()
 {
  return li.removeFirst();    //一走并返回第一个元素
 }
 public Object peek()
 {
  return li.getFirst();       //查看并返回起一个元素
 }
 public boolean empty()
 {
  return li.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.pop());
  System.out.println(ms.empty());
 }
}

队列：
队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表。
表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front)。
队列的操作是按先进先出(FIFO)的原则进行的。
队列的物理存储可以用顺序存储结构，也可以用链式存储结构。

import java.util.*;
class MyQueue
{
 private LinkedList li = new LinkedList();
 public void push(Object o)
 {
  li.addLast(o);
 }
 public Object pop()
 {
  return li.removeFirst();    //取走并返回第一个元素
 }
 public Object peek()
 {
  return li.getFirst();       //查看并返回起一个元素
 }
 public boolean empty()
 {
  return li.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.pop());
  System.out.println(ms.empty());
 }
}

ArrayList底层采用数组完成，而LinkedList则是以一般的双向链表(double-linked list)完成，其内每个对象除了数据本身外，还有两个 引用，分别指向前一个元素和后一个元素。
如果我们经常在List的开始处增加元素，或者在List中进行插入和删除操作，我们应该使用LinkedList，否则的话，使用ArrayList将更加快速。

HashSet:
实现Set接口的hash table(哈希表)，依靠HashMap来实现的。
我们应该为要存放到散列表的各个对象定义hashCode()和equals()。
散列表又称为哈希表。散列表算法的基本思想是：
以结点的关键字为自变量，通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为该结点存储在散列表中的地址。
当散列表中的元素存放太满，就必须进行再散列，将产生一个新的散列表，所有元素存放到新的散列表中，原先的散列表将被删除。在Java语言中，通过负载因子(load factor)来决定何时对散列表进行再散列。例如：如果负载因子是0.75，当散列表中已经有75%的位置已经放满，那么将进行再散列。
负载因子越高(越接近1.0)，内存的使用效率越高，元素的寻找时间越长。负载因子越低(越接近0.0)，元素的寻找时间越短，内存浪费越多。
HashSet类的缺省负载因子是0.75。

class HashSetTest
{
 public static void main(String[] args)
 {
  HashSet hs = new HashSet();
 // hs.add("one");
 // hs.add("two");
 // hs.add("three");
 // hs.add("two");     //hashset 实现 了set接口，不可以有重复的接口
  hs.add(new Student(1,"one"));
  hs.add(new Student(2,"two"));
  hs.add(new Student(3,"three"));
  hs.add(new Student(1,"one"));   //产生的新对象，如果不重写hashCode方法，计算的hash值不一样
                                  //导致重复的值也被存入了
  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()   //hashCode根据对象的内存地址计算结果，要避免重复，必须重写hashCode()
 {
  return num*name.hashCode();
 }
 
 public boolean equals(Object o)    //还必须重写equals
 {
  Student st = (Student)o;
  return num == st.num && name.equals(st.name);
 }
 
 public String toString(Student s)
 {
  return "num =:" + num + "name=:" + name;
 }
}

TreeSet是依靠TreeMap来实现的。
TreeSet是一个有序集合，TreeSet中元素将按照升序排列，缺省是按照自然顺序进行排列，意味着TreeSet中元素要实现Comparable接口。
我们可以在构造TreeSet对象时，传递实现了Comparator接口的比较器对象。
import java.util.*;
class TreeSetTest
{
 public static void main(String[] args)
 {
  TreeSet ts = new TreeSet(new Student.StudentComparator());
 // ts.add("zhangsan");
 // ts.add("lisi");
 // ts.add("wangwu");
  
  ts.add(new Student(2, "zhangsan"));
  ts.add(new Student(3, "lisi"));
  ts.add(new Student(1, "wangwu"));
  ts.add(new Student(2, "zhangliu"));
  
  Iterator it = ts.iterator();
  while(it.hasNext())
  {
   System.out.println(it.next());
  }
 }
}

class Student implements Comparable  //实现Comparable接口
{
 int num;
 String name;
 Student(int num, String name)
 {
  this.num = num;
  this.name = name;
 }
 
 static class StudentComparator implements Comparator
 {
  public int compare(Object o1, Object o2)
  {
   Student s1 = (Student)o1;
   Student s2 = (Student)o2;
   int result = s1.num > s2.num ? 1 : (s1.num == s2.num ? 0 : -1);
   if(result == 0)
   {
    result = s1.name.compareTo(s2.name);   //学号相同，比较名字
   }
   return result;
  }
 }
 
 public int compareTo(Object o)    //覆盖compareTo方法
 {
  Student s = (Student)o;
  return num > s.num ? 1:(num == s.num ? 0: -1);
 }
 
 public String toString(Student s)
 {
  return "num =:" + num + "name=:" + name;
 }
}

HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。
我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。

HashMap对key进行散列。
keySet()、values()、entrySet()。

import java.util.*;
class HashMapTest
{
 public static void printElements(Collection c)   //打印元素
 {
  Iterator it = c.iterator();
  while(it.hasNext())
  {
   System.out.println(it.next()); 
  }
 }
 public static void main(String[] args)
 {
  HashMap hs = new HashMap();
  hm.put("one", "zhangsan");     //put增加元素
  hm.put("two", "lisi");
  hm.put("three", "wangwu");
  
  System.out.println(hs.get("one"));   //get获取key
  System.out.println(hs.get("two"));
  System.out.println(hs.get("three"));
  
  Set keys = hm.keySet();         //获取键key
  printElements(keys);
  Collection value = hm.values();  //返回键值
  printElements(value);
  Set entry = hm.entrySet();      //返回键值对
  printElements(entry);
 }
}
TreeMap按照key进行排序。
和Set类似，HashMap的速度通常都比TreeMap快，只有在需要排序的功能的时候，才使用TreeMap。