数据结构

数据结构表（ADT）解析(下)

1、前言

这部分的内容是根据之前的ADT讲解所遗留下来的内容，如果有什么不太明确，可以看之前的博客。

2、LinkedList的简单实现。

ArrayList底层是由数组实现的，而LinkedList底层是通过链表实现的，但是在Java当中是没有链表这种数据结构的。所以我们要通过自定义来进行。

2.1、分析

我们上述已经知道我们需要通过自定义底层节点，来实现双向链表，所以定义一个Node< T >是必须的，关于链我们直接通过Java当中的索引来做，我们还需要对当前双向链表进行简单的改造，通过标记节点来完成。还需要对该集合的操作进行定义，在这里提供出三个核心方法，其与的方法都是建立在这三个核心方法之上的。最后为了可以通过Iterable进行遍历，提供一个LinkedListIterator。我们可以把我们要完成的在下方总结一下：

  • 自定义Node< T >。
  • 添加头节点和尾节点。
  • 对外提供操作。
  • 对外提供LinkedListIterator 好进行遍历。

2.2、节点和链

我们知道一个节点，应该包含有三个部分，第一个部分应该是指上一个节点的索引，第二部分应该是该节点所含有的数据，第三部分应该是指向下一个节点的索引。

note的内容

具体实现如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 节点类，用来表示链表当中的一个节点。
 *
 * @author pengchengliu
 * @param <AnyType>
 */
//TODO : 问题一：为什么选择是private。
//TODO : 问题二：为什么选择是static。
private static class Node<AnyType>{
	
	//TODO ：为什么内部属性选用public 。
	public AnyType data ;
	public Node<AnyType> prev ;
	public Node<AnyType> next ;
	
	public Node(AnyType data, Node<AnyType> prev, Node<AnyType> next){
		this.data = data ;
		this.prev = prev ;
		this.next = next ;
	}
}

在上述代码当中，笔者提到了三个问题。这这里简单的说一下。

第一个问题：为什么选择是private。

答案 ： 应该这个内部类没有必要暴露给外部，外部只要默默的使用该类就Ok，不需要知道内部实现细节，注意这里的外部是指使用LinkedList的外部的类，而不是LinkedList。

第二个问题：为什么选择是static。

答案：这里应该是静态内部类和内部类的区别。想深入理解一下的看客可以去输入了解一下。这里笔者简单的说一下，Node这个类是独立于LinkedList的，也就是Node这个类没有使用到LinkedList这个类的实例，并且Node不依赖于LinkedList实例被实例化。所以选择static了。

第三个问题：为什么内部属性选用public

答案：这个问题好回答，既然整个类都是private，内部是用public也就无所谓了。

2.3、标记节点

了解了上述Node类以后，这里特别说明一下有两个比较特殊的位置，就是第一个元素和最后一个元素，我们第一个元素的第一部分应该是null，而最后一个节点的第三部分应该是null，当我们检测到了最后一个节点的第三部分是null，则代表遍历结束，这是基本的链表结构，但是为了省去不必要的麻烦，我们使用标记节点。代替第一个元素和最后一个元素。为什么选择标记节点。

标记节点

需要注意的是由于第一个元素和最后一个元素都比较特殊，所以通过标记节点头节点和尾节点。

为什么使用标记节点呢？

如果我们不使用标记节点，我们会存在特殊情况，比如删除或者添加第一个元素，这样就会存在一种可能，那就是我们需要改变第一个元素的位置，而如果有标记节点的话，第一个元素的位置和最后一个元素的位置就是一定的，我们规避了这一种特殊情况。

2.4、主要操作

我们知道数据结构重要的地方有两点，第一个比较重要的地方就是集合内的元素，而第二个重要的地方就是操作。

2.4.1、清空集合

因为我们有标记节点，所以我们清空集合只需要，让头节点指向尾节点，尾节点指向头节点，然后让size为0即可。效果图如下所示

head节点

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 清空当前的容器
 */
public void clear() {
	beginMarker = new Node<AnyType>(null, null, null);
	endMarker = new Node<AnyType>(null, beginMarker, null);
	beginMarker.next = endMarker ;
	
	//	重置计数器。
	theSize = 0 ;
	modCount++ ;
}

2.4.2、插入元素

在固定的位置插入一个元素，也就是说，改变该位置上面前后节点的链即可，具体的步骤如下图所示：

插入元素

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
/**
 * 添加一个元素，将元素item添加到node之前。此方法为其他方法的服务方法，所以不需要暴露给外部类调用
 */
private void addBefore(Node<AnyType> node, AnyType item){
	Node<AnyType> itemNode = new Node<AnyType>(item, node.prev, node);
	itemNode.prev.next = itemNode ;
	node.prev = itemNode ;
	//更新计数器。
	theSize ++ ;
	modCount ++ ;
}

2.4.3、移除元素

这个操作方法和上述插入元素，没有什么区别，也是改变前后节点的链的问题。

移除元素

代码实现如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 移除一个元素，将oldNode在原有的集合当前删除。
 * @param oldNode
 * @return
 */
