[学习交流] 石家庄校区就业班day03-List,Set

【石家庄校区】就业班day03-List,Set数据结构

不同的数据结构代表了不同的存储方式

不同的数据结构中, 会有不同的存入, 取出, 查找的方式和效率, 数据的存放方式 ,也不同.

栈的特点:

先进后出 (FILO, First In Last Out) // 第一个进最后一个出来

入口和出口在同一侧

入栈(压栈): 将元素存入栈出栈(弹栈): 从栈中取出元素

栈的适用场景:

栈内存 (main方法先进栈调用, main方法中的其他方法都调用完毕后, main才能出栈) 反转内容 (车尾变车头, 进去再出来就反转了)

队列的特点:

先进先出 (FIFO, First In First Out) //第一个进去的,第一个出来入口和出口在两端

数组的特点:

查询快: 通过 (第一个元素地址值 + 索引) 可以快速计算出该索引元素的地址值增删慢: 增加一个元素, 要创建长度+1的新数组, 然后将原数组元素复制到新数组, 然后存入新元素;

// 添加元素
      +-----+-----+-----+-----+-----+----------+
      |  "a" |  "b"  |  "c"  |  "d"  |  "e"  |
      +-----+-----+-----+-----+-----+----------+
         如果要添加元素"f"

      +-----+-----+-----+-----+-----+-----+-----------+
      |  "a"  |  "b"  |  "c"  |  "d"  |  "e"  |  "f"  |
      +-----+-----+-----+-----+-----+-----+-----------+
      创建一个新数组, 将原数组元素复制进去, 然后存入新元素
      链表的特点:

查询慢: 要找到其中某个节点, 只能从第一个节点一个一个向后寻找增删快: 只需要修改保存的下一个节点的地址值, 就可以快速完成增删

单向链表:

每个节点存储数据和下一个节点的地址值

链表 = 0x11

      0x11             0x44             0x88
+-----+----+-----+-----+    +-----+-----+    +-----+-----+
      |  "a"  |  0x44| --> | "b" | 0x88  | --> | "c" | null |
+-----+----+-----+-----+    +-----+-----+    +-----+-----+
   数据  下一个    数据  下一个    数据  下一个双向链表:

每个节点存储数据, 上一个节点地址值和下一个节点地址值

0x11                   0x44                   0x88
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
null|"a"|0x44| <--> |0x11|"b"|0x88| <--> |0x44 | "c" | null
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
上一个  数据  下一个上一个  数据  下一个  上一个  数据  下一个

// 单向链表的节点
class Node<T> {
T data;    // 存储的数据
Node next; // 下一个节点的地址值
}

// 双向链表的节点
class Node<T> {
T data;    // 存储的数据
Node before;  // 上一个节点的地址值
Node after; // 下一个节点的地址值
}红黑树:

是一种平衡二叉查找树平衡: 左子节点和右子节点数量相等 //左==右二叉: 每个节点最多有2个子节点 //分支不能超过两个查找: 节点存储的元素是按照大小顺序存储的 //在二叉树基础上 ,元素大小的顺序是一样的

特点:

元素存储过程中就完成了大小排序查询比链表快, 增删比数组快 (数组和链表的折中) 特点趋近于平衡树查询的非常快,查询叶子节点最大次数和最小次数不能超过2倍

代码中树节点的实现

// 树的节点
class Entry<T> {
T data;          // 存储的数据
Entry left;    // 左子节点的地址值
Entry right;    // 右子节点的地址值
Entry parent;    // 父节点的地址值
}
约束:
节点可以是红色的或者黑色的
根节点是黑色的
叶子节点(空节点)是黑色的
每个红色的节点的子节点都是黑色的

day03 【List、Set、数据结构、Collections】List集合List介绍和常用方法

List集合体系的特点:

元素存取有序 (存入和取出元素的顺序一致) 3 2 1 3 2 1
元素可以重复 3 2 2 1
有索引

