Java集合之List集合_javalist集合

一、 List概述

1.1概念

List是一种常用的集合类型，它可以存储任意类型的对象，也可以结合泛型来存储具体的类型对象，本质上就是一个容器。

1.2体系

List中主要有ArrayList、LinkedList两个实现类

1.3 通用方法

ArrayList和LinkedList通用方法

这里以ArrayList举例
代码测试：

public static void main(String[] args) {
		// TODO Auto-generated method stub
		// 创建集合
		List list = new ArrayList<>();

		// 添加元素
		list.add("hello");
		list.add("world");
		list.add("java");

		// public boolean remove(Object o)：删除指定的元素，返回删除是否成功
		 System.out.println(list.remove("world"));//true
		 System.out.println(list.remove("javaee"));//false

		// public E remove(int index)：删除指定索引处的元素，返回被删除的元素
		 System.out.println(list.remove(1));//world

		// IndexOutOfBoundsException
		 System.out.println(list.remove(3));

		// public E set(int index,E element)：修改指定索引处的元素，返回被修改的元素
		 System.out.println(list.set(1,"javaee"));//world

		// IndexOutOfBoundsException
		 System.out.println(list.set(3,"javaee"));

		// public E get(int index)：返回指定索引处的元素
		 System.out.println(list.get(0));//hello
		 System.out.println(list.get(1));//world
		 System.out.println(list.get(2));//java
		// IndexOutOfBoundsException
		 System.out.println(list.get(3));

		// public int size()：返回集合中的元素的个数
		 System.out.println(list.size());//3
		
		// 输出集合
		 System.out.println("list:" + list);//list:[hello, world, java]

		// boolean contains(Object o) 如果此列表包含指定的元素，则返回 true
		 System.out.println(list.contains("world"));//true
		 
		// boolean addAll(int index, Collection c) 
		//将指定集合中的所有元素插入到此列表中，从指定的位置开始
		List list2 = new ArrayList<>();
		//addall前list2
		System.out.println(list2);// []
		System.out.println(list2.addAll(0, list));// true
		//addall后list2
		System.out.println(list2);// [hello, world, java]
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

二、List的特点

（1）有序性：List中的元素是按照添加顺序进行存放的。因为有序，所以有下标，下标从0开始

（2）可重复性： List中可以存储重复的元素

三、遍历方式

3.1 foreach

       List list = new ArrayList<>();

        //添加元素
        list.add("hello");
        list.add("world");
        list.add("java");
        for (Object object : list) {
			System.out.println(object);
		}
		
1
2
3
4
5
6
7
8
9
10

3.2 for循环

根据下标遍历

       //创建集合
       List list = new ArrayList<>();

        //添加元素
        list.add("hello");
        list.add("world");
        list.add("java");
       for (int i = 0; i < list.size(); i++) {
		System.out.println(list.get(i));
	}

1
2
3
4
5
6
7
8
9
10
11

3.3迭代器

        //创建集合
       List list = new ArrayList<>();

        //添加元素
        list.add("hello");
        list.add("world");
        list.add("java");
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
        	System.out.println(iterator.next());
		}

1
2
3
4
5
6
7
8
9
10
11
12

四、ArrayList

4.1ArrayList概述

4.1.1概念

ArrayList是Java中的一个类，实现了List接口，底层使用数组来存储元素。与数组相比，它具有更灵活的大小和动态的增加和删除元素。

4.1.2数据结构

ArrayList的数据结构本质上就是数组。区别在于，数组是一种静态的数据结构，需要在创建数组时就指定它的长度，并且创建后长度无法改变。而ArrayList是一种动态的数据结构，它可以自动进行扩容。

ArrayList的底层数据结构：

4.2ArrayList的特点

除了具备List有序性、可重复性特点外，ArrayList还具备以下的特点：

4.2.1自动扩容

当向ArrayList中加入的元素超过了其默认的长度时（由于ArrayList是数组的封装类，在创建ArrayList时不用给定长度，其默认长度为10），它会自动扩容以增加存储容量

4.2.2随机访问

随机访问是指可以直接访问元素，而不需要从头部或者尾部遍历整个列表。由于ArrayList底层是用数组实现的，因此可以通过索引来快速访问元素。

4.2.3 慢速插入/删除：

相比于链表（如LinkedList），ArrayList在中间插入或删除元素较慢，因为需要移动元素。

4.2.4高效的遍历

