【数据结构】链表

⭐ 作者：小胡_不糊涂
🌱 作者主页：小胡_不糊涂的个人主页
📀 收录专栏：浅谈数据结构
💖 持续更文，关注博主少走弯路，谢谢大家支持 💖

链表

1. ArrayList的缺陷
2. 链表
3. LinkedList的使用
- 3.1 什么是LinkedList
- 3.2LinkedList的使用
4. ArrayList和LinkedList的区别

1. ArrayList的缺陷

通过源码可以知道，ArrayList底层是使用数组来存储元素的：

public class ArrayList<E> extends AbstractList<E>
	implements List<E>, RandomAccess, Cloneable, java.io.Serializable
	{
		// ...
		// 默认容量是10
		private static final int DEFAULT_CAPACITY = 10;
		//...
		// 数组：用来存储元素
		transient Object[] elementData; // non-private to simplify nested class access
		// 有效元素个数
		private int size;
		public ArrayList(int initialCapacity) {
			if (initialCapacity > 0) {
				this.elementData = new Object[initialCapacity];
			} else if (initialCapacity == 0) {
				this.elementData = EMPTY_ELEMENTDATA;
			} else {
				throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
			}
		}
		// ...
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。

2. 链表

2.1 链表的概念

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

链表的结构如下图所示：
在这里插入图片描述

从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
现实中的结点一般都是从堆上申请出来的
从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

单向、双向链表
不带头、带头链表
循环、非循环链表

注：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等。
无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

2.2 无头单向非循环链表的模拟实现

public class SingleLinkedList {
    static class ListNode{
        public int val;
        public ListNode next;//指向当前结点的下一个结点

        public ListNode(int val){
            this.val=val;
        }
    }

    public ListNode head;

    //创建一段链表
    public void creatList(){
        ListNode node1=new ListNode(3);
        ListNode node2=new ListNode(7);
        ListNode node3=new ListNode(9);
        ListNode node4=new ListNode(6);

        node1.next=node2;
        node2.next=node3;
        node3.next=node4;

        this.head=node1;
    }

    //头插法
    public void addFirst(int data){
        ListNode node=new ListNode(data);
        //判断链表是否为空
        if(this.head==null){
            this.head=node;
        }else{
            node.next=this.head;
            this.head=node;
        }

    }
    //尾插法
    public void addLast(int data){
        ListNode node=new ListNode(data);
        ListNode cur=this.head;
        if(this.head==null){
            this.head=node;
        }else{
            //找到尾巴
            while(cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
        }
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        if(index < 0 || index > size()) {
            throw new PosIllegality("插入元素下标异常: "+index);
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        //找到前一个结点
        ListNode node=new ListNode(data);
        ListNode pre=this.head;
        while(index>1){
            pre=pre.next;
            index--;
        }
        node.next=pre.next;
        pre.next=node;

    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = this.head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        //链表为空
        if(this.head==null){
            return;
        }
        //首结点==key
        if(this.head.val==key){
            this.head=this.head.next;
            return;
        }

        //其他情况
        //找前驱结点
        ListNode pre=this.head;
        while(pre.next.val==key && pre.next!=null){
            pre=pre.next;
        }
        if(pre.next==null){
            System.out.println("没有你要找的值");
            return;
        }
        pre=pre.next.next;
    }

    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(this.head == null) {
            return;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.val == key) {
            head = head.next;
        }
    }

    //得到单链表的长度
    public int size(){
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public void clear() {
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            //cur.val = null;
            cur.next = null;
            cur = curNext;
        }
        head = null;
    }

    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
}
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

测试类：

public static void main(String[] args) {
        SingleLinkedList singleLinkedList=new SingleLinkedList();
        singleLinkedList.creatList();
        singleLinkedList.addLast(10);
        singleLinkedList.display();

        singleLinkedList.addFirst(1);
        singleLinkedList.display();

        singleLinkedList.addIndex(3,10);
        singleLinkedList.display();

        System.out.println(singleLinkedList.contains(3));

        singleLinkedList.remove(10);
        singleLinkedList.display();

        System.out.println(singleLinkedList.size());

        singleLinkedList.removeAllKey(7);
        singleLinkedList.display();

        singleLinkedList.clear();
        singleLinkedList.display();
    }
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

PosIllegality异常类：

public class PosIllegality extends RuntimeException{
    public PosIllegality(String msg) {
        super(msg);
    }
}
1
2
3
4
5

2.3 无头双向链表的模拟实现

public class MyLinkedList {
    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode prev;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;//指向头结点
    public ListNode last;//指向尾结点

    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            head = node;
            last = node;
        }else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            head = node;
            last = node;
        }else {
            last.next = node;
            node.prev = last;
            last = node;
        }
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        int len = size();
        // 检查index是否合法
        if(index < 0 || index > len) {
            throw new PosIllegality("插入元素下标异常: "+index);
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == len) {
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);
        ListNode node = new ListNode(data);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }
    //找当前节点前一个结点
    private ListNode findIndex(int index) {
        ListNode cur = head;
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key){
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                if(cur == head) {
                    head = head.next;//head == null
                    if(head == null) {
                        last = null;
                    }else {
                        head.prev = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next == null) {
                        last = last.prev;
                    }else {
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }else {
                cur = cur.next;
            }
        }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //得到单链表的长度
    public int size(){
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public void display(){
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void clear(){
        head = null;
        last = null;

    }
}
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

测试类：

public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(1);
        myLinkedList.addLast(2);
        myLinkedList.addLast(3);
        myLinkedList.addLast(4);
        myLinkedList.display();

        myLinkedList.addFirst(0);
        myLinkedList.display();

        myLinkedList.addIndex(2,9);
        myLinkedList.display();

        myLinkedList.remove(9);
        myLinkedList.display();

        myLinkedList.clear();
        myLinkedList.display();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3. LinkedList的使用

3.1 什么是LinkedList

LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

在集合框架中，LinkedList也实现了List接口，具体如下：
在这里插入图片描述
说明：

LinkedList实现了List接口
LinkedList的底层使用了双向链表
LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
.LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
LinkedList比较适合任意位置插入的场景

3.2LinkedList的使用

LinkedList的构造：

方法	解释
LinkedList()	无参构造
public LinkedList(Collection c)	使用其他集合容器中元素构造List

例如：

public static void main(String[] args) {
	// 构造一个空的LinkedList
	List<Integer> list1 = new LinkedList<>();
	
	List<String> list2 = new java.util.ArrayList<>();
	list2.add("JavaSE");
	list2.add("JavaWeb");
	list2.add("JavaEE");
	
	// 使用ArrayList构造LinkedList
	List<String> list3 = new LinkedList<>(list2);
}
1
2
3
4
5
6
7
8
9
10
11
12

LinkedList的其他常用方法：

方法	解释
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection c)	尾插 c 中的元素
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置元素
E set(int index, E element)	将下标 index 位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)	截取部分 list

