vlambda博客
学习文章列表

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 采用分段锁机制,保证线程安全,效率又比较高