【Java】轻松掌握链表操作_java对链表的操作

1.1 什么是链表

在数组存储的过程中，数组的存储必须使用连续的内存空间，并且会预留一部分空间方便扩展。这样在内存中会大大降低内存的使用率，这种事情是不被接受的。所以出现了一种新的数据结构，叫作——链表

综上可知：链表的发明其实是对数组的一种补充。因此它的功能和数组非常类似，都是用于存储一系列相同类型的数组，并且都有增删改查等基本操作

用一句话来总结：

数组能做的所有事情，一般都可以用链表实现

只是他们的存储方式不同，导致他们的实现逻辑也不同，同样时间复杂度也将不同。下面我们来分析一下链表的特性：

节点

数组里面每个元素我们称之为元素，而链表中每个元素我们称为节点。

从图中看出，每个节点都是由两部分组成 — 节点内容和下一个节点地址。元素和节点的差别就在这个下一个节点地址

在数组中，由于是连续内存空间存储，我们可以通过 start_address + item_size * i 计算元素的位置。而在链表中，存储空间是分散存储的，所以我们需要每个节点保存下一个节点的位置。也就是可以通过节点 1 找到节点 2，节点 2 找到节点 3…依次遍历所有的节点信息

从这个结构，可以看出链表对于数组最大的好处，它可以将数据分散存储在内存中，达到内存最大利用率

代码创建链表：

public class Node {

	private int content;

  	private Node next;

  	public Node() {
  	}

  	public Node(int content, Node next) {
    	this.content = content;
    	this.next = next;
  	}

  	public int getContent() {
    	return content;
  	}

  	public void setContent(int content) {
    	this.content = content;
  	}

  	public Node getNext() {
    	return next;
  	}

  	public void setNext(Node next) {
    	this.next = next;
  	}
}
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

