目录

一、常见的数据结构

1、栈

 2、队列

3、数组

4、链表

5、红黑树

二、List集合

1、List接口介绍

2、List接口中常用方法

三、List的子类

1、ArrayList集合

2、LinkedList集合

四、Set接口

1、HashSet集合介绍

2、HashSet集合存储数据的结构（哈希表）

3、哈希值 & Set集合存储元素不重复的原理

4、HashSet存储自定义类型元素

5、LinkedHashSet

一、常见的数据结构

1、栈

栈：stack,又称堆栈，它是运算受限的线性表，其限制是仅允许在标的一端进行插入和删除操作，不允许在其他任何位置进行添加、查找、删除等操作。

简单的说：采用该结构的集合，对元素的存取有如下的特点

先进后出（即，存进去的元素，要在后它后面的元素依次取出后，才能取出该元素）。

压栈：就是存元素。即，把元素存储到栈的顶端位置，栈中已有元素依次向栈底方向移动一个位置。

弹栈：就是取元素。即，把栈的顶端位置元素取出，栈中已有元素依次向栈顶方向移动一个位置。

 2、队列

队列：queue,简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。

先进先出（即，存进去的元素，要在后它前面的元素依次取出后，才能取出该元素）。

3、数组

数组：Array,是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。就像是一排出租屋，有100个房间，从001到100每个房间都有固定编号，通过编号就可以快速找到租房子的人。

 （2）增删元素慢

指定索引位置增加元素：需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根据索引，复制到新数组对应索引的位置。如下图

4、链表

（2）查找元素慢：想查找某个元素，需要通过连接的节点，依次向后查找指定元素

（3）增删元素快：

增加元素：只需要修改连接下个元素的地址即可。

 删除元素：只需要修改连接下个元素的地址即可。

5、红黑树

二叉树：binary tree ,是每个结点不超过2的有序树（tree）。

红黑树的约束:

1. 节点可以是红色的或者黑色的

2. 根节点是黑色的

3. 叶子节点(特指空节点)是黑色的

4. 每个红色节点的子节点都是黑色的

5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

红黑树的特点:

速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍

二、List集合

1、List接口介绍

List接口特点：

1. 它是一个元素存取有序的集合。例如，存元素的顺序是11、22、33。那么集合中，元素的存储就是按照11、22、33的顺序完成的）。

2. 它是一个带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）。

3. 集合中可以有重复的元素，通过元素的equals方法，来比较是否为重复的元素。

tips:我们在基础班的时候已经学习过List接口的子类java.util.ArrayList类，该类中的方法都是来自List中定义。

2、List接口中常用方法

public void add(int index, E element) : 将指定的元素，添加到该集合中的指定位置上。

public E get(int index) :返回集合中指定位置的元素。

public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。

public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素。

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;/*java.util.List接口 extends Collection接口List接口的特点:1.有序的集合,存储元素和取出元素的顺序是一致的(存储123 取出123)2.有索引,包含了一些带索引的方法3.允许存储重复的元素List接口中带索引的方法(特有)- public void add(int index, E element): 将指定的元素，添加到该集合中的指定位置上。- public E get(int index):返回集合中指定位置的元素。- public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素。- public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回值的更新前的元素。注意:操作索引的时候,一定要防止索引越界异常IndexOutOfBoundsException:索引越界异常,集合会报ArrayIndexOutOfBoundsException:数组索引越界异常StringIndexOutOfBoundsException:字符串索引越界异常*/
public class Demo01List {public static void main(String[] args) {//创建一个List集合对象,多态List<String> list = new ArrayList<>();//使用add方法往集合中添加元素list.add("a");list.add("b");list.add("c");list.add("d");list.add("a");//打印集合System.out.println(list);//[a, b, c, d, a]  不是地址重写了toString//public void add(int index, E element): 将指定的元素，添加到该集合中的指定位置上。//在c和d之间添加一个itheimalist.add(3,"Specter");//[a, b, c, Specter, d, a]System.out.println(list);//public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素。//移除元素String removeE = list.remove(2);System.out.println("被移除的元素:"+removeE);//被移除的元素:cSystem.out.println(list);//[a, b, Specter, d, a]//public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回值的更新前的元素。//把最后一个a,替换为AString setE = list.set(4, "A");System.out.println("被替换的元素:"+setE);//被替换的元素:aSystem.out.println(list);//[a, b, Specter, d, A]//List集合遍历有3种方式//使用普通的for循环for(int i=0; i<list.size(); i++){//public E get(int index):返回集合中指定位置的元素。String s = list.get(i);System.out.println(s);}System.out.println("-----------------");//使用迭代器Iterator<String> it = list.iterator();while(it.hasNext()){String s = it.next();System.out.println(s);}System.out.println("-----------------");//使用增强forfor (String s : list) {System.out.println(s);}String r = list.get(5);//IndexOutOfBoundsException: Index 5 out-of-bounds for length 5System.out.println(r);}
}

三、List的子类

1、ArrayList集合

2、LinkedList集合

java.util.LinkedList 集合数据存储的结构是链表结构。方便元素添加、删除的集合。

