数据结构

LinkedList与链表

链表

链表的概念及结构

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

实际中链表的结构非常多样

  1. 单向或者双向
  2. 带头或者不带头
  3. 循环或者非循环

重点掌握：

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

链表的实现 

  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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203

package MyLlist;

public class Node {
    int data;
    Node next;
    public Node(int data){
        this.data = data;
    }
}


package MyLlist;

/**
 * 该类实现了一个无头单向非循环链表，包含链表的基本操作，如插入、删除、查找等。
 */
public class MyLinkedList {
    // 链表的头节点
    Node head;

    /**
     * 构造函数，初始化链表，将头节点置为 null，表示链表为空。
     */
    public MyLinkedList(){
        head = null;
    }

    // 1、无头单向非循环链表实现
    /**
     * 头插法，将新节点插入到链表头部。
     * @param data 要插入节点的数据
     */
    public void addFirst(int data){
        // 创建一个新节点
        Node node = new Node(data);
        // 如果链表为空，直接将新节点作为头节点
        if (head == null){
            head = node;
            return;
        }
        // 新节点的 next 指向原头节点
        node.next = head;
        // 更新头节点为新节点
        head = node;
    }
    /**
     * 尾插法，将新节点插入到链表尾部。
     * @param data 要插入节点的数据
     */
    public void addLast(int data){
        // 创建一个新节点
        Node node = new Node(data);
        // 如果链表为空，直接将新节点作为头节点
        if (head == null){
            head = node;
            return;
        }
        // 找到链表的最后一个节点
        Node cur = head;
        while (cur.next != null){
            cur = cur.next;
        }
        // 最后一个节点的 next 指向新节点
        cur.next = node;
    }
    /**
     * 在任意位置插入节点，第一个数据节点为 0 号下标。
     * @param index 插入位置的下标
     * @param data 要插入节点的数据
     */
    public void addIndex(int index,int data){
        // 检查插入位置是否合法
        if (index < 0 || index > size()){
            System.out.println("位置不合法");
            return;
        }
        // 如果插入位置为 0，调用头插法
        if (index == 0){
            addFirst(data);
            return;
        }
        // 创建一个新节点
        Node node = new Node(data);
        // 找到插入位置的前一个节点
        Node cur = head;
        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;
        }
        // 新节点的 next 指向插入位置的节点
        node.next = cur.next;
        // 插入位置的前一个节点的 next 指向新节点
        cur.next = node;
    }
    /**
     * 查找链表中是否包含关键字 key。
     * @param key 要查找的关键字
     * @return 如果包含返回 true，否则返回 false
     */
    public boolean contains(int key){
        // 从链表头开始遍历
        Node cur = head;
        while (cur != null){
            // 如果当前节点的数据等于关键字，返回 true
            if (cur.data == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    /**
     * 删除链表中第一次出现关键字为 key 的节点。
     * @param key 要删除节点的关键字
     */
    public void remove(int key){
        // 如果链表为空，直接返回
        if (head == null){
            return;
        }
        // 如果头节点的数据等于关键字，更新头节点
        if (head.data == key){
            head = head.next;
            return;
        }
        // 找到要删除节点的前一个节点
        Node cur = head;
        while (cur.next != null){
            // 如果下一个节点的数据等于关键字，删除该节点
            if (cur.next.data == key){
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
    }
    /**
     * 删除链表中所有值为 key 的节点。
     * @param key 要删除节点的关键字
     */
    public void removeAllKey(int key){
        // 如果链表为空，直接返回
        if (head == null){
            return;
        }
        // 处理头节点数据等于关键字的情况
        while (head != null && head.data == key) {
            head = head.next;
        }
        // 从链表头开始遍历
        Node cur = head;
        while (cur != null && cur.next != null){
            // 如果下一个节点的数据等于关键字，删除该节点
            if (cur.next.data == key){
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
    }
    /**
     * 获取链表的长度。
     * @return 链表的长度
     */
    public int size(){
        int count = 0;
        // 从链表头开始遍历
        Node cur = head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    /**
     * 清空链表，释放所有节点的引用。
     */
    public void clear() {
        // 从链表头开始遍历
        Node cur = head;
        while (cur != null){
            // 保存下一个节点的引用
            Node next = cur.next;
            // 断开当前节点的 next 引用
            cur.next = null;
            cur = next;
        }
        // 将头节点置为 null
        head = null;
    }
    /**
     * 打印链表中的所有元素。
     */
    public void display() {
        // 从链表头开始遍历
        Node cur = head;
        while (cur != null){
            // 打印当前节点的数据
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

LinkedList的模拟实现 

  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

public class MyLinkedList implements IList{

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

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



    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if(head == null) {
            head = last = node;
        }else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }
 
    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(head == null) {
            head = last = node;
        }else {
            last.next = node;
            node.prev = last;
            last = last.next;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        int len = size();
        if(index < 0 || index > len) {
            return;
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == len) {
            addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = findIndex(index);
        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;
    }
    @Override
    public void remove(int key) {

        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                //开始删除
                if(cur == head) {
                    head = head.next;
                    if(head != null) {
                        head.prev = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next == null) {
                        last = last.prev;
                    }else {
                        cur.next.prev = cur.prev;
                    }
                }
               return;
            }
            cur = cur.next;
        }
    }
    @Override
    public void removeAllKey(int key) {

        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                //开始删除
                if(cur == head) {
                    head = head.next;
                    if(head != null) {
                        head.prev = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next == null) {
                        last = last.prev;
                    }else {
                        cur.next.prev = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }
    @Override
    public void clear() {

        ListNode cur = head;
        while (cur != null) {
            ListNode curN = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curN;
        }
        head = last = null;
    }

    @Override
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    @Override
    public int size() {
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
}

LinkedList的使用

什么是LinkedList

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

【说明】

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

LinkedList的构造

方法 解释
LinkedList() 无参构造方法，创建一个空的链表
public LinkedList(Collection<? extends E> c) 使用其他集合容器中的元素构造 LinkedList 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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);
}

LinkedList的其他常用方法

方法 解释
boolean add(E e) 在链表尾部插入元素 e
void add(int index, E element) 在指定 index 位置插入元素 element
boolean addAll(Collection<? extends E> 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) 截取链表中从 fromIndex 到 toIndex 的子链表 
 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

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());
}

LinkedList的遍历 

 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

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();
}

ArrayList和LinkedList的区别

不同点 ArrayList LinkedList
存储空间 物理上一定连续 逻辑上连续，物理上不一定连续
随机访问 支持 O(1) 时间复杂度 不支持，需要 O(N) 时间复杂度
头插 需要搬移元素，效率低 O(N) 只需修改引用的指向，时间复杂度 O(1)
插入 空间不够时需要扩容 没有容量的概念
应用场景 元素高效存储 + 频繁访问 任意位置插入和删除频繁
© 2025 一夕夙愿
微信：zxcyuijkl
使用 Hugo 构建
主题 Stack 由 Jimmy 设计