Java集合01_ArrayList、LinkedList 和 Vector

野性酷女 2022-12-03 02:23 226阅读 0赞

## Java集合 ##

**数组的优点：**

元素连续分配空间，根据下标访问元素（随机访问效率高）

**数组的局限性：**

长度固定不变，不能自动扩容

删除和插入操作效率较低，需要移动大量的元素

元素的类型只能是一种

元素连续分配空间，在 heap 内存中必须找到连续的内存空间来存储数组（对内存要求较高）

--------------------

**为了解决数组的局限性，引入了容器类的概念**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JMVV8xMTE_size_16_color_FFFFFF_t_70_pic_left]

**ArrayList**

**ArrayList 底层数据结构是数组，查询快，增删慢，线程不安全，效率高**

add()、size()、isEmpty()
    contains()、indexOf()、lastIndexOf()
    iterator()、remove()、set()
    get()、toArray()、clear()

public static void main(String[] args) { 
    
    	ArrayList<String> arrayList = new ArrayList<String>();
    	arrayList.add("hello");
    	arrayList.add("world");
    	arrayList.add("BLU");
    	arrayList.add("everyday");
    	arrayList.add(3,"happy");
    	
    	System.out.println(arrayList);
    	System.out.println("size:"+arrayList.size());
    	System.out.println("是否为空集合："+arrayList.isEmpty());
    	System.out.println("位置为3的元素："+arrayList.get(3));
    	System.out.println("是否包含元素'BLU'："+arrayList.contains("BLU"));
    	System.out.println("元素'BLU'所在位置："+arrayList.indexOf("BLU"));
    	System.out.println("元素'BLU'最后出现的位置："+arrayList.lastIndexOf("BLU"));
    	
    	Iterator it = arrayList.iterator();
    	while(it.hasNext()) { 
    		String s1 = (String) it.next();
    		System.out.println("迭代器迭代："+s1);
    	}
    	
    	arrayList.remove("BLU");
    	arrayList.remove(1);
    	arrayList.set(0, "HELLO!");
    	
    	for(int i=0; i<arrayList.size();i++) { 
    		String s2 = (String) arrayList.get(i);
    		System.out.println("for循环输出："+s2);
    	}
    
    	for(String s : arrayList) { 
    		System.out.println("增强for循环输出："+s);
    	}
    	
    	Object[] array = arrayList.toArray();
    	
    	for (int i = 0; i < array.length; i++) { 
    		System.out.println("数组："+array[i]);
    	}
    	
    	arrayList.clear();
    	System.out.println("size:"+arrayList.size());
    	
    }

[hello, world, BLU, happy, everyday]
    size:5
    是否为空集合：false
    位置为3的元素：happy
    是否包含元素'BLU'：true
    元素'BLU'所在位置：2
    元素'BLU'最后出现的位置：2
    迭代器迭代：hello
    迭代器迭代：world
    迭代器迭代：BLU
    迭代器迭代：happy
    迭代器迭代：everyday
    for循环输出：HELLO!
    for循环输出：happy
    for循环输出：everyday
    增强for循环输出：HELLO!
    增强for循环输出：happy
    增强for循环输出：everyday
    数组：HELLO!
    数组：happy
    数组：everyday
    size:0

containsAll()	本集合是否包含指定集合中的所有元素
    addAll()		将指定集合中的所有元素添加到本集合
    removeAll()		移除本集合中与指定集合的交集部分
    retainAll()		移除本集合中指定集合的补集部分，保留交集

public static void main(String[] args) { 
    
    	ArrayList<String> arrayList1 = new ArrayList<String>();
    	arrayList1.add("aaa");
    	arrayList1.add("bbb");
    	arrayList1.add("ccc");
    	ArrayList<String> arrayList2 = new ArrayList<String>();
    	arrayList2.add("ccc");
    	arrayList2.add("ddd");
    	arrayList2.add("eee");
    	
    	System.out.println("list1:"+arrayList1);
    	System.out.println("list2:"+arrayList2);
    	System.out.println("list1是否包含list2中的所有元素："+arrayList1.containsAll(arrayList2));
    	arrayList1.addAll(arrayList2);
    	System.out.println("list1:"+arrayList1);
    	arrayList1.removeAll(arrayList2);
    	System.out.println("list1:"+arrayList1);
    	arrayList1.add("ccc");
    	arrayList1.retainAll(arrayList2);
    	System.out.println("list1:"+arrayList1);
    
    }

list1:[aaa, bbb, ccc]
    list2:[ccc, ddd, eee]
    list1是否包含list2中的所有元素：false
    list1:[aaa, bbb, ccc, ccc, ddd, eee]
    list1:[aaa, bbb]
    list1:[ccc]

**数组长度是有限的，而 ArrayList 可以存放任意数量的对象，长度不受限制，它是怎么实现的呢？**

采用数组扩容的方式！

ArrayList 的默认初始容量大小为 **DEFAULT\_CAPACITY** = 10

当 add() 时发现**所需容量 minCapacity** 超出了初始容量大小，将进入 grow(int minCapacity) 方法进行扩容，创建一个容量为 1.5倍旧容量 的新 ArrayList，将原数组数据拷贝至新数组

int newCapacity = oldCapacity + (oldCapacity >> 1);

elementData = Arrays.copyOf(elementData, newCapacity);

--------------------

**注：常见的写法会把引用声明为接口List类型**

写法一：
    ArrayList<String> h=new ArrayList<String>();
    
    写法二（推荐）：
    List<String> mylist = new ArrayList<String>();

写法一用当前类作为引用类型，那么可以访问到ArrayList这个类中的所有公用方法。
    写法二用接口List作为引用类型，那么通过list引用可以访问到接口中定义的方法。但是就无法调用的List接口以外的方法了。
    
    设计模式中有：“代码尽量依赖于抽象，不依赖于具体”。
    第一种形式就是依赖具体，第二种形式就是依赖于抽象。
    代码依赖于抽象的好处是，代码可以方便替换。
    
    例如，代码List list = new ArrayList();下面通过list来操作集合。
    代码编写后发现集合使用的不准确，应该使用LinkedList，那么只要修改一行代码List list = new LinkedList();就可以了
    因为List接口保证了调用的都是接口中的方法，而ArrayList与LinkedList都实现了List接口。
    而如果当时用ArrayList list = new ArrayList()这种形式的话，那么list访问到的就可能是ArrayList里独有的方法而非List接口中的方法。
    这样替换成LinkedList的时候就有可能需要修改很多的代码。

--------------------

**LinkedList**

**LinkedList：底层数据结构是链表，查询慢，增删快，线程不安全，效率高**

**LinkedList 和 ArrayList 一样实现了 list 接口，也同样拥有 list 接口的相关方法**

此外 LinkedList 还实现了 **Deque** 接口，因此还拥有以下特有方法：

addFirst()、addLast()
    offerFirst()、offerLast()
    getFirst()、getLast()
    removeFirst()、removeLast()
    
    addFirst() 和 offerFirst() 的区别是前者返回void,后者固定返回true

public static void main(String[] args) { 
    	LinkedList<String> list = new LinkedList<String>();
    	list.add("hello");
    	list.add("world");
    	list.addFirst("Hi");
    	list.addLast("BLU!");
    	System.out.println(list);
    	
    	Iterator<String> it = list.iterator();
    	while(it.hasNext()) { 
    		System.out.println(it.next());
    	}
    	
    	System.out.println("头部元素："+list.getFirst());
    	System.out.println("尾部元素："+list.getLast());
    	list.removeFirst();
    	list.removeLast();
    	list.offerFirst("first");
    	list.offerLast("last");
    	System.out.println(list);
    }

[Hi, hello, world, BLU!]
    Hi
    hello
    world
    BLU!
    头部元素：Hi
    尾部元素：BLU!
    [first, hello, world, last]

--------------------

**ArrayList 和 LinkedList 的区别：**

**ArrayList 底层是数组，LinkedList 是基于链表的数据结构**

**ArrayList 查询快，而 LinkedList 查询需要移动指针，效率低**

**对于新增和删除操作，LinkedList 占优势，而 ArrayList 新增和删除需要移动数据，效率低**

--------------------

**Vector**

**Vector：底层数据结构是数组，查询快，增删慢，线程安全，效率低**

public static void main(String[] args) { 
    
    	Vector<String> list = new Vector<String>();
    	list.addElement("hello");
    	list.addElement("world");
    	list.addElement("BLU");
    	
    	for(int i=0;i<list.size();i++) { 
    		System.out.println(list.elementAt(i));
    	}
    	
    	Enumeration<String> elements = list.elements();
    	
    	while(elements.hasMoreElements()) { 
    		System.out.println(elements.nextElement());
    	}
    }

hello
    world
    BLU
    hello
    world
    BLU

--------------------

**案例1：去除集合中字符串的重复值**

思路1：创建一个新集合，遍历原集合，元素依次存入新集合，存入之前判断在新集合中是否已经存在
    思路2：依次比较集合中的元素和集合后面的所有元素，发现有相同的值就把后面的元素删掉

**思路1（注意这个 contains() 方法，它的底层是 equals() 方法，如果判断的是普通对象，则调用的是父类 Object 中的 equals 方法，而 Object 中的 equals 方法判断的是地址值是否相同，所以该普通对象需要重写 equals 方法）：**

public static void main(String[] args) { 
    	ArrayList<String> list = new ArrayList<>();
    	list.add("a");
    	list.add("b");
    	list.add("c");
    	list.add("d");
    	list.add("c");
    	list.add("c");
    	list.add("e");
    	list.add("b");
    	ArrayList<String> newlist = new ArrayList<>();
    	
    	for(int i=0;i<list.size();i++) { 
    		if(!newlist.contains(list.get(i))) { 
    			newlist.add(list.get(i));
    		}
    	}
    		
    	System.out.println(newlist);
    }

[a, b, c, d, e]

**思路2（注意这个y减减，因为删除了一个元素后，后面的元素索引都会更改）：**

public static void main(String[] args) { 
    	ArrayList<String> list = new ArrayList<>();
    	list.add("a");
    	list.add("b");
    	list.add("c");
    	list.add("d");
    	list.add("c");
    	list.add("c");
    	list.add("e");
    	list.add("b");
    	
    	for(int i=0;i<list.size()-1;i++) { 
    		for(int j=i+1;j<list.size();j++) { 
    			if(list.get(i).equals(list.get(j))) { 
    				list.remove(j);
    				j--;
    			}
    		}
    	}
    	
    	System.out.println(list);	
    		
    }

[a, b, c, d, e]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JMVV8xMTE_size_16_color_FFFFFF_t_70_pic_left]: /images/20221123/09ce818983df44a9a4c296faf8b81319.png