java.util.List<E>接口:
// 常用特有成员方法 (都是按照索引来操作的)
public?void?add(int?index,?E?element): 将指定的元素, 添加到该集合中的指定位置上
public?E?get(int?index): 返回集合中指定位置的元素
public?E?remove(int?index): 移除列表中指定位置的元素, 返回的是被移除的元素
public?E?set(int?index,?E?element): 用指定元素替换集合中指定位置的元素, 返回值的更新前的元素
java.util.LinkedList<E>类: 链表结构, 查询慢, 增删快
// 特有成员方法(主要操作开头和末尾元素)
void?addFirst(E?e): 将指定元素插入此列表的开头
void?addLast(E?e): 将指定元素添加到此列表的结尾
E?getFirst(): 返回此列表的第一个元素
E?getLast(): 返回此列表的最后一个元素
E?removeFirst(): 移除并返回此列表的第一个元素
E?removeLast(): 移除并返回此列表的最后一个元素
E?pop(): (其实就是removeFirst())从此列表所表示的堆栈处弹出一个元素栈stack
void?push(E?e): (其实就是addFirst())将元素推入此列表所表示的堆栈

java.util.Set<E>接口:
// 成员方法
boolean add(E e): 添加元素. 元素不重复则添加成功, 返回true; 否则返回false

java.util.Collections类: 操作集合的工具类
// 静态方法
static?<T>?boolean?addAll(Collection<T>?c,?T...?elements):往集合中添加一些元素
static?void?shuffle(List<?>?list) :打乱集合顺序
static?<T>?void?sort(List<T>?list) :将集合中元素按照默认规则排序
static?<T>?void?sort(List<T>?list，Comparator<??super?T>?c):将集合中元素按照指定规则排序
public static void main(String[] args) {
      List<String> list=new ArrayList<>();
      list.add("a");
      list.add("b");
      list.add("c");
      list.add("d");
      list.add("e");
      list.add(3,"itheima");                //增删改查
      //在cd之间添加字符串
      list.remove(1);
      //删除索引元素
      list.set(4,"A");
      //替换索引位置元素
      for (String s : list) {
         System.out.println(s);
      }//遍历集合
      }ArrayList的特点:

查询快增删慢线程不安全, 效率高

LinkedList集合的特点和特有方法LinkedList底层的数据结构:

链表

LinkedList的特点:

查询慢增删快线程不安全, 效率高

LinkedList<String> s = new LinkedList<>();
      s.add("a");
      s.add("b");
      s.add("c");
      s.add("d");
      System.out.println(s);  //abcd
      s.addFirst("A"); //添加第一个元素
      System.out.println(s); //Aabcd
      s.addLast("E");       //添加最后一个元素
      System.out.println(s);  //AabcdE
      String s1 = s.getFirst();  //获取第一个元素
      System.out.println(s1); //A
      String s2 = s.getLast(); //获取最后一个元素
      System.out.println(s2);  //E
      String s3 = s.removeFirst(); //删除第一个元素
      System.out.println(s3); //A
      String s4 = s.removeLast();    //删除最后一个元素
      System.out.println(s4); //E
      String s5 = s.pop();          //删除第一个栈弹出的元素
      System.out.println(s5);  //a
      s.push("a");          //将添加的元素到此列所表示的栈中
      System.out.println(s);//abcdSet集合体系HashSet集合Set集合体系特点:

1.不允许存储重复的元素

2.没有索引,没有带索引的方法,也不能使用普通for循环遍历 (增强for循环,迭代器)

HashSet特点:
1. 元素不可重复
2. 没有索引,没有带索引的方法,也不能使用普通for循环遍历 (增强for循环,迭代器)
3. 元素存取无序 (存入和取出顺序有可能不一致)
4. 底层采用哈希表结构. (查询快)
哈希表 = 数组 + 链表或红黑树

java.util.HashSet类: // 常用方法 boolean add(E e): 添加元素, 根据元素的 hashCode() 和 equals() 方法判断是否重复. 重复则不添加并返回false, 不重复则添加并返回true

public static void main(String[] args) {
      HashSet<Integer> in = new HashSet<>();
      in.add(5);
      in.add(5);             //有序无序存入和取出的顺序
      in.add(3);             //排序从小到大从大到小
      in.add(4);             //无索引

      in.add(3);
      in.add(2);
      in.add(1);
      for (Integer integer : in) {
         System.out.println(integer);
      }
}HashSet原理: 哈希值

哈希值: 一个十进制数值, 一般是通过将该对象的内部地址转换成一个整数来实现的