// 创建链表
public static Node createLinkedList(int[] array) {
    // 创建一个根节点
    Node root = null;
    // 从末尾元素开始依次创建Node节点
    for (int i = array.length - 1; i >= 0; i--) {
        Node node = new Node(array[i], null);
        // 创建两个节点的连接关系
        if (root != null) {
            node.setNext(root);
            root = node;
        } else {
            root = node;
        }
    }
    // 返回根节点
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.2 链表的读取与查找

链表中索引内容读取

看一下数组是如何进行数据的读取的：

因为数组是连续内存空间存储的，通过 start_address + item_size * i 便能计算出索引地址，然后 1 步便完成内容的读取，时间复杂度是 O(1)

那链表中应该如何操作呢？比如我们要找到 9, 2, 4 链表中索引为 2 的存储内容？

计算机肯定是无法一步完成这个操作，因为链表在内存中是分散存储的，我们现在只有第一个节点的地址，因此需要依次遍历找到第 3 个节点的地址

时间复杂度

从上图可以看出，链表中的读取时间复杂度和索引值有关。最好的情况是读取第一个节点，只需要一步。因此链表的读取时间复杂度为 O(N)，相比较数组性能可能会差一点

链表中遍历查找元素

如果想要在链表 9, 2, 4 中查找是否包含某个节点它的内容是4，该如何操作？

我们同样需要利用第一个节点，依次往后面遍历，每次遍历到一个节点，比较这个节点内容是否为 4

逻辑很简单，所需步数和读取索引值一样，最好的情况在第一个节点就可以查找到，著需要1步。最差的情况是在最后一个节点才查找到，需要N步

所以时间复杂度为 O(N)，查找元素的时间复杂度和数组是一样的

代码如下：

public class OrangeLinkedList {

  	private Node root = null;
  	int size = 0;

  	public OrangeLinkedList() {
  	}

  	// 数组创建一个链表
  	public static Node createLinkedLNode(int[] array) {
    	// 创建一个根节点
    	Node root = null;
    	// 从末尾元素开始依次创建Node节点
    	for (int i = array.length - 1; i >= 0; i--) {
      		Node node = new Node(array[i], null);
      		// 创建两个节点的连接关系
      		if (root != null) {
        		node.setNext(root);
        		root = node;
      		} else {
        		root = node;
      		}
    	}
    	return root;
  	}

  	public orangeLinkedList(int[] array) {
    	this.root = YKDLinkedList.createLinkedLNode(array);
    	this.size = array.length;
  	}

  	// 获取长度
  	public int size() {
    	return this.size;
  	}

  	// 获取某个索引节点内容
  	public int get(int index) {
    	int i = 0;
    	Node node = this.root;
    	// 依次往前推进
    	while (i < index) {
      		node = node.getNext();
      		i++;
    	}
    	return node.getContent();
  	}

  	// 查找某个值的索引值，默认不存在为-1
  	public int find(int value) {
    	Node node = this.root;
    	// index 保存当前的索引
    	int index = 0;
    	// 依次遍历链表，找到内容等于value的node，返回index
    	while (node != null) {
      		if (node.getContent() == value) {
        		return index;
      		}
      		node = node.getNext();
      		index++;
    	}
    	return -1;
  	}

    // 提供数据进行测试
  	public static void main(String[] args) {
    	int[] array = {1, 2, 3};
    	orangeLinkedList linkedList = new OrangeLinkedList(array);
    	System.out.println(linkedList.find(2));
    	System.out.println(linkedList.find(8));
    	System.out.println(linkedList.get(2));
  	}
}
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

1.3 链表的插入

头部插入分两部分执行：

1. 新节点的 next 指向原来的 root 节点
2. root 指针指向新节点

时间复杂度很容易计算出来为 O(1)

同理，中间插入也是分为两部分执行：

1. 新节点 next 指向原来前置节点的 next
2. 原来前置节点的 next，指向新节点

看起来也只需要 O(1) 就能完成插入，但是这样的插入有一个前置条件，也就是我们知道插入节点的前置节点。否则，我们只能根据索引通过 N步 找到前置节点

尾部插入和中间插入的逻辑完全一样。只是中间插入的时候前置节点的 next 是一个节点，而此处为 null：

1. 新节点 next 指向原来前置节点的 next（此处为null）
2. 原来前置节点的 next，指向新节点

通过上面的对比，我们可以总结如下：

如果已经知道插入节点的前置节点，那么链表的插入时间复杂度为 O(1) 普通情况（根据索引值插入节点），插入的时间复杂度为 O(N) 这个和数组是一样的。但有趣的是，链表插入的最好和最差的情况刚好和数组相反，链表在头部插入很方便，但是数组开头插入确很麻烦。而数组在尾部插入很方便，但链表尾部插入要先扫描再插入

1.4 链表的删除

头部删除分为两步执行：

1. root 指针指向第二个节点
2. 原始 root 节点的 next 设置为 Null

时间复杂度很容易计算出来为 O(1)

同理，中间删除也分为两部分执行

1. 待删除节点前置节点 next 指向待删除节点后置节点
2. 待删除节点的 next，指向 Null

看起来好像也只需要 O(1) 就能完成删除，但是这样的删除有一个前置条件，也就是我们知道插入节点的前置节点。否则，我们只能根据索引通过 N步 找到前置节点

尾部删除和中间删除的逻辑完全一样。只是中间删除的时候前置节点的 next 改为待删除节点的后置节点，而此处后置节点为 null

待删除节点原本的 next 为 null，所以不需要再赋值为空。但是，我们仍然必须需要执行 N步 找到倒数第二个节点，再执行上面的删除操作

总结：其实删除操作，只是插入操作的反操作，原理还是比较容易理解，我们总结一下链表删除的时间复杂度

如果已经知道待删除节点的前置节点，那么链表的删除时间复杂度为 O(1) 普通情况（根据索引值删除节点），因为需要新找到前置节点，所以时间复杂度为 O(N)，这个和数组一样。和链表插入一样，链表删除的最好和最差的情况刚好和数组想反，链表在头部删除很方便，但是数组开头删除却很麻烦。而数组在尾部删除很方便，但链表尾部删除要先扫描再删除

链表插入和删除的代码如下：

public class OrangeLinkedList {

 	private Node root = null;
  	int size = 0;

  	public OrangeLinkedList() {
  	}

  	// 数组创建一个链表
  	public static Node createLinkedLNode(int[] array) {
    	// 创建一个根节点
    	Node root = null;
    	// 从末尾元素开始依次创建Node节点
    	for (int i = array.length - 1; i >= 0; i--) {
      		Node node = new Node(array[i], null);
      		// 创建两个节点的连接关系
      		if (root != null) {
        		node.setNext(root);
        		root = node;
      		} else {
        		root = node;
      		}
    	}
    	return root;
  	}

  	public OrangeLinkedList(int[] array) {
    	this.root = YKDLinkedList.createLinkedLNode(array);
    	this.size = array.length;
  	}

  	// 获取长度
  	public int size() {
    	return this.size;
  	}

  	// 获取某个索引节点内容
  	public int get(int index) {
    	int i = 0;
    	Node node = this.root;
    	// 依次往前推进
    	while (i < index) {
      		node = node.getNext();
      		i++;
    	}
    	return node.getContent();
  	}

  	// 查找某个值的索引值，默认不存在为-1
  	public int find(int value) {
    	Node node = this.root;
    	// index 保存当前的索引
    	int index = 0;
    	// 依次遍历链表，找到内容等于value的node，返回index
    	while (node != null) {
      		if (node.getContent() == value) {
        		return index;
      		}
      		node = node.getNext();
      		index++;
    	}
    	return -1;
  	}

  	// 末尾添加元素
  	public boolean add(int value) {
    	return this.add(this.size - 1, value);
  	}

  	// 头部插入元素
  	public boolean addFirst(int value) {
    	return this.add(-1, value);
  	}

  	// 插入元素
  	public boolean add(int index, int value) {
    	if (index < -1 || index > this.size - 1){
      		return false;
    	}
    	if (index == -1) {
      		if (this.root != null) {
        		this.root = new Node(value, this.root);
      	} else {
        	this.root = new Node(value, null);
    	} else {
      		Node pre = this.root;
      		while (index > 0) {
        		if (pre.getNext() == null) {
          			return false;
        		}
        		pre = pre.getNext();
        		index--;
      		}

      		if (pre == null) {
        		return false;
      		}

      		Node newNode = new Node(value, pre.getNext());
      		pre.setNext(newNode);
    	}
    	this.size++;
    	return true;
  	}

  	// 删除最后一个元素
  	public boolean removeLast() {
    	return this.remove(this.size - 1);
  	}

  	// 删除第一个元素
  	public boolean removeFirst() {
    	return this.remove(0);
  	}

  	// 插入元素
  	// index = 0, 表示删除第 1 个元素
  	// index = n，表示删除第 n+1 个元素
  	public boolean remove(int index) {
    	if (index < 0 || index > this.size - 1){
      		return false;
    	}
    	// 判断整个列表为空情况，删除失败
    	if (this.root == null) {
      		return false;
    	}
    	if (index == 0) {
      		// 删除第一个元素，情况比较简单，注意必须先保留 this.root，因为紧接着 this.root 会被修改
      		Node node = this.root;
      		this.root = node.getNext();
      		node.setNext(null);
    	} else {
      	// 判断越界问题
      	if(this.size < index + 1){
        	return false;
      	}
      	// 遍历获取index的前置节点
      	Node pre = this.root;
      	while (index > 1) {
        	pre = pre.getNext();
        	index--;
      	}
      		// 修改next指针，同样大家需要先保存 pre.next，因为紧接着下一步会修改 pre.next 指针
      		Node next = pre.getNext();
      		pre.setNext(next.getNext());
      		next.setNext(null);
    	}
    	this.size--;
    	return true;
  	}

  	// 链表中的元素字符串形式
  	public String toString() {
    	if (this.root == null) {
      		return "";
    	}

    	StringBuilder str = new StringBuilder();
    	Node node = this.root;
    	while (node != null) {
      		str.append(node.getContent()).append(" ");
      		node = node.getNext();
    	}
    	return str.toString();
  	}

  	public static void main(String[] args) {
    	int[] array = {10, 9, 2, 4};
    	OrangeLinkedList linkedList = new OrangeLinkedList(array);
    	boolean result = linkedList.removeFirst();
    	if (!result) {
      		System.out.println("removeFirst失败");
      		return;
    	}
    	result = linkedList.removeLast();
    	if (!result) {
      		System.out.println("removeLast失败");
      		return;
    	}
    	result = linkedList.remove(1);
    	if (!result) {
      		System.out.println("remove(1)失败");
      		return;
    	}

    	System.out.println(linkedList.toString());
  	}
}
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

1.5 链表 vs 数组

链表与数组在性能上有什么区别？

链表看似除了在存储方面有优势，好像其他都不如数组。但是在复杂场景下，表现并不是这样：

我们手里有一堆手机号码，我们希望写一个算法删除无效的手机号码。具体逻辑为：我们每次读取一个手机号码，判断这个手机号码是否为11为，并且满足一定的正则表达式要求

这种场景下应该用什么数据结构存储这一堆手机号码呢？

在这个场景下最关键的两个因素遍历和删除

遍历

无论使用数组或者链表进行存储，都需要经历 N 次遍历。这部分无法减小

删除

如果使用数组删除的话，每次都需要移动后面的元素，所以每次删除的时间复杂度都是 O(N)

而如果使用链表的话，就不存在这个问题。因为在遍历场景下，我们都可以拿到需要删除节点的前置节点，所以在这个场景下的删除时间复杂度为 O(1)

总结

简单统计下，在这种场景下使用数组的操作的时间复杂度为 O(N^2)。而使用链表的时间复杂度为 O(N)

从这个例子看出链表在频繁插入和删除的情况下，有绝对的优势！

1.6 双向链表

双向链表的特点：

1. 对于每个节点，由三部分组成，prev（指向前一个节点），next（指向后一个节点），content（节点内容）
2. 对于双向链表，为了方便遍历，我们需要同时保留第一个节点和最后一个节点

阅读 LinkedList 源码，我们会发现它实际上就是利用 双向链表 实现的，在源码中我们可以找到如下代码：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

    /**
     * Constructs an empty list.
     */
    public 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

需要关注这里的两个变量 first 和 last。分别表示双向链表的头部和尾部两个节点