private AnyType remove(Node<AnyType> oldNode){
	oldNode.next.prev = oldNode.prev ;
	oldNode.prev.next = oldNode.next ;
	//更新计数器
	theSize-- ;
	modCount++ ;
	return oldNode.data ;
}

2.4.4、得到节点

通过下标得到相应的Node，具体的代码实现如下所示：

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
/**
 * 得到一个元素，根据index下表值，得到一个元素
 * @param index 下表值
 * @return 得到的元素。
 */
private Node<AnyType> getNode(int index){
	Node<AnyType> tempNode ;
	//下标合法性验证
	if(index < 0 || index > this.size()){
		throw new IndexOutOfBoundsException();
	}
	//由于是双向列表，所以根据index的值不同在两端获取。使得效率更加的高效，O(N/2)的时间复杂度。
	if(index < this.size() / 2){
		//从开头开始找,获取第一个元素
		tempNode = beginMarker.next ;
		for(int i = 0; i < index; i ++){
			tempNode = tempNode.next ;
		}
	} else {
		//从结尾开始找,获取最后一个元素。
		tempNode = endMarker.prev ;
		for(int i = this.size(); i > index; i--){
			tempNode = tempNode.prev ;
		}
	}
	return tempNode ;
}

2.5、LinkedListIterator的实现。

代码实现如下所示：

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
/***
	 * LinkedList的迭代器。
	 * @author pengchengliu
	 *
	 */
	private class LinkedListIterator implements Iterator<AnyType>{

		//当前的位置，默认指向第一个元素。
		private Node<AnyType> current = beginMarker.next ;
		private int expectedModCount = modCount ;
		private boolean okToRemove = false ;
		
		@Override
		public boolean hasNext() {
			return current != endMarker;
		}

		@Override
		public AnyType next() {
			//TODO : 为什么需要做这么一步判断呢？
			if(modCount == expectedModCount){
				throw new ConcurrentModificationException();
			}
			
			//TODO ：为什么需要这个判断
			if(!hasNext()){
				throw new NoSuchElementException() ;
			}
			
			AnyType data = current.data;
			current = current.next ;
			okToRemove = true ;
			return data;
		}

		@Override
		public void remove() {
			if(modCount != expectedModCount){
				throw new ConcurrentModificationException();
			}
			
			//TODO ：为什么需要这个判断
			if(!okToRemove){
				throw new IllegalStateException();
			}
			
			MyLinkedList.this.remove(current.prev);
			okToRemove = false ;
			expectedModCount++ ;
		}
	}

在上述代码当中笔者提出了三个问题，在这里笔者简单的说一下。

第一个问题：

1
2
3
if(modCount == expectedModCount){
             throw new ConcurrentModificationException();
         }

这个判断存在的必要。在遍历阶段，防止对表结构进行改变，

第二个问题：

1
2
3
if(!hasNext()){
			throw new NoSuchElementException() ;
		}

也就是我们常说的越界吧。

第三个问题

1
2
3
if(!okToRemove){
			throw new IllegalStateException();
		}

就是没有使用遍历就是调用remove方法。

2.6总体实现

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
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
package list;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 自定义LinkedList .
 * 实现选择是选用头节点和尾节点。可以极大简便很多的特殊情况，例如：删除头节点。额外的调整整个链表的头节点。
 * @author pengchengliu
 *
 */
public class MyLinkedList<AnyType> implements Iterable<AnyType>{
	
	private Node<AnyType> beginMarker ;
	private Node<AnyType> endMarker ;
	
	//TODO ：为什么会存在modCount计数器呢？
	private int theSize ;
	private int modCount ;
	
	public MyLinkedList(){
		this.clear();
	}

	/**
	 * 清空当前的容器
	 */
	public void clear() {
		beginMarker = new Node<AnyType>(null, null, null);
		endMarker = new Node<AnyType>(null, beginMarker, null);
		beginMarker.next = endMarker ;
		
		//	重置计数器。
		theSize = 0 ;
		modCount++ ;
	}
	
	/**
	 * 获取当前容器的长度。
	 * @return 当前容器的长度 。
	 */
	public int size(){
		return theSize ;
	}
	
	/**
	 * 判断当前集合是否为空
	 * @return 当前容器是否为空
	 */
	public boolean isEmpty(){
		return this.size() == 0 ;
	}
	
	/**
	 * 添加一个节点，到整个集合的最后面。
	 * @param node
	 * @return
	 */
	public boolean add(AnyType node){
		add(size(), node);
		return true ;
	}
	
	/**
	 * 添加一个一个节点，在index的位置上面添加一个元素。
	 * @param index ：
	 * @param newVaule ：
	 */
	public void add(int index, AnyType newVaule){
		addBefore(getNode(index), newVaule);
	}
	
	/**
	 * 得到集合当中的一个元素，通过索引得到集合当中的一个元素。
	 * @param index 
	 * @return
	 */
	public AnyType get(int index){
		return getNode(index).data;
	}
	
	/**
	 * 替换一个元素，替换位置在index上面的元素为newValue
	 * @param index 原有的位置
	 * @param newValue 新元素的值
	 * @return 以前index位置的元素值。
	 */
	public AnyType set(int index, AnyType newValue){
		Node<AnyType> node = getNode(index);
		AnyType oldValue = node.data;
		node.data = newValue ;
		return oldValue ;
	}
	
	/**
	 * 移除一个元素，移除index位置的元素并且把给元素返回
	 * @param index ： 指定的位置。
	 * @return ： 要移除的元素。
	 */
	public AnyType remove(int index){
		return remove(getNode(index));
	}
	
	/**
	 * 添加一个元素，将元素item添加到node之前。此方法为其他方法的服务方法，所以不需要暴露给外部类调用
	 */
	private void addBefore(Node<AnyType> node, AnyType item){
		Node<AnyType> itemNode = new Node<AnyType>(item, node.prev, node);
		itemNode.prev.next = itemNode ;
		node.prev = itemNode ;
		//更新计数器。
		theSize ++ ;
		modCount ++ ;
	}
	
	/**
	 * 移除一个元素，将oldNode在原有的集合当前删除。
	 * @param oldNode
	 * @return
	 */
	private AnyType remove(Node<AnyType> oldNode){
		oldNode.next.prev = oldNode.prev ;
		oldNode.prev.next = oldNode.next ;
		//更新计数器
		theSize-- ;
		modCount++ ;
		return oldNode.data ;
	}
	
	/**
	 * 得到一个元素，根据index下表值，得到一个元素
	 * @param index 下表值
	 * @return 得到的元素。
	 */
	private Node<AnyType> getNode(int index){
		Node<AnyType> tempNode ;
		//下标合法性验证
		if(index < 0 || index > this.size()){
			throw new IndexOutOfBoundsException();
		}
		//由于是双向列表，所以根据index的值不同在两端获取。使得效率更加的高效，O(N/2)的时间复杂度。
		if(index < this.size() / 2){
			//从开头开始找,获取第一个元素
			tempNode = beginMarker.next ;
			for(int i = 0; i < index; i ++){
				tempNode = tempNode.next ;
			}
		} else {
			//从结尾开始找,获取最后一个元素。
			tempNode = endMarker.prev ;
			for(int i = this.size(); i > index; i--){
				tempNode = tempNode.prev ;
			}
		}
		return tempNode ;
	}

	@Override
	public Iterator<AnyType> iterator() {
		return new LinkedListIterator();
	}
	
	/***
	 * LinkedList的迭代器。
	 * @author pengchengliu
	 *
	 */
	private class LinkedListIterator implements Iterator<AnyType>{

		//当前的位置，默认指向第一个元素。
		//TODO : 下面两个变量存在的意义。
		private Node<AnyType> current = beginMarker.next ;
		private int expectedModCount = modCount ;
		private boolean okToRemove = false ;
		
		@Override
		public boolean hasNext() {
			return current != endMarker;
		}

		@Override
		public AnyType next() {
			//TODO : 为什么需要做这么一步判断呢？
			if(modCount == expectedModCount){
				throw new ConcurrentModificationException();
			}
			
			//TODO ：为什么需要这个判断
			if(!hasNext()){
				throw new NoSuchElementException() ;
			}
			
			AnyType data = current.data;
			current = current.next ;
			okToRemove = true ;
			return data;
		}

		@Override
		public void remove() {
			if(modCount != expectedModCount){
				throw new ConcurrentModificationException();
			}
			
			//TODO ：为什么需要这个判断
			if(!okToRemove){
				throw new IllegalStateException();
			}
			
			MyLinkedList.this.remove(current.prev);
			okToRemove = false ;
			expectedModCount++ ;
		}
	}
	
	
	/**
	 * 节点类，用来表示链表当中的一个节点。
	 *
	 * @author pengchengliu
	 * @param <AnyType>
	 */
	//TODO : 问题一：为什么选择是private。
	//TODO : 问题二：为什么选择是static。
	private static class Node<AnyType>{
		
		//TODO ：为什么内部属性选用public 。
		private AnyType data ;
		public Node<AnyType> prev ;
		public Node<AnyType> next ;
		
		public Node(AnyType data, Node<AnyType> prev, Node<AnyType> next){
			this.data = data ;
			this.prev = prev ;
			this.next = next ;
		}
	}

}

##3、两者实现方式在效率上面的差别

我们知道了ArrayList适合读，而插入和删除还是选择LinkedList，具体的要看两者之间的差别，还是需要通过一个例子来看。

例子：删除一个List当中为偶数的元素。

1
2
3
4
5
6
7
8
public static void testDome(List<Integer> list){
	Iterator<Integer> its = list.iterator();
	while(its.hasNext()){
		if(itr.next() % 2 == 0){
			itr.remove();
		}
	}
}

如果是LinkedList，40万条数据，大概时间是0.031秒，而如果是ArrayList大概是2.5分钟，而如果是80万数据的话，LinkedList大概是0.062秒，ArrayList则是10分钟。