public native int hashCode(); 可以调用系统本地代码(C/C++)计算出一个对象地址的哈希值 hashCode()方法的作用方法内部的算法用于将对象计算为一个哈希值, 便于根据哈希值比较对象是否"相等" 哈希值主要是为了提高对象存储在哈希表中的效率

注意:
1. 如果我们不满意Object中的哈希值计算方法, 可以重写hashCode()方法.
      但在Java代码中不能直接重写带有 native 的方法, 重写时应该将 native 去掉
                  @Override
                  public int hashCode() {}
2. hashCode() 方法有可能将"不同的对象"计算出"相同的哈希值", 这称为"哈希冲突", 在出现冲突后, 一般再通过 equals() 方法来继续判断对象是否"相等"

"重地" "通话"

HashSet原理: 哈希表结构

哈希表: JDK 8以前 : 哈希表 = 数组 + 链表 JDK 8及之后 : 哈希表 = 数组 + 链表或红黑树数组中存储的每个元素, 是哈希值相同的一组节点的链表或红黑树

HashSet原理: 存储元素不重复的原理HashSet集合保证添加元素不重复的原理:

调用 add(E e) 添加元素时, 先调用 hashCode() 获取哈希值, 和当前HashSet集合中的元素比较 如果哈希值不同, 则认为元素不重复, 添加, 并返回true 如果哈希值相同, 则有可能是哈希冲突, 所以继续调用元素的 equals() 方法和所有哈希值相同的元素比较 如果 equals() 比较所有元素都没有相同的, 则认为元素不重复, 添加, 并返回true 如果 equals() 比较出有相同的元素, 则认为元素重复, 不添加, 并返回false

public static void main(String[] args) {
      HashSet<String> s = new HashSet<>();
      String s1 = new String("abc");
      String s2 = new String("abc");
      s.add(s1);
      s.add("abc");
      s.add(s2);
      s.add("重地");
      s.add("通话");
      System.out.println(s);
}HashSet存储自定义元素的去重

自定义JavaBean对象实现在HashSet中去重: JavaBean默认继承Object类中的 hashCode() 和 equals() 方法, 都是根据对象地址值判断是否重复的要根据属性值判断是否重复, 应该在JavaBean类中重写 hashCode() 和 equals() 方法, 使其按照属性值比较

LinkedHashSet集合LinkedHashSet特点:
1. 元素存取有序 (存入和取出顺序一致)
2. 元素不可重复
3. 没有索引

LinkedHashSet底层数据结构: 哈希表 + 链表 (也就是: 数组 + 链表或红黑树 + 链表) 其中, 哈希表用于存储数据, 额外的链表用于记录元素添加时的先后顺序, 以便在获取元素时保持顺序一致

总结: 什么时候用List, 什么时候用Set?                   //ArrayList 可重复增删少遍历方便
   要存储的元素可以重复的, 用List集合:                //LinkList    可重复增删多遍历不方便
            增删少, 用ArrayList                   //HashSet    不可重复存取可不一致
            增删多, 用LinkedList                //LinkedHashSet 不可重复存取需一致
要存储的数据要求不重复, 或者相对一个集合去重, 用Set集合:
            不要求存取顺序一致, 用HashSet
            要求存取顺序一致, 用LinkedHashSet

HashSet<String> set=new HashSet<>();
      set.add("www");                      //遍历只有哈希表
      set.add("4399");
      set.add("com");       //无序,且不可重复
      set.add("com");
      System.out.println(set);
      LinkedHashSet<String> link=new LinkedHashSet<>();
      link.add("WWW");                      //遍历有哈希表+链表数组+链表+链表
      link.add("WWW");
      link.add("4399");    //有序,且可重复
      link.add("COM");
      System.out.println(link);可变参数