 双向链表：

public void addFirst(E e) :将指定元素插入此列表的开头。

public void addLast(E e) :将指定元素添加到此列表的结尾。

public E getFirst() :返回此列表的第一个元素。

public E getLast() :返回此列表的最后一个元素。

public E removeFirst() :移除并返回此列表的第一个元素。

public E removeLast() :移除并返回此列表的最后一个元素。

public E pop() :从此列表所表示的堆栈处弹出一个元素。

public void push(E e) :将元素推入此列表所表示的堆栈。

public boolean isEmpty() ：如果列表不包含元素，则返回true。

import java.util.LinkedList;/*java.util.LinkedList集合 implements List接口LinkedList集合的特点:1.底层是一个链表结构:查询慢,增删快2.里边包含了大量操作首尾元素的方法注意:使用LinkedList集合特有的方法,不能使用多态- public void addFirst(E e):将指定元素插入此列表的开头。- public void addLast(E e):将指定元素添加到此列表的结尾。- public void push(E e):将元素推入此列表所表示的堆栈。- public E getFirst():返回此列表的第一个元素。- public E getLast():返回此列表的最后一个元素。- public E removeFirst():移除并返回此列表的第一个元素。- public E removeLast():移除并返回此列表的最后一个元素。- public E pop():从此列表所表示的堆栈处弹出一个元素。- public boolean isEmpty()：如果列表不包含元素，则返回true。*/
public class Demo02LinkedList {public static void main(String[] args) {show03();}/*- public E removeFirst():移除并返回此列表的第一个元素。- public E removeLast():移除并返回此列表的最后一个元素。- public E pop():从此列表所表示的堆栈处弹出一个元素。此方法相当于 removeFirst*/private static void show03() {//创建LinkedList集合对象LinkedList<String> linked = new LinkedList<>();//使用add方法往集合中添加元素linked.add("a");linked.add("b");linked.add("c");System.out.println(linked);//[a, b, c]//String first = linked.removeFirst();String first = linked.pop();System.out.println("被移除的第一个元素:"+first);String last = linked.removeLast();System.out.println("被移除的最后一个元素:"+last);System.out.println(linked);//[b]}/*- public E getFirst():返回此列表的第一个元素。- public E getLast():返回此列表的最后一个元素。*/private static void show02() {//创建LinkedList集合对象LinkedList<String> linked = new LinkedList<>();//使用add方法往集合中添加元素linked.add("a");linked.add("b");linked.add("c");//linked.clear();//清空集合中的元素 在获取集合中的元素会抛出NoSuchElementException//public boolean isEmpty()：如果列表不包含元素，则返回true。if(!linked.isEmpty()){String first = linked.getFirst();System.out.println(first);//aString last = linked.getLast();System.out.println(last);//c}}/*- public void addFirst(E e):将指定元素插入此列表的开头。- public void addLast(E e):将指定元素添加到此列表的结尾。- public void push(E e):将元素推入此列表所表示的堆栈。此方法等效于 addFirst(E)。*/private static void show01() {//创建LinkedList集合对象LinkedList<String> linked = new LinkedList<>();//使用add方法往集合中添加元素linked.add("a");linked.add("b");linked.add("c");System.out.println(linked);//[a, b, c]//public void addFirst(E e):将指定元素插入此列表的开头。//linked.addFirst("www");//两者等效linked.push("www");System.out.println(linked);//[www, a, b, c]//public void addLast(E e):将指定元素添加到此列表的结尾。此方法等效于 add()linked.addLast("com");System.out.println(linked);//[www, a, b, c, com]}
}

四、Set接口

tips:Set集合取出元素的方式可以采用：迭代器、增强for。

1、HashSet集合介绍

HashSet 是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。保证元素唯一性的方式依赖于： hashCode 与 equals 方法。

我们先来使用一下Set集合存储，看下现象，再进行原理的讲解:

package ListAndSet.demo02.Set;import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;/*java.util.Set接口 extends Collection接口Set接口的特点:1.不允许存储重复的元素2.没有索引,没有带索引的方法,也不能使用普通的for循环遍历java.util.HashSet集合 implements Set接口HashSet特点:1.不允许存储重复的元素2.没有索引,没有带索引的方法,也不能使用普通的for循环遍历3.是一个无序的集合,存储元素和取出元素的顺序有可能不一致4.底层是一个哈希表结构(查询的速度非常的快)*/
public class Demo01Set {public static void main(String[] args) {Set<Integer> set = new HashSet<>();//使用add方法往集合中添加元素set.add(1);set.add(3);set.add(2);set.add(1);//使用迭代器遍历set集合Iterator<Integer> it = set.iterator();while (it.hasNext()){Integer n = it.next();System.out.println(n);//1,2,3}//使用增强for遍历set集合System.out.println("-----------------");for (Integer i : set) {System.out.println(i);}}
}

2、HashSet集合存储数据的结构（哈希表）

3、哈希值 & Set集合存储元素不重复的原理

/*哈希值:是一个十进制的整数,由系统随机给出(就是对象的地址值,是一个逻辑地址,是模拟出来得到地址,不是数据实际存储的物理地址)在Object类有一个方法,可以获取对象的哈希值int hashCode() 返回该对象的哈希码值。hashCode方法的源码:public native int hashCode();native:代表该方法调用的是本地操作系统的方法*/
public class Demo01HashCode {public static void main(String[] args) {//Person类继承了Object类,所以可以使用Object类的hashCode方法Person p1 = new Person();int h1 = p1.hashCode();System.out.println(h1);//1967205423  | 1Person p2 = new Person();int h2 = p2.hashCode();System.out.println(h2);//42121758   |  1/*toString方法的源码:return getClass().getName() + "@" + Integer.toHexString(hashCode());*/System.out.println(p1);//ListAndSet.demo03.hashCode.Person@1System.out.println(p2);//ListAndSet.demo03.hashCode.Person@1System.out.println(p1==p2);//false ( 物理地址不相等 )/*String类的哈希值String类重写Obejct类的hashCode方法*/String s1 = new String("abc");String s2 = new String("abc");System.out.println(s1.hashCode());//96354System.out.println(s2.hashCode());//96354System.out.println("重地".hashCode());//37597889System.out.println("通话".hashCode());//37709653}
}

public class Person extends  Object{//重写hashCode方法@Overridepublic int hashCode() {return  1;}
}

4、HashSet存储自定义类型元素

import java.util.HashSet;/*HashSet存储自定义类型元素set集合报错元素唯一:存储的元素(String,Integer,...Student,Person...),必须重写hashCode方法和equals方法要求:同名同年龄的人,视为同一个人,只能存储一次*/
public class Demo03HashSetSavePerson {public static void main(String[] args) {//创建HashSet集合存储PersonHashSet<Person> set = new HashSet<>();Person p1 = new Person("小美女",18);Person p2 = new Person("小美女",18);Person p3 = new Person("小美女",19);System.out.println(p1.hashCode());//1967205423System.out.println(p2.hashCode());//42121758System.out.println(p1==p2);//falseSystem.out.println(p1.equals(p2));//falseset.add(p1);set.add(p2);set.add(p3);System.out.println(set);}}

import java.util.Objects;public class Person {private String name;private int age;public Person() {}public Person(String name, int age) {this.name = name;this.age = age;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Person person = (Person) o;return age == person.age &&Objects.equals(name, person.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}@Overridepublic String toString() {return "Person{" +"name='" + name + '\'' +", 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;}
}

5、LinkedHashSet

package ListAndSet.demo02.Set;import java.util.HashSet;
import java.util.LinkedHashSet;/*java.util.LinkedHashSet集合 extends HashSet集合LinkedHashSet集合特点:底层是一个哈希表(数组+链表/红黑树)+链表:多了一条链表(记录元素的存储顺序),保证元素有序*/
public class Demo04LinkedHashSet {public static void main(String[] args) {HashSet<String> set = new HashSet<>();set.add("www");set.add("abc");set.add("abc");set.add("Specter");System.out.println(set);//[abc, www, Specter] 无序,不允许重复LinkedHashSet<String> linked = new LinkedHashSet<>();linked.add("www");linked.add("abc");linked.add("abc");linked.add("Specter");System.out.println(linked);//[www, abc, Specter] 有序,不允许重复}
}