使用实例：

import java.util.LinkedList;
import java.util.List;
public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1); // add(elem): 表示尾插
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        System.out.println(list.size());
        System.out.println(list);
        // 在起始位置插入0
        list.add(0, 0); // add(index, elem): 在index位置插入元素elem
        System.out.println(list);
        list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
        list.removeFirst(); // removeFirst(): 删除第一个元素
        list.removeLast(); // removeLast(): 删除最后元素
        list.remove(1); // remove(index): 删除index位置的元素
        System.out.println(list);
		// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
        if(!list.contains(1)){
            list.add(0, 1);
        }
        list.add(1);
        System.out.println(list);
        System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
        System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
        int elem = list.get(0); // get(index): 获取指定位置元素
        list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
        System.out.println(list);
		// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
        List<Integer> copy = list.subList(0, 3);
        System.out.println(list);
        System.out.println(copy);
        list.clear(); // 将list中元素清空
        System.out.println(list.size());
    }
}
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

LinkedList的遍历：

public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1); // add(elem): 表示尾插
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        System.out.println(list.size());
        // foreach遍历
        for (int e:list) {
            System.out.print(e + " ");
        }
        System.out.println();
        // 使用迭代器遍历---正向遍历
        ListIterator<Integer> it = list.listIterator();
        while(it.hasNext()){
            System.out.print(it.next()+ " ");
        }
        System.out.println();
        // 使用反向迭代器---反向遍历
        ListIterator<Integer> rit = list.listIterator(list.size());
        while (rit.hasPrevious()){
            System.out.print(rit.previous() +" ");
        }
        System.out.println();
    }
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

4. ArrayList和LinkedList的区别

不同点	ArrayList	LinkedList
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
头插	需要搬移元素，效率低O(N)	只需修改引用的指向，时间复杂度为O(1)
插入	空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁

相关阅读:
Redis高可用实战之Cluster
阿里内部强推的SpringScurity实战笔记，与君共分享
 好用软件推荐
 JavaWeb开发之——DDL-操作表-数据类型(08)
Node.js 基础学习
 Java线程池是如何保证核心线程不被销毁的
 MacOS使用clion配置mounriver 工具链
 HDU_1018
[论文评析]基于人体姿态识别的立定跳远动作智能评估系统
 RabbitMQ
原文地址：https://blog.csdn.net/iLoyo_/article/details/133847674