可变参数: JDK 5 出现. 指同一个类型参数个数可变的参数可变参数的本质就是一个"数组" 格式: 用在方法的参数中修饰符返回值类型方法名(int... 变量名) { // 可以直接将变量名当作数组名使用 } 方法名();

public static void main(String[] args) {
      add(1,2,4,3,4,6,100,9,4,5);
      System.out.println(add(1,2,4,3,4,6,100,9,4,5));
}

private static int  add(int ...arr) {
      int sum=0;
      for (int i : arr) {
         sum+=i;
      }
      return sum;
                                                            //只能有一个可变参数
}
//注意事项:

//1. 可变参数可以传递的参数个数, 可以是 0个, 1个, 多个
//2. 一个方法的参数列表中, 只能有一个可变参数
//3. 如果方法的参数有多个, 可变参数必须写在参数列表的最后
Collections集合工具类Collections集合工具类: addAll(), shuffle()

java.util.Collections类: 操作集合的工具类 // 静态方法 static <T> boolean addAll(Collection<? super T> c, T... elements):往集合中添加一些元素 static void shuffle(List<?> list): 打乱集合顺序 static <T> void sort(List<T> list): 将集合中元素按照默认规则排序 static <T> void sort(List<T> list，Comparator<? super T> c):将集合中元素按照指定规则排序

Collections集合工具类: sort(List<T> list)

sort(List<T> list): 默认按照"升序"将元素排序数字, 字母, 都可以按照升序排序自定义JavaBean对象默认不能排序, 因为不知道如何比较哪个对象大, 哪个对象小自定义JavaBean对象要想排序, 需要实现 Comparable<E> 接口, 重写 int compareTo(E e) 方法规则: this-参数: 升序(从小到大) 参数-this: 降序(从大到小)

public static void main(String[] args) {
      ArrayList<Person> list = new ArrayList<>();
      list.add(new Person("张三",15));
      list.add(new Person("李四",17));
      list.add(new Person("王五",20));
      Collections.sort(list);
      System.out.println(list);
}

--------------------------------------------------------------
public class Person implements Comparable<Person>
.....
   //重写排序的规则
@Override
public int compareTo(Person o) {
   //  return this.getAge()-o.getAge();//升序排序年龄  /  //o.是传进来的参数
      return o.getAge()-this.getAge();//降续排序年龄    //this.是本身的参数
   // return 0;//认为元素都是相同的       //本can的年龄减去传入的年龄年龄小的往前排
}Collections集合工具类: sort(List<T> list，Comparator<? super T> )

Comparable接口和Comparator接口区别 Comparable: 让JavaBean自身具有可比较性 (自己和其他人比) Comparator: 定义一个比较器类, 用比较器对象比 (让第三个人来帮两个人比较)

Comparator使用方式: 定义类作为比较器, 实现Comparator<E>接口, 重写 int compare(E o1, E o2) 方法, 泛型为要比较的元素的类型在Collections.sort(List<T> list，Comparator<? super T> c)方法中传入自定义比较器对象规则: o1-o2: 升序(从小到大) o2-o1: 降序(从大到小)

//数字排序
public static void main(String[] args) {
   //创建Arraylist集合
      ArrayList<Integer> list = new ArrayList<>();
   //添加元素至集合
      Collections.addAll(list,1,2,3);
      System.out.println(list);
   //第三者比较覆盖重写
      Collections.sort(list, new Comparator<Integer>() {
         @Override
         public int compare(Integer o1, Integer o2) {
            //如果o2-o1  则输出降序
            //如果o1-o2  则输出升序
            return o2-o1;
         }
      });
      System.out.println(list);

}
//按年龄比较方法
public class Person {

private String name;
private int age;

public Person() {
}

public Person(String name, int age) {
      this.name = name;
      this.age = 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;
}

@Override
public String toString() {
      return "Person{" +
            "name='" + name + '\'' +
            ", age=" + age +
            '}';
}
}

public class Test {
public static void main(String[] args) {
      // 创建3个Person对象
      Person p1 = new Person("李四", 14);
      Person p2 = new Person("张三", 13);
      Person p3 = new Person("王五", 15);

      // 创建集合添加元素
      ArrayList<Person> list = new ArrayList<>();
      list.add(p1);
      list.add(p2);
      list.add(p3);

      System.out.println("排序前:" + list);
      // 对集合排序
      Collections.sort(list, new Comparator<Person>() {
         @Override
         public int compare(Person o1, Person o2) {
            /*
            规则:
                  o1-o2: 升序
                  o2-o1: 降序
               */
            // 按照年龄升序
//             return o1.getAge() - o2.getAge();

            // 按照年龄降序
            return o2.getAge() - o1.getAge();
         }
      });
      System.out.println("排序后:" + list);
}
}

帐号		自动登录	找回密码
密码			加入黑马

[学习交流] 石家庄校区 就业班day03-List,Set

0 个回复

[学习交流] 石家庄校区就业班day03-List,Set