Java集合之List集合（上）https://developer.aliyun.com/article/1386301
代码证明：
public static void main(String[] args) throws Exception { List list = new ArrayList(); for (int i = 0; i < 100; i++) { System.out.print(i + "=="); list.add(i); elementDataLength(list); // 调用 elementDataLength 方法输出当前容量 } } /** * 定义一个名为 "elementDataLength" 的方法，该方法用于使用反射获取 ArrayList 中存储元素的底层数组的长度并输出 * */ public static void elementDataLength(List list) throws Exception { // 使用反射获取 ArrayList 对象的成员变量 elementData Field ed = list.getClass().getDeclaredField("elementData"); ed.setAccessible(true); // 设置允许访问私有变量 Object[] o = (Object[]) ed.get(list); // 获取 ArrayList 中存储元素的底层数组对象的引用 // 输出 ArrayList 的容量信息，即底层数组的长度 System.out.println("当前List集合容量为：" + o.length); } //输出的内容： 0==当前List集合容量为：10 1==当前List集合容量为：10 2==当前List集合容量为：10 3==当前List集合容量为：10 4==当前List集合容量为：10 5==当前List集合容量为：10 6==当前List集合容量为：10 7==当前List集合容量为：10 8==当前List集合容量为：10 9==当前List集合容量为：10 10==当前List集合容量为：15 11==当前List集合容量为：15 12==当前List集合容量为：15 13==当前List集合容量为：15 14==当前List集合容量为：15 15==当前List集合容量为：22 16==当前List集合容量为：22 17==当前List集合容量为：22 18==当前List集合容量为：22 19==当前List集合容量为：22 20==当前List集合容量为：22 21==当前List集合容量为：22 22==当前List集合容量为：33 23==当前List集合容量为：33 24==当前List集合容量为：33 25==当前List集合容量为：33 26==当前List集合容量为：33 27==当前List集合容量为：33 28==当前List集合容量为：33 29==当前List集合容量为：33 30==当前List集合容量为：33 31==当前List集合容量为：33 32==当前List集合容量为：33 33==当前List集合容量为：49 34==当前List集合容量为：49 35==当前List集合容量为：49 36==当前List集合容量为：49 37==当前List集合容量为：49 38==当前List集合容量为：49 39==当前List集合容量为：49 40==当前List集合容量为：49 41==当前List集合容量为：49 42==当前List集合容量为：49 43==当前List集合容量为：49 44==当前List集合容量为：49 45==当前List集合容量为：49 46==当前List集合容量为：49 47==当前List集合容量为：49 48==当前List集合容量为：49 49==当前List集合容量为：73 50==当前List集合容量为：73 51==当前List集合容量为：73 52==当前List集合容量为：73 53==当前List集合容量为：73 54==当前List集合容量为：73 55==当前List集合容量为：73 56==当前List集合容量为：73 57==当前List集合容量为：73 58==当前List集合容量为：73 59==当前List集合容量为：73 60==当前List集合容量为：73 61==当前List集合容量为：73 62==当前List集合容量为：73 63==当前List集合容量为：73 64==当前List集合容量为：73 65==当前List集合容量为：73 66==当前List集合容量为：73 67==当前List集合容量为：73 68==当前List集合容量为：73 69==当前List集合容量为：73 70==当前List集合容量为：73 71==当前List集合容量为：73 72==当前List集合容量为：73 73==当前List集合容量为：109 74==当前List集合容量为：109 75==当前List集合容量为：109 76==当前List集合容量为：109 77==当前List集合容量为：109 78==当前List集合容量为：109 79==当前List集合容量为：109 80==当前List集合容量为：109 81==当前List集合容量为：109 82==当前List集合容量为：109 83==当前List集合容量为：109 84==当前List集合容量为：109 85==当前List集合容量为：109 86==当前List集合容量为：109 87==当前List集合容量为：109 88==当前List集合容量为：109 89==当前List集合容量为：109 90==当前List集合容量为：109 91==当前List集合容量为：109 92==当前List集合容量为：109 93==当前List集合容量为：109 94==当前List集合容量为：109 95==当前List集合容量为：109 96==当前List集合容量为：109 97==当前List集合容量为：109 98==当前List集合容量为：109 99==当前List集合容量为：109
我们可以看到内部容量不足时，ArrayList会将原数组长度乘以1.5进行扩容。
注意，由于 ArrayList 底层使用的是数组，因此一旦创建了 ArrayList，它的大小就是固定的。而当元素添加到 ArrayList 中时，如果底层数组已满，则需要创建一个更大的数组，并将原有元素复制到新数组中，这会带来一定的性能损耗。
因此，在实际开发中，建议在创建 ArrayList 时设置一个合适的初始化容量，避免在运行时频繁进行扩容操作，同时也可避免浪费过多空间资源。
拿以上例子稍作修改，将ArrayList容量改为50：
public static void main(String[] args) throws Exception { List list = new ArrayList(50); for (int i = 0; i < 100; i++) { System.out.print(i + "=="); list.add(i); elementDataLength(list); // 调用 elementDataLength 方法输出当前容量 } } /** * 定义一个名为 "elementDataLength" 的方法，该方法用于使用反射获取 ArrayList 中存储元素的底层数组的长度并输出 * */ public static void elementDataLength(List list) throws Exception { // 使用反射获取 ArrayList 对象的成员变量 elementData Field ed = list.getClass().getDeclaredField("elementData"); ed.setAccessible(true); // 设置允许访问私有变量 Object[] o = (Object[]) ed.get(list); // 获取 ArrayList 中存储元素的底层数组对象的引用 // 输出 ArrayList 的容量信息，即底层数组的长度 System.out.println("当前List集合容量为：" + o.length); } //输出的内容： 0==当前List集合容量为：50 1==当前List集合容量为：50 2==当前List集合容量为：50 3==当前List集合容量为：50 4==当前List集合容量为：50 5==当前List集合容量为：50 6==当前List集合容量为：50 7==当前List集合容量为：50 8==当前List集合容量为：50 9==当前List集合容量为：50 10==当前List集合容量为：50 11==当前List集合容量为：50 12==当前List集合容量为：50 13==当前List集合容量为：50 14==当前List集合容量为：50 15==当前List集合容量为：50 16==当前List集合容量为：50 17==当前List集合容量为：50 18==当前List集合容量为：50 19==当前List集合容量为：50 20==当前List集合容量为：50 21==当前List集合容量为：50 22==当前List集合容量为：50 23==当前List集合容量为：50 24==当前List集合容量为：50 25==当前List集合容量为：50 26==当前List集合容量为：50 27==当前List集合容量为：50 28==当前List集合容量为：50 29==当前List集合容量为：50 30==当前List集合容量为：50 31==当前List集合容量为：50 32==当前List集合容量为：50 33==当前List集合容量为：50 34==当前List集合容量为：50 35==当前List集合容量为：50 36==当前List集合容量为：50 37==当前List集合容量为：50 38==当前List集合容量为：50 39==当前List集合容量为：50 40==当前List集合容量为：50 41==当前List集合容量为：50 42==当前List集合容量为：50 43==当前List集合容量为：50 44==当前List集合容量为：50 45==当前List集合容量为：50 46==当前List集合容量为：50 47==当前List集合容量为：50 48==当前List集合容量为：50 49==当前List集合容量为：50 50==当前List集合容量为：75 51==当前List集合容量为：75 52==当前List集合容量为：75 53==当前List集合容量为：75 54==当前List集合容量为：75 55==当前List集合容量为：75 56==当前List集合容量为：75 57==当前List集合容量为：75 58==当前List集合容量为：75 59==当前List集合容量为：75 60==当前List集合容量为：75 61==当前List集合容量为：75 62==当前List集合容量为：75 63==当前List集合容量为：75 64==当前List集合容量为：75 65==当前List集合容量为：75 66==当前List集合容量为：75 67==当前List集合容量为：75 68==当前List集合容量为：75 69==当前List集合容量为：75 70==当前List集合容量为：75 71==当前List集合容量为：75 72==当前List集合容量为：75 73==当前List集合容量为：75 74==当前List集合容量为：75 75==当前List集合容量为：112 76==当前List集合容量为：112 77==当前List集合容量为：112 78==当前List集合容量为：112 79==当前List集合容量为：112 80==当前List集合容量为：112 81==当前List集合容量为：112 82==当前List集合容量为：112 83==当前List集合容量为：112 84==当前List集合容量为：112 85==当前List集合容量为：112 86==当前List集合容量为：112 87==当前List集合容量为：112 88==当前List集合容量为：112 89==当前List集合容量为：112 90==当前List集合容量为：112 91==当前List集合容量为：112 92==当前List集合容量为：112 93==当前List集合容量为：112 94==当前List集合容量为：112 95==当前List集合容量为：112 96==当前List集合容量为：112 97==当前List集合容量为：112 98==当前List集合容量为：112 99==当前List集合容量为：112
我们可以看到这次只扩容了两次，从50-75、从75-112，这大大减少了性能损耗，所以在创建 ArrayList 时设置一个合适的初始化容量是非常重要的。
4.5 ArrayList去重
4.5.1字符串去重
使用contains方法
public static void main(String[] args) { List list = new ArrayList(); list.add("a"); list.add("b"); list.add("c"); System.out.println("目前集合容器中的元素："+list);//目前集合容器中的元素：[a, b, c] if (!list.contains("b")){//如果不包含“b” list.add("b");//才增加 } System.out.println("目前集合容器中的元素："+list);//目前集合容器中的元素：[a, b, c] } }
4.5.2对象去重
public static void main(String[] args) { List list = new ArrayList(); list.add(new Student("zs",16)); list.add(new Student("ls",17)); list.add(new Student("ww",18)); System.out.println("目前集合容器中的元素："+list); //目前集合容器中的元素：[com.xqx.demo.Student@33909752, com.xqx.demo.Student@55f96302, com.xqx.demo.Student@3d4eac69] if (!list.contains(new Student("ls",17))){//不包含才新增 list.add(new Student("ls",17)); } System.out.println("目前集合容器中的元素："+list); //目前集合容器中的元素：[com.xqx.demo.Student@33909752, com.xqx.demo.Student@55f96302, com.xqx.demo.Student@3d4eac69, com.xqx.demo.Student@42a57993] if (list.contains(new Student("ls",17))){//包含才移除 list.remove(new Student("ls",17)); } System.out.println("目前集合容器中的元素："+list); //目前集合容器中的元素：[com.xqx.demo.Student@33909752, com.xqx.demo.Student@55f96302, com.xqx.demo.Student@3d4eac69, com.xqx.demo.Student@42a57993] } } class Student{ private String name; private int age; public Student(String name, int age) { this.name = name; this.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; }
为什么 student(‘ls’,17) 并没有新增与移除？
由于在 Java 中，比较对象是否相等是基于对象的地址进行的，而不是基于对象的属性值进行的。而实例化后，会新开一个地址。所以即使两个student的属性值相等，但实例化后地址不同，那么这两个对象就也不是相等的。
解决方案
重写equals方法即可
public static void main(String[] args) { List list = new ArrayList(); list.add(new Student("zs",16)); list.add(new Student("ls",17)); list.add(new Student("ww",18)); System.out.println("目前集合容器中的元素："+list); //目前集合容器中的元素：[com.xqx.demo.Student@33909752, com.xqx.demo.Student@55f96302, com.xqx.demo.Student@3d4eac69] if (!list.contains(new Student("ls",17))){//不包含才新增 list.add(new Student("ls",17)); } System.out.println("目前集合容器中的元素："+list); //目前集合容器中的元素：[com.xqx.demo.Student@33909752, com.xqx.demo.Student@55f96302, com.xqx.demo.Student@3d4eac69] if (list.contains(new Student("ls",17))){//包含才移除 list.remove(new Student("ls",17)); } System.out.println("目前集合容器中的元素："+list); //目前集合容器中的元素：[com.xqx.demo.Student@33909752, com.xqx.demo.Student@3d4eac69] } } class Student{ private String name; private int age; public Student(String name, int age) { this.name = name; this.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; } @Override public boolean equals(Object o) { System.out.println("调用了equals方法。。。"); if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; return age == student.age && name.equals(student.name); }
在重写的equals方法中，我们定义了只有姓名和年龄都相同时，才认为两个学生相等。因此，当通过新建一个Student对象来判断是否存在于ArrayList中时，即使该对象的内存地址不同，只要该对象的姓名和年龄与列表中某个元素的姓名和年龄相等，就会被视为存在于ArrayList中，从而避免了重复添加元素。而在删除元素时，由于通过该对象的equals方法判断该对象是否在ArrayList中存在，因此也可以正常进行删除。
总结
Java中的引用类型在判断相等性时，是根据对象在内存中的地址进行比较的。如果不重写equals方法，那么，由于ArrayList中存储的是对象的引用，所以相当于比较的是每个对象在内存中的地址是否相同，只有两个对象的地址相同时才会被视为相等。而我们通常认为，只有两个对象的属性值相同时才能被视为相等。因此，我们需要根据对象的实际比较规则重写equals方法。
五、LinkedList
5.1 LinkedList概述
5.1.1概念
LinkedList也是Java中的一个常用的集合类，实现了List接口，底层使用的是双向链表数据结构。
与ArrayList不同，LinkedList在内部存储元素时，不是使用连续的内存空间，而是使用一个链表来存储元素。
5.1.2数据结构
LinkedList底层采用的是双向链表（doubly linked list） 数据结构。链表中的每个节点（结点）都由两个部分组成，一部分是存储数据元素的值域，另一部分是指向前一个节点和后一个节点的指针（引用）。对于双向链表来说，除了一个指向前一个节点的指针外，还有一个指向后一个节点的指针
5.2LinkedList的特点
5.2.1随机访问性能较差：
LinkedList的随机访问性能较差，因为在链表中要从头开始遍历链表，直到找到目标元素。所以如果在代码中需要频繁进行随机访问元素的操作，LinkedList可能不是一个最佳的选择。
5.2.2添加/删除操作快：
由于LinkedList底层使用双向链表，因此它的添加和删除操作非常快，因为只需要更改指针的指向即可，不需要像ArrayList一样重新分配数组空间，而且LinkedList还支持在指定位置插入和删除元素。
5.2.3需要额外空间：
链表中每个节点都需要额外存储到前一个和后一个节点的指针，因此比数组等其他数据结构需要更多的内存空间。
5.2.4适用于队列和双端队列：
LinkedList还可以支持队列和双端队列的功能，如在链表头部或尾部添加或删除元素，实现队列和双端队列的常见操作。
- 双端队列（Deque，即Double Ended Queue的缩写）是一种允许在队列的两端进行插入和删除操作的数据结构。双端队列可以从队列的头部和尾部添加和移除元素。
5.3常用方法
| 方法名 | 说明 |
| addFirst(E element) | 将元素添加到列表的开头 |
| getFirst()： | 返回列表的第一个元素。 |
| getLast()： | 返回列表的最后一个元素。 |
| removeFirst()： | 删除并返回列表的第一个元素。 |
| removeLast()： | 删除并返回列表的最后一个元素。 |
5.4堆栈和队列
5.4.1堆栈
堆栈（Stack）是一种具有后进先出特性的数据结构。在堆栈结构中，新的元素总是被添加到栈顶（也就是最新元素），而只有在栈顶的元素才可以被移除。
堆栈最典型的例子是计算器的运算操作，先输入的操作数最后被计算，而最后输入的操作数最先被计算。对于堆栈结构，我们可以在程序中使用push（添加）和pop（移除）方法来实现后进先出的存储和读取数据。
5.4.2队列
队列（Queue）是一种具有先进先出特性的数据结构。在队列结构中，新的元素总是从队列的末尾添加到队列中，然后从队列的开头进行访问或删除。
队列最典型的例子是排队。排队的人总是按先来后到的顺序排队，当前面的人离开队列之后，后面的人才能够进入。对于队列结构，我们可以使用offer()方法将新的元素添加到队尾，使用poll()方法从队列开头移除元素。
5.5常见面试题：用LinkedList完成一个堆栈容器
package com.xqx.demo; import java.util.LinkedList; public class demo3 { public static void main(String[] args) { //创建集合 LinkedList ll = new LinkedList(); //添加元素 ll.add("lisi"); ll.add("zs"); ll.add("ww"); //实例化堆栈 DuiZhan DuiZhan = new DuiZhan(ll); System.out.println(DuiZhan.pop()); System.out.println(DuiZhan.pop()); System.out.println(DuiZhan.pop()); } } class DuiZhan{ LinkedList ll = null; public DuiZhan(LinkedList ll){// 堆栈的构造函数，接受一个 LinkedList 对象作为参数，用于存储堆栈元素 this.ll = ll; } //压栈 public void add(String a){ ll.add(a); } //弹栈 public String pop(){ return (String) ll.removeLast(); 从链表末尾移除一个元素并返回其值 } }
考察核心：
- 考察LinkedList的api方法
- 考察堆栈/队列的数据结构特点
六、ArrayList和LinkedList的比较
- 由于ArrayList的数据结构为数组，所以查询修改快，新增删除慢；而LinkedList的数据结构为链表结构，所以查询修改慢，新增删除快
- ArrayList是基于数组实现的动态数组，在内存中有连续的空间，可以通过下标访问元素，由于数组需要提前分配一定大小的空间，因此当元素数量增多之后，可能会导致数组空间不足需要重新分配数组，这种情况下可能会出现内存空间浪费；相比之下，LinkedList是基于链表实现的，每个元素都有一个引用指向下一个元素，不需要提前分配空间，因此能够更加灵活地插入和删除元素。然而，链表在内存中是不连续的，每个元素的引用占用额外的内存空间。由于链表中每个元素都需要有一个指向下一个元素的引用，因此在存储同样数量的元素时，LinkedList通常会占用比ArrayList更大的内存空间。
好啦，今天的分享就到此为止！希望你看完本篇文章有所收获，祝你变得更强！！!
