Java 链表、二叉树、集合的相关总结（附代码）

vlambda
2021-07-22

Java 链表、二叉树、集合的相关总结（附代码）

1、链表节点：

class Node{

Object data;

Node next;

}

二叉树：

class Node{

Object data;

Node left;

Node right;

}

2、Collecotion接口，里面包含了十五个方法。

它有两个子接口：List、Set

List允许有重复元素，Set不允许有重复元素，这是两个子接口的区别。

3、List集合：

3.1、ArrayList：使用的是数组结构，对于增加删除慢，查找快。

//无参构造方法创建一个长度为0的数组，要第一次传进去数据的时候才会改为10的长度。每次动态扩容的时候都是扩大为原来的1.5倍。

ArrayList<类型> data = new ArrayList<>();

data.add(100); //add返回的一一定是true。

有三种构造方法，其他两个见API。

一些方法的实现：

//无参构造
ArrayList<String> data = new ArrayList<>();
//有参构造 拥有五个长度的列表,当元素超出长度时，会自动扩容。（我们不需进行操作）
ArrayList<String> dataNew = new ArrayList<>(5);
//添加三个元素,都是添加到列表的尾部，依次有序添加。
data.add("123");
data.add("ming");
data.add("2021");
//在第二个位置添加一个元素（从下标0开始的）
data.add(1,"new");
dataNew.add("21");
dataNew.add("32");
//可以添加重复的元素
dataNew.add("21");
//指定dataNew列表的第三个元素，data列表全部元素加入到指定位置，然后顺序往后。
dataNew.addAll(2,data);
//返回此列表中的元素总数
System.out.println(data.size());    // 4
System.out.println(dataNew.size()); // 7

将列表data的所有元素加入到dataNew（Collection<? extends E> c）列表的尾后。

dataNew.addAll(data);

返回列表的所有元素 clone()方法：

System.out.println(dataNew.clone());

上面一行代码返回的是上面所有加入dataNew列表的所有元素（类型均为String类型）。元素结果如下：[21, 32, 123, new, ming, 2021, 21, 123, new, ming, 2021]。此结果也证明了上面的添加元素的准确。

删除所有元素：data.clear();

查询元素是否在列表中，contains（Object o）方法返回true或false：

ArrayList<String> data = new ArrayList<>();
data.add("123");
data.add("ming");
data.add("2021");
System.out.println(data.contains("123"));

返回true
当不为字符串或者是其他结果时都将是false。

第二种方式，以下标元素进行查找get（int index）方法：

ArrayList<String> data = new ArrayList<>();
data.add("123");
data.add("ming");
data.add("2021");
data.add(1,"new");
System.out.println(data.get(3));//下标索引

结果为：2021

第三种方式，indexOf（Object o）方法，如果列表中存在则返回该元素下标索引，若不存在则返回-1.

//无参构造
ArrayList<String> data = new ArrayList<>();
//添加三个元素,都是添加到列表的尾部，依次有序添加。
data.add("123");
data.add("ming");
data.add("2021");
//在第二个位置添加一个元素，从下标0开始的
data.add(1,"new");
System.out.println(data.indexOf(3));
System.out.println(data.indexOf("new"));

结果：
-1
1

查找一个元素最后出现的索引，如果没有该元素则返回-1：int lastIndexOf(Object o)

判断列表是否为空则可以使用isEmpty（）方法，如果列表不为空则返回false，如果为空则返回true：

//无参构造
ArrayList<String> data = new ArrayList<>();
//添加三个元素,都是添加到列表的尾部，依次有序添加。
data.add("123");
data.add("ming");
data.add("2021");
//在第二个位置添加一个元素，从下标0开始的
data.add(1,"new");
System.out.println(data.isEmpty());

删除一个指定的元素使用remove方法：E remove(int index)或boolean remove(Obejct o)可以以下标索引删除元素，也可以元素值删除。两者都可用。

ArrayList<String> data = new ArrayList<>();
//添加三个元素,都是添加到列表的尾部，依次有序添加。
data.add("123");
data.add("ming");
data.add("2021");
//在第二个位置添加一个元素，从下标0开始的
data.add(1,"new");
data.remove("new");
data.remove(1);
System.out.println(data.clone());

结果为：[123, 2021]。

删除一个指定的列表所有元素，使用 boolean removeAll(Collection<?> c)：

//有参构造 拥有五个长度的列表,当元素超出长度时，会自动扩容。（我们不需进行操作）
ArrayList<String> dataNew = new ArrayList<>(5);
//无参构造
ArrayList<String> data = new ArrayList<>();
//添加三个元素,都是添加到列表的尾部，依次有序添加。
data.add("123");
data.add("ming");
data.add("2021");
//在第二个位置添加一个元素，从下标0开始的
data.add(1,"new");
dataNew.add("21");
dataNew.add("32");
//可以添加重复的元素
dataNew.add("21");
System.out.println(data.clone());
System.out.println(dataNew.clone());
data.addAll(1,dataNew);
System.out.println(data.clone());
data.removeAll(dataNew);
System.out.println(data.clone());

删除一个列表中指定范围的元素使用void removeRange(int fromIndex, int toIndex)

retainAll（Collection<?> c）保留列表中指定的列表元素，其他元素均被删除：

//有参构造 拥有五个长度的列表,当元素超出长度时，会自动扩容。（我们不需进行操作）
ArrayList<String> dataNew = new ArrayList<>(5);
//无参构造
ArrayList<String> data = new ArrayList<>();
//添加三个元素,都是添加到列表的尾部，依次有序添加。
data.add("123");
data.add("ming");
data.add("2021");
//在第二个位置添加一个元素，从下标0开始的
data.add(1,"new");
dataNew.add("21");
dataNew.add("32");
//可以添加重复的元素
dataNew.add("21");
data.addAll(2,dataNew);
data.retainAll(dataNew);
System.out.println(data.clone());

