【Java 数据结构】LinkedList与链表

1. ArrayList的缺陷

上节课已经熟悉了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
23

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

2. 链表

2.1 链表的概念及结构

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

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

1. 单向或者双向

• 带头或者不带头
  
• 循环或者非循环
  
  虽然有这么多的链表的结构，但是我们重点掌握两种:
• 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
• 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

2.2 链表的实现

自己实现接口ILIST

public interface IList {
    //头插法
    void addFirst(int data);
    //尾插法
    void addLast(int data);
    //任意位置插入,第一个数据节点为0号下标
    void addIndex(int index,int data);
    //查找是否包含关键字key是否在单链表当中
    boolean contains(int key);
    //删除第一次出现关键字为key的节点
    void remove(int key);
    //删除所有值为key的节点
    void removeAllKey(int key);
    //得到单链表的长度
    int size();
    void clear();
    void display();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

链表实现

public class MySingleList implements IList {

    //节点的内部类
    static class ListNode {
        public int val;
        public ListNode next;

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


    public ListNode head;
    //public int usedSize;//可以定义

    public void createList() {
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);

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

        this.head = node1;
    }

    @Override
    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;
        }
    }

    @Override
    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 现在指向了最后一个节点
            cur.next = node;
        }

    }

    @Override
    public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            //抛自定义的异常
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = searchPrev(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }

    private ListNode searchPrev(int index) {
        ListNode cur = this.head;
        int count = 0;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if (this.head == null) {
            //一个节点都没有 无法删除！
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        //1. 找到前驱
        ListNode cur = findPrev(key);
        //2、判断返回值是否为空？
        if (cur == null) {
            System.out.println("没有你要删除的数字");
            return;
        }
        //3、删除
        ListNode del = cur.next;
        cur.next = del.next;


    }

    /**
     * 找到关键字key的前一个节点的地址
     *
     * @param key
     * @return
     */
    private ListNode findPrev(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    @Override
    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;
        }
    }

    @Override
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

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

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


    /**
     * 这个是从指定位置开始打印
     *
     * @param newHead
     */
    public void display(ListNode newHead) {
        ListNode cur = newHead;
        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
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
204
205
206
207
208
209
210
211
212
213
214
215

3. LinkedList的模拟实现

// 2、无头双向链表实现
public class MyLinkedList {
	//头插法
	public void addFirst(int data){ }
	//尾插法
	public void addLast(int data){}
	//任意位置插入,第一个数据节点为0号下标
	public void addIndex(int index,int data){}
	//查找是否包含关键字key是否在单链表当中
	public boolean contains(int key){}
	//删除第一次出现关键字为key的节点
	public void remove(int key){}
	//删除所有值为key的节点
	public void removeAllKey(int key){}
	//得到单链表的长度
	public int size(){}
	public void display(){}
	public void clear(){}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4.LinkedList的使用

4.1 什么是LinkedList

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

在集合框架中，LinkedList也实现了List接口

【说明】

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

4.2LinkedList的使用

1. LinkedList的构造
   

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

2. LinkedList的其他常用方法介绍
   
3. 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

5. ArrayList和LinkedList的区别