Java集合整理（Arraylist、Vector、Linklist）_arraylsit和linklist和vector

1、类集概述

类集设置的目的(常用类库的重点)：
对象数组有那些问题?普通的对象数组的最大问题在于数组中的元素个数是固定的，不能动态的扩充大小，所以最早的时候可以通过链表实现一个动态对象数组。但是这样做毕竟太复杂了,所以在Java中为了方便用户操作各个数据结构，所以引入了类集的概念，有时候就可以把类集称为java对数据结构的实现。
在整个类集中的，这个概念是从JDK12 (Java2) 之后才正式引入的，最早也提供了很多的操作类，但是并没有完整的提出类集的完整概念。
类集中最大的几个操作接口: Collection、 Map、Iterator, 这三个接口为以后要使用的最重点的接口。 所有的类集操作的接口或类都在javautil包中。

Java类集结构图:.

• Collection：用来存储单值
• Map：用来存储双值
• Iterator：迭代器可以用最优的方式来存取数据

2、链表

数组的动态扩容很费内存。主要表现在数组存储中不利于删除数据，删除数据后数据不连续，操作前移费内存。但链表就解决了这个问题。
链表 [Linked List]：链表是由一组不必相连（不必相连：可以连续也可以不连续） 的内存结构（节点） ，按特定的顺序链接在一起的抽象数据类型。

补充：
抽象数据类型（Abstract Data Type [ADT]）：表示数学中抽象出来的一些操作的集合。
内存结构：内存中的结构，如： struct、特殊内存块…等等之类；

数组和链表的区别和优缺点：

数组是一种连续存储线性结构，元素类型相同，大小相等。
数组的优点： 存取速度快
数组的缺点：
事先必须知道数组的长度
插入删除元素很慢
空间通常是有限制的
需要大块连续的内存块
插入删除元素的效率很低

链表是离散存储线性结构 n 个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。

链表优点：空间没有限制 插入删除元素很快
链表缺点：存取速度很慢

删除指针：后一个指针向前移！

2、链表共分几类？
链表常用的有 3 类： 单链表、双向链表、循环链表。

单链表：只知道下一数据的下标
双链表：既知道上一个数据的下标，也知道下一个数据的下标
循环链表：首尾相连
链表的核心操作集有 3 种：插入、删除、查找(遍历）

单链表

//链表节点
class Node{
   
	Object data;
	Node next;
}

1
2
3
4
5
6
7

单链表 [Linked List]：由各个内存结构通过一个 Next 指针链接在一起组成，每一个内存结构都存在后继内存结构(链尾除外） ，内存结构由数据域和 Next 指针域组成。
单链表实现图示：

解析：
Data 数据 + Next 指针，组成一个单链表的内存结构 ；
第一个内存结构称为 链头，最后一个内存结构称为 链尾；
链尾的 Next 指针设置为 NULL [指向空]；
单链表的遍历方向单一（只能从链头一直遍历到链尾）
单链表操作集：

3、二叉树

二叉树是树的一种，每个节点最多可具有两个子树，即结点的度最大为 2（结点度：结点拥有的子树数）。

//二叉树节点
class Node{
   
	Object data;
	Node left;
	Node right;
}
1
2
3
4
5
6
7

先序遍历(根-左-右):1-2-4-8-9-5-10-3-6-7
中序遍历:(左-根-右):8-4-9-2-10-5-1-6-3-7
后序遍历(左-右-根):8-9-4-10-5-2-6-7-3-1

4、Collection接口（重点）

Collection 接口是在整个 Java 类集中保存单值的最大操作父接口， 里面每次操作的时候都只能保存一个对象的数据。
此接口定义在 java.util 包中。

本接口中一共定义了 15 个方法， 那么此接口的全部子类或子接口就将全部继承以上接口中的方法。
但是， 在开发中不会直接使用 Collection 接口。 而使用其操作的子接口： List、 Set。
之所以有这样的明文规定， 也是在 JDK 1.2 之后才有的。 一开始在 EJB 中的最早模型中全部都是使用 Collection 操作的， 所以很早之前开发代码都是以 Collection 为准， 但是后来为了更加清楚的区分， 集合中是否允许有重复元素所以， SUN在其开源项目 —— PetShop（宠物商店） 中就开始推广 List （允许重复）和 Set （不允许重复）的使用。

5、List接口（重点）

在整个集合中 List 是 Collection 的子接口， 里面的所有内容都是允许重复的。
List 子接口的定义：

public interface List<E> extends Collection<E>
1

此接口上依然使用了泛型技术。 此接口对于 Collection 接口来讲有如下的扩充方法：

在 List 接口中有以上 10 个方法是对已有的 Collection 接口进行的扩充。
所以， 证明， List 接口拥有比 Collection 接口更多的操作方法。
了解了 List 接口之后， 那么该如何使用该接口呢？ 需要找到此接口的实现类， 常用的实现类有如下几个：
· ArrayList（95%） 、 Vector（4%） 、 LinkedList（1%）

5.1、ArrayList（重点）

ArrayList 是 List 接口的子类， 此类的定义如下：

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable
1
2

此类继承了 AbstractList 类。 AbstractList 是 List 接口的子类。 AbstractList 是个抽象类， 适配器设计模式。

范例： 增加及取得元素
package org.listdemo.arraylistdemo;
import java.util.ArrayList;
import java.util.List;
public class ArrayListDemo01 {
   
	public static void main(String[] args) {
   
		List<String> all = new ArrayList<String>(); // 实例化List对象， 并指定泛型类型
		all.add("hello "); // 增加内容， 此方法从Collection接口继承而来
		all.add(0, "LAMP ");// 增加内容， 此方法是List接口单独定义的
		all.add("world"); // 增加内容， 此方法从Collection接口继承而来
		System.out.println(all); // 打印all对象调用toString()方法
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

ArrayList的构造方法

当用ArrayList() 创建一个长度为10的数组，当存储到11个数据时，会扩容1.5倍，知道扩容到足够位置，如果存储大量的数据，便会导致大量的内存空间被浪费，因此初次创建时需要创建大量的数据时，因使用ArrayList​(int initialCapacity)的一参构造方法，指定存储的数量。
ArrayList通过无参构造器构造的集合在开始时长度是多少？
为0.，然后当存入数据后，会比较发现存不下，在将容量扩容到10

package com.java.arrayListDemo;
import java.util.ArrayList;
public class Demo1 {
   
    public static void main(String[] args) {
   
        ArrayList<Integer> arr = new ArrayList();
        arr.add(100);
    }
}

1
2
3
4
5
6
7
8
9
10
11

进入add方法的中：

    public boolean add(E e) {
   
        modCount++;
        add(e, elementData, size);//add(要往集合中添加的内容，存数据的数组，数组的长度)
        return true;//只要调用add方法，一定返回True，必定为true
    }
1
2
3
4
5
6

再看下add算法

    private void add(E e, Object[] elementData, int s) {
   
        if (s == elementData.length)//目前存的数据跟数据长度一致，说明已经存满了 
            elementData = grow();//存满的话，调用扩容算法，扩容后将新的数组赋值给elementData 
        elementData[s] = e;//正常存
        size = s + 1;//存完size（数组长度）+1
    }
1
2
3
4
5
6
7

再看下add算法下的grow()算法

    private Object[] grow() {
   
        return grow(<
1
2