结果：[21, 32, 21]

按索引更改元素：set（int index，Object o）：

//无参构造
ArrayList<String> data = new ArrayList<>();
//添加三个元素,都是添加到列表的尾部，依次有序添加。
data.add("123");
data.add("ming");
data.add("2021");
//在第二个位置添加一个元素，从下标0开始的
data.add(1,"new");
data.set(2,"happy");
System.out.println(data.clone());

int size（）返回列表的元素总数：

data.set();

subList（int indexFrom,int indexTo）查看indexFrom（包括）到indexTo（不包括）之间的元素：

ArrayList<String> data = new ArrayList<>();
//添加三个元素,都是添加到列表的尾部，依次有序添加。
data.add("123");
data.add("ming");
data.add("2021");
//在第二个位置添加一个元素，从下标0开始的
data.add(1,"new");
data.set(2,"happy");
System.out.println(data.subList(1,2));

结果：[new]

可以使用trimTosize()调整列表实例的容量为当前的大小，最小化了ArrayList实例的存储。

3.2、Vector

构造方法：默认构造方法Vector()，其内部数据数组的大小为0，增量标准为0，当需要增加的时候，是大小翻一番。有参构造方法Vector(int initialCapacity, int capacityIncrement),第一个参数是数组大小，第二个设置具体的增量。另外两种构造方法见API。

Vector实现的方法与ArrayList类似。这里参考上一篇博文。

3.3、LinkedList 使用的是双向链表结构，对于增加删除快，查找慢。

LinkedList <Integer> data = new LinkedList <>();

压栈：（存储数据）

data.push(100);

data.push(200);

弹栈：（取出数据）

Integer i = data.pop();

System.out.println(i);

结果为：200

在有关栈的使用，使用上面这种方法进行存取数据取出数据。

迭代器：

1、Iterator 可以迭代List和Set

iterator.hasNext() 判断下一个数据是否存在。如果存在返回true，否则false。

iterator.next() 返回下一个数据的值。这两个方法一般就用于循环取出数据。

删除的方法，需要在执行iterator.next();之后才能进行remove删除。完整格式： Integer i = iterator.next(); iterator.remove(); ==>这样才删除了此数据 i 。

2、ListIterator 只可以迭代List

ListIterator<Integer> iterator = data.ListIterator<>();

可以add增加元素，iterator .add(100);set改变元素，iterator .set(200);改变的是iterator指向的元素。同样可以iterator.previous()向前移动。前提是此时指向的存在数据。才能往前移。

forEach : 增强For循环，最早出现在C#中。

用于迭代数组或集合

forEach语法：

for(数据类型变量名：集合或数组){}

4、Set集合：（不包含重复元素的集合，最多一个null元素，没有get()方法）

Set有一些子类是无序的存储方式。

4.1、HashSet：散列存放，不能保证存储顺序的，是一种无序的存储方式（哈希表在学习HashMap集合石讲解）

4.2、TreeSet: 是一种有序的存储方式，自然顺序。

在实现排序的时候我们例如内部类，在排序的时候我们需要自己去布置如何排序，即是要在内部类实现一个Comparable的接口，这个接口里面只有一个方法，就是compareTo方法，此方法就是我们需要实现的方法，方体体我们自定义编写排序规则。

5、Map集合（与Collection集合一个级别）

Map集合存储的是一个个的键值对数据。Map集合的键(key)不可重复

Interface Map<K,V> (泛型，是两个因为一个Key一个映射的值)

常用的方法：

增：

V put(K key,V value) 将指定的值与映射中的指定键进行关联。返回的是原来的value值，如果原来value为null，则返回的是null。如果不为空那，则返回原来的value。

删：

第一种方式直接删除key键 V remove(Object key) 则删除的就是key的映射，返回的是value值；第二种方式：default boolean remove(Object key, Object value) 只有当key与value对应起来的时候删除了。

改：

default V replace(K key, V value) 或 default boolean replace(K key, V oldValue, V newValue)

查：

Set<K> keySet() 返回此映射中包含的键的Set视图。

V get(Object key) 查看key映射的value值。

int size() 返回键值对映射的数量。

最后 void clear() 删除所有映射。

其他非常用的方法可以需要时候再查看API。

6、HashMap：

哈希表又称为散列表。

哈希表（又称哈希桶）：对象数组+链表：

哈希桶中的数据量大于8时，从链表转为红黑二叉树；当哈希桶中的数据量减少到6时，从红黑二叉树转换为链表。

初始桶数量 16、散列因子0.75.

存在哪儿是由key键决定的。

哈希表的遍历方式：

Hash<String,String> data = new HashMap<>();data.put("key1","abc");data.put("key2","ABC");Set<String> set = data.keyget();for(String key:set){ System.out.println(key+"->"+data.get(key));}Collection<String> values = data.values();for(String value:values){System.out.println(value);}

结果为：key1->abc key2->ABC abc ABC

HashMap\Hashtable\ConcurrentHashMap\TreeMap\LinkedHashMap对于上面的代码都能支持。

HashMap、TreeMap 存储无序。LinkedHashMap存储有序，实际上里面存在一个链表。

HashMap\Hashtable\ConcurrentHashMap的区别：

多线程，线程安全与否。上面三个都属于容器。HashMap 线程不安全，效率高。Hashtable 线程安全，效率低。ConcurrentHashMap 采用分段锁机制，保证线程安全，效率又比较高

vlambda博客
学习文章列表