java-栈、队列、数组、链表、Hash、树以及集合（一）

引言 在这里主要介绍一些比较重要的算法：栈、队列、数组、链表、Hash、树以及集合的概念 栈：先进后出 队列：先进先出，横向队列，存入取出 有关栈和队列的具体存储数据的过程，可以通过有关图片进行理解： 链表：通过一个链子把多个结点（元素）连接起来，由数据和地址组成的一个元素， 节点本身必须有一个地址值（就是下一个元素的地址值） 特点：查询慢，增删快 链表与数组刚好相反，对于数组而言，数组的特点是：查询快，增删慢 链表和数组的关系同样可以通过图示来进行理解： 链表分类： 单向链表：数据+下一个元素的地址 双向链表 ：数据+下一个元素的地址+上一个元素的地址 单向循环链表 ：最后一个元素存储的地址是第一个元素的地址值 双向循环链表：存储的是两个地址，最后一个元素所存储的两个地址分别是上一个元素的地址和第一个元素的地址 hash:一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的信息压缩到某一固定长度的消息摘要的函数。这个概念理解起来有点困难，但是后面遇到有关hash的使用后，就不会太难了。 二叉树，有关二叉树的概念，在这里，通过一张图解进行理解： 集合 为什么会用到集合呢？那么就有必要强调一下集合与数组的区别，因为数组不适应变化的需求，用一个案例来理解。 需求：存储5个学生对象，并输出学生对象的数据信息。 用数组的思想去分析: A:定义学生类(name,age) B:定义学生数组，用于存储学生对象 C:创建学生对象，给学生对象的成员变量赋值 D:把创建好的学生对象添加到数组中 E:遍历数组。 如果换成集合来理解： 在集合中存储3个学生对象，并遍历,拿出每一个学生对象的属性。 1.创建学生对象 2.创建集合 3.将学生对象添加到集合中 4.遍历集合 有关代码实现如下： 在这里，代码部分共用一个学生类，在自己进行编写的时候，分开来写，在不同包下进行测试。

//学生的javabean package com.stu01; public class Student { private String name; private int age; public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } public Student(String name, int age) { super(); this.name = name; this.age = age; } public Student() { super(); // TODO Auto-generated constructor stub } } //数组 package com.stu02; public class StudentTest { private static final Student[] Student = null; public static void main(String[] args) { Student s1 = new Student("薛之谦",35); Student s2 = new Student("周杰伦",36); Student[] arr=new Student[2]; arr[0]=s1; arr[1]=s2; for(int i=0;i<arr.length;i++){ System.out.println(arr[i].getName()+" "+arr[i].getAge()); } } } //集合 package com.stu01; import java.util.ArrayList; import java.util.Collection; //在集合中存储5个学生对象，并遍历,拿出每一个学生对象的属性。 public class StudentTest { public static void main(String[] args) { Student s1 = new Student("章子怡",45); Student s2 = new Student("郭德纲",55); Student s3 = new Student("岳云鹏",44); Student s4 = new Student("汪峰",44); Student s5 = new Student("那英",44); Collection c=new ArrayList(); c.add(s1); c.add(s2); c.add(s3); c.add(s4); c.add(s5); //Object[] toArray():把集合转成数组，然后遍历数组，其实就相当于遍历了集合。 Object[] arr=c.toArray(); for(int i=0;i<arr.length;i++){ Student s=(Student) arr[i]; System.out.println(s.getName()+" "+s.getAge()); } } }

编译运行后结果如下： 数组部分： 薛之谦 35 周杰伦 36 集合部分： 章子怡 45 郭德纲 55 岳云鹏 44 汪峰 44 那英 44 所以，总的来说，数组和集合的区别如下： 数组： 1.长度固定 2.可以存储基本类型，也可以存储引用类型 3.存储元素类型一致 集合： 1.长度可变 2.只可以存储引用类型 3.可以存储多种类型 为了满足不同的需求，Java提供了不同的集合类。而这些集合类由于数据结构不同，才可以满足不通的需求。数据结构指的就是存储元素的方式。 而无论这些集合的结构是什么样子的，都是要装水的，所以，他们应该有共性的内容。通过不断的向上提取，最终会形成一个集合的继承体系图。 java API 集合类图介绍 Collction体系结构图 Collection List ArrayList Vector LinkedList Set HashSet TreeSet 他们之间的关系，可以通过一个图来进行理解： 下面主要介绍集合的有关接口和类： Collection是集合的顶层结构，定义了集合的共性功能。可以存储对象，这些对象也被称为元素。 成员方法： A:添加功能 boolean add(Object obj):往集合中添加一个元素 boolean addAll(Collection c):往集合中添加多个元素 B:删除功能 void clear():清空所有元素 boolean remove(Object o):从集合中删除一个元素 boolean removeAll(Collection c):从集合中删除另一个集合的元素 C:判断功能 boolean contains(Object o):判断集合中是否包含指定的元素 boolean containsAll(Collection c):判断集合中是否包含另一个集合的元素 boolean isEmpty():判断集合是否为空。 D:交集功能 boolean retainAll(Collection c) E:长度功能 int size():返回集合中元素的个数 在这里，我写了一段简单的代码来介绍这些功能：

package com.stu.collection; import java.util.ArrayList; import java.util.Collection; /* * 成员方法：(看到E我们先把它理解为Object即可) * A:添加功能 * boolean add(Object obj):往集合中添加一个元素 * boolean addAll(Collection c):往集合中添加多个元素 * B:删除功能 * void clear():清空所有元素 * boolean remove(Object o):从集合中删除一个元素 * boolean removeAll(Collection c):从集合中删除另 一个集合的元素 * C:判断功能 * boolean contains(Object o):判断集合中是否包含指定的元素 * boolean containsAll(Collection c):判断集合中是否包含另一个集合的元素 * boolean isEmpty():判断集合是否为空。 D:交集功能 * boolean retainAll(Collection c) * * E:长度功能 * int size():返回集合中元素的个数 */ public class CollectionStu01 { public static void main(String[] args) { //创建集合 Collection c=new ArrayList(); c.add("hello"); c.add("world"); c.add("java"); // boolean add(Object obj):往集合中添加一个元素 // boolean flag1 = c.add("fg"); // System.out.println(flag1); //boolean addAll(Collection c):往集合中添加多个元素 Collection c2=new ArrayList(); c2.add("nihao"); c2.add("shijie"); boolean flag2=c.addAll(c2); //System.out.println(flag2); // void clear():清空所有元素 // c.clear(); // // boolean remove(Object o):从集合中删除一个元素 // boolean flag3 = c.remove("hello"); // System.out.println(flag3); // boolean removeAll(Collection c):从集合中删除另一个集合的元素 // boolean flag4=c.removeAll(c2); // System.out.println(flag4); //boolean contains(Object o):判断集合中是否包含指定的元素 // boolean flag5 = c.contains("java"); // System.out.println(flag5); //boolean containsAll(Collection c):判断集合中是否包含另一个集合的元素 // boolean flag6=c.containsAll(c2); // System.out.println(flag6); //boolean isEmpty():判断集合是否为空。 // boolean empty = c.isEmpty(); // System.out.println(empty); //boolean retainAll(Collection c)交集功能 // boolean flag7=c.retainAll(c2); // System.out.println(flag7); //int size():返回集合中元素的个数 int size = c.size(); System.out.println(size); Object[] arr = c.toArray(); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } }

有关上述一些方法的运行结果在这里就不多做介绍了。 迭代器： 为了可以更好地理解迭代器，在这里，分别创建String对象，Student对象添加集合遍历练习。 Iterator iterator() Object next():返回迭代的下一个元素,并移动指向的位置 boolean hasNext():判断是否有元素 可以用一张图来介绍一下迭代器： NoSuchElementException:没有这样的元素异常。 原因是：你已经获取到元素的末尾了，你还要继续获取元素，已经没有了，所以就报错了。 解决方案：你不要再拿了。我哪知道什么就不拿了啊?怎么办呢?就应该在拿之前判断一下是否有元素。 迭代器遍历集合： 迭代器是依赖于集合而存在的。所以，要想得到迭代器对象，必须先有集合对象。 迭代步骤： A:通过集合对象获取到迭代器对象 B:通过迭代器对象的hasNext()方法判断是否有元素 C:通过迭代器对象的next()方法获取元素 需求：创建狗对象（带参数），存储到集合，用迭代器进行遍历并打印对象的属性数据

//狗 package com.stu03; // 需求：创建狗对象（带参数），存储到集合，用迭代器进行遍历并打印对象的属性数据 public class Dog { private String name; private int age; public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } public Dog(String name, int age) { super(); this.name = name; this.age = age; } public Dog() { super(); // TODO Auto-generated constructor stub } } //dogtest package com.stu03; import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; public class DogTest { public static void main(String[] args) { //创建狗对象 Dog d1 = new Dog("旺旺",2); Dog d2 = new Dog("小花",3); //创建集合对象 Collection c=new ArrayList(); c.add(d1); c.add(d2); //创建迭代器对象 Iterator it = c.iterator(); while(it.hasNext()){ //强制类型转换 Dog d=(Dog) it.next(); System.out.println(d.getName()+" "+d.getAge()); } } }

编译运行后如下： 旺旺 2 小花 3 List List集合的元素有序(存储和取出顺序一致),元素可重复 List的特有功能： A:添加功能 void add(int index,Object obj):在指定的位置添加元素 B:删除功能 Object remove(int index):通过指定的索引删除元素，并把删除的元素返回 C:获取功能 get(int index) 返回列表中指定位置的元素。 D:替换功能 Object set(int index,Object obj) 用一部分代码简单介绍一下这些功能

package com.stu.list; import java.util.ArrayList; import java.util.List; /* * List的特有功能： A:添加功能 void add(int index,Object obj):在指定的位置添加元素 B:删除功能 Object remove(int index):通过指定的索引删除元素，并把删除的元素返回 C:获取功能 get(int index) 返回列表中指定位置的元素。 D:替换功能 Object set(int index,Object obj) */ public class ListStu01 { public static void main(String[] args) { List list=new ArrayList(); list.add("hello"); list.add("world"); list.add("java"); //void add(int index,Object obj):在指定的位置添加元素 list.add(1, "nihao"); //Object remove(int index):通过指定的索引删除元素，并把删除的元素返回 Object remove = list.remove(1); System.out.println(remove); //get(int index) 返回列表中指定位置的元素。 Object object = list.get(2); System.out.println(object); //Object set(int index,Object obj)替换功能 list.set(2, "C++"); System.out.println("---------------"); for(Object obj:list){ System.out.println(obj.toString()); } } }

相关运行结果不多做说明 有关List的其他功能 案例： A:List存储字符串并遍历 B:List存储自定义对象并遍历 List的倒序与洗牌 List中元素顺序可以被洗牌Collections.shuffle(list) List中元素顺序可以被倒序Collections.reverse(list) Collections.sort(list)对List元素排序

package com.stu.list; import java.util.ArrayList; import java.util.Collections; import java.util.Iterator; import java.util.List; /* * 案例： A:List存储字符串并遍历(迭代器,普通for) B:List存储自定义对象并遍历(迭代器,普通for) List的倒序与洗牌 List中元素顺序可以被洗牌Collections.shuffle(list) List中元素顺序可以被倒序Collections.reverse(list) Collections.sort(list)对List元素排序 */ public class ListStu02 { public static void main(String[] args) { List list=new ArrayList(); list.add("hello"); list.add("world"); list.add("java"); //A:List存储字符串并遍历(迭代器,普通for) for(int i=0;i<list.size();i++){ System.out.println(list.get(i)); } //List中元素顺序可以被洗牌Collections.shuffle(list) //Collections.shuffle(list); //List中元素顺序可以被倒序Collections.reverse(list) // Collections.reverse(list); //Collections.sort(list)对List元素排序（字母数字分别进行测试） Collections.sort(list); Iterator it = list.iterator(); while(it.hasNext()){ System.out.println(it.next()); } } }

编译运行结果如下： hello world java hello java world 在这里做一个需求来理解List 需求：用List集合存储3个汽车对象，然后遍历。 在遍历过程中，介绍三种遍历方式，具体代码实现如下：

//Car package com.stu05; public class Car { private String brand; private int price; private String color; public Car(String brand, int price, String color) { super(); this.brand = brand; this.price = price; this.color = color; } public Car() { super(); // TODO Auto-generated constructor stub } public String getBrand() { return brand; } public void setBrand(String brand) { this.brand = brand; } public int getPrice() { return price; } public void setPrice(int price) { this.price = price; } public String getColor() { return color; } public void setColor(String color) { this.color = color; } } //测试 package com.stu05; import java.util.ArrayList; import java.util.Iterator; import java.util.List; //用List集合存储3个汽车对象，然后遍历。 public class CarTest { public static void main(String[] args) { Car c1 = new Car("大众",120000,"黑色"); Car c2 = new Car("奔驰",200000,"白色"); Car c3 = new Car("劳斯莱斯",3000000,"红色"); List list=new ArrayList(); list.add(c1); list.add(c2); list.add(c3); //迭代器 Iterator it = list.iterator(); while(it.hasNext()){ Car c=(Car) it.next(); System.out.println(c.getBrand()+" "+c.getColor()+" "+c.getPrice()); } System.out.println("（---------------------------------）"); //for循环 for(int i=0;i<list.size();i++){ Car c=(Car) list.get(i); System.out.println(c.getBrand()+" "+c.getColor()+" "+c.getPrice()); } System.out.println("（---------------------------------）"); //强制for循环 for(Object obj:list){ Car c=(Car)obj; System.out.println(c.getBrand()+" "+c.getColor()+" "+c.getPrice()); } } }

编译运行后结果如下： 大众 黑色 120000 奔驰 白色 200000 劳斯莱斯 红色 3000000 （—————————————————） 大众 黑色 120000 奔驰 白色 200000 劳斯莱斯 红色 3000000 （————————————————–） 大众 黑色 120000 奔驰 白色 200000 劳斯莱斯 红色 3000000 ArrayList 其实就是List接口的一个实现类，简单的用一个案例介绍一下 案例：存储字符串并遍历

package com.stu.arraylist; import java.util.ArrayList; import java.util.Iterator; import java.util.List; //存储字符串并遍历 public class ArrayListStu01 { public static void main(String[] args) { //创建集合对象 List list=new ArrayList(); list.add("hello"); list.add("world"); list.add("java"); //遍历字符串 /*1、普通for循环 *2、加强for循环 *3、迭代器 */ //1、普通for循环 //Object[] arr = list.toArray(); for(int i=0;i<list.size();i++){ System.out.println(list.get(i)); } System.out.println("（--------------------）"); //2、加强for循环 for(Object obj:list){ System.out.println(obj); } System.out.println("（---------------------------）"); //3、迭代器 Iterator it = list.iterator(); while(it.hasNext()){ System.out.println(it.next()); } } }

编译运行结果如下： hello world java （——————–） hello world java （—————————） hello world java LinkedList 同ArrayList相同，也是List接口的一个实现类 LinkedList特有功能: public void addFirst(E e) public void addLast(E e) public E getFirst() public E getLast() public E removeFirst() public E removeLast() ArrayList与LinkedList的相同点与不同点 相同点：有顺序的，元素可以重复 (1)ArrayList特点: 底层数据结构是数组,查询快,增删慢 线程不安全,效率高 (2)LinkedList特点: 底层数据结构是链表,查询慢,增删快 线程不安全,效率高 在最后，还需要掌握一点，在前面代码编译过程中，会遇到或多或少的警告，那么要取消这些警告，就要引入泛型的概念。 泛型 是一种把明确数据类型的工作推迟到创建对象或者调用方法的时候才去明确类型的特殊类型 格式： <数据类型> 默认情况下，是Object类型。 这里数据类型只能是引用类型。如果你看到写基本类型也行，其实这里使用了自动装箱。 好处： A:把运行时期问题提前到了编译时期 B:避免了强制类型转换 C:优化程序设计，解决了黄色警告线问题 在哪里用? 一般来说就是在集合中用的多。 看API,如果类或者接口或者方法出现了<>说明这里就有泛型。 用一个简单的例子来理解：

package com.stu.generic; public class GenericTest01 { public static void main(String[] args) { GenericStu01<String> gs = new GenericStu01<String>(); gs.show("hello"); } }

编译运行结果如下： hello