由于ArrayList底层采用了数组来存储元素，所以对于ArrayList的遍历操作比较高效。

4.3常用方法

代码测试：

package com.xqx.list;

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.List;

public class demo4 {
public static void main(String[] args) throws Exception {
	//创建一个容量为100的集合
	ArrayList list = new ArrayList(100);
	//新增数据前容量
	elementDataLength(list); //当前List集合容量为：100
	for (int i = 0; i < 101; i++) {
		list.add(i);//增加101个元素
	}
	//新增数据后容量大小
	elementDataLength(list); //当前List集合容量为：150
	list.trimToSize();
	//调用trimToSize()方法后容量大小，能够避免资源浪费
	elementDataLength(list); //当前List集合容量为：101
	
	//创建一个容量为4的集合
	ArrayList list2 = new ArrayList(4);
	elementDataLength(list2);//当前List集合容量为：4
	list2.add(1);
	list2.add(2);
	list2.add(3);
	list2.add(4);
	list2.add(5);
	//超过4个元素自动扩容 4*1.5=6
	elementDataLength(list2);//当前List集合容量为：6
	
	//手动扩容，减少扩容次数，影响性能
	list2.ensureCapacity(100);
	
	elementDataLength(list2);//当前List集合容量为：100
	Integer[] arr = new Integer[list2.size()];//注意，传入的数组长度应该至少等于ArrayList的元素个数，否则将会抛出空指针异常。
	for (Integer integer : arr) {
		System.out.println(integer);//null null null null null
	}
	list2.toArray(arr);
	
	for (Integer integer : arr) {
		System.out.println(integer);// 1 2 3 4 5
	}

}

/**
 * 定义一个名为 "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);
}
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

4.4 增长因子论证

我们说ArrayList的底层数据结构是数组，而数组的长度是固定的，但ArrayList长度却是可变的。这里就能产生两个问题：

1、数组和ArrayList的性质都不一样，你怎么能说ArrayList的底层数据结构是数组？

2、即使你已经证明了ArrayList的底层数据结构是数组，那为什么数组的长度是固定的，但ArrayList长度却是可变的？

4.4.1证明ArrayList的底层数据结构是数组

证明第一个问题其实很简单，我们查看源代码即可：

（1）：

（2）：

（3）：

我们一步步往上查看，可以看到有一个名为 elementData 的字段： transient Object[] elementData;

这个字段是用于存储 ArrayList 中所有元素的数组。

通过这些代码实现，我们可以看到 ArrayList 的内部实现确实是基于数组实现的。

4.4.2证明ArrayList的容量可变

证明第二个问题，跟我们ArrayList的一个特点密切相关，没错，聪明的你已经猜出来了,就是自动扩容：

在ArrayList中，每当添加一个元素时，都需要先检查当前数组容量是否足够，如果容量不足，则需要进行扩容操作。而ArrayList的扩容机制是：将原数组的长度乘以一个增长因子，通常是1.5，生成一个新的大数组，然后将原数组中的元素复制到新数组中来，这样就完成了扩容操作。

代码证明：

	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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

我们可以看到内部容量不足时，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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

我们可以看到这次只扩容了两次，从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]
	    }
}
1
2
3
4
5
6
7
8
9
10
11
12

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

为什么 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);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

在重写的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常用方法

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(); 从链表末尾移除一个元素并返回其值
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

考察核心：

• 考察LinkedList的api方法
• 考察堆栈/队列的数据结构特点

六、ArrayList和LinkedList的比较

• 由于ArrayList的数据结构为数组，所以查询修改快，新增删除慢；而LinkedList的数据结构为链表结构，所以查询修改慢，新增删除快
• ArrayList是基于数组实现的动态数组，在内存中有连续的空间，可以通过下标访问元素，由于数组需要提前分配一定大小的空间，因此当元素数量增多之后，可能会导致数组空间不足需要重新分配数组，这种情况下可能会出现内存空间浪费；相比之下，LinkedList是基于链表实现的，每个元素都有一个引用指向下一个元素，不需要提前分配空间，因此能够更加灵活地插入和删除元素。然而，链表在内存中是不连续的，每个元素的引用占用额外的内存空间。由于链表中每个元素都需要有一个指向下一个元素的引用，因此在存储同样数量的元素时，LinkedList通常会占用比ArrayList更大的内存空间。

好啦，今天的分享就到此为止！希望你看完本篇文章有所收获，祝你变得更强！！!