链表

发表于 | 分类于 | 阅读次数:
字数统计: 1.7k | 阅读时长 ≈ 9

LinkedList是用链表结构存储数据的，很适合数据的动态插入和删除，而随机访问和遍历的速度则较慢。另外，它还提供了List接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。

链表LinkedList

由于ArrayList是用数组实现的，所以 get(int index) 和 set(int index, E e) 方法可以通过下标访问和修改元素，也可以用 add(E e) 方法在线性表末尾添加元素，它们是高效的。但是 add(int index, E e) 和 remove(int index) 方法的效率很低，因为需要移动潜在的大量元素。
为了提高在表中开始位置添加和删除元素的效率，可以采用链式结构来实现线性表。

节点

每个节点都包含元素和一个名为next的数据域，next指向下一个元素。如果节点是线性表中的最后一个，那么它的指针数据域next所包含的值是null。

LinkedList节点类
1
2
3
4
5
6
7
8
9
10
    // This class is only used in LinkedList, so it is private.
	// This class does not need to access any
	// instance members of LinkedList, so it is defined static.
private static class Node<E> {
	E element;
	Node<E> next;
	public Node(E element) {
		this.element = element;
	}
}

实现addFirst(E e)方法

addFirst(E e)方法
1
2
3
4
5
6
7
8
public void addFirst(E e) {
	Node<E> newNode = new Node<>(e);
	newNode.next = head;
	head = newNode;
	size++;
	if (tail == null)
		tail = head;
}

实现addLast(E e)方法

addLast(E e)方法
1
2
3
4
5
6
7
8
9
10
public void addLast(E e) {
	Node<E> newNode = new Node<>(e);
	if (tail == null) {
		head = tail = newNode;
	} else {
		tail.next = newNode;
		tail = tail.next;
	}
	size++;
}

实现add(int index, E e)方法

add(int index, E e)方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void add(int index, E e) {
	if (index == 0) {
		//addFirst && addLast contains size++
		addFirst(e);
	} else if (index >= size) {
		addLast(e);
	} else {
		Node<E> current = head;
		for (int i = 1; i < index; i++) {
			current = current.next;
		}
		Node<E> tmp = current.next;
		current.next = new Node<>(e);
		(current.next).next = tmp;
		size++;
	}
}

实现removeFirst()方法

removeFirst()方法
1
2
3
4
5
6
7
8
9
10
public E removeFirst() {
	if (size == 0) {
		return null;
	} else {
		Node<E> tmp = head;
		head = head.next;
		size--;
		return tmp.element;
	}
}

实现removeLast()方法

removeLast()方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public E removeLast() {
	if (size == 0) {
		return null;
	} else if (size == 1) {
		Node<E> tmp = head;
		head = tail = null;
		size = 0;
		return tmp.element;
	} else {
		Node<E> current = head;
		for (int i = 0; i < size - 2; i++) 
			current = current.next;
		Node<E> tmp = tail;
		tail.next = null;
		size--;
		return tmp.element;
	}
}

实现remove(int index)方法

remove(int index)方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public E remove(int index) {
		if (index < 0 || index >= size) {
			return null;
		} else if (index == 0) {
			return removeFirst();
		} else if (index == size -1) {
			return removeLast();
		} else {
			Node<E> previous = head;
			for (int i = 1; i < index; i++)
				previous = previous.next;
			Node<E> current = previous.next;
			previous.next = current.next;
			size--;
			return current.element;
		}
	}

MyLinkedList具体实现

MyLinkedList具体实现
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
241
242
243
244
245
246
247

import java.util.Iterator;

public class MyLinkedList<E> extends MyAbstractList<E> {
	private Node<E> head, tail;
	
	public MyLinkedList() {
		
	}
	public MyLinkedList(E[] objects) {
		super(objects);
	}
	
	public E getFirst() {
		if (size == 0) {
			return null;
		} else {
			return head.element;
		}
	}
	public E getLast() {
		if (size == 0) {
			return null;
		} else {
			return tail.element;
		}
	}
	
	public void addFirst(E e) {
		Node<E> newNode = new Node<>(e);
		newNode.next = head;
		head = newNode;
		size++;
		if (tail == null)
			tail = head;
	}
	public void addLast(E e) {
		Node<E> newNode = new Node<>(e);
		if (tail == null) {
			head = tail = newNode;
		} else {
			tail.next = newNode;
			tail = tail.next;
		}
		size++;
	}
	@Override
	public void add(int index, E e) {
		if (index == 0) {
			//addFirst && addLast contains size++
			addFirst(e);
		} else if (index >= size) {
			addLast(e);
		} else {
			Node<E> current = head;
			for (int i = 1; i < index; i++) {
				current = current.next;
			}
			Node<E> tmp = current.next;
			current.next = new Node<>(e);
			(current.next).next = tmp;
			size++;
		}
	}

	@Override
	public void clear() {
		size = 0;
		head = tail = null;
	}

	@Override
	public boolean contains(E e) {
		if (size == 0) {
			return false;
		} else {
			Node<E> current = head;
			while (current != null) {
				if (current.element == e)
					return true;
				current = current.next;
			}
		}
		return false;
	}

	@Override
	public E get(int index) {
		if (index < 0 || index >= size) {
			return null;
		} else if (index == 0) {
			return getFirst();
		} else if (index == size -1) {
			return getLast();
		} else {
			Node<E> current = head.next;
			for (int i = 1; i < index; i++)
				current = current.next;
			return current.element;
		}
	}

	@Override
	public int indexOf(E e) {
		if (head.element == e) {
			return 0;
		} else if (tail.element == e) {
			return size - 1;
		} else {
			Node<E> current = head.next;
			int index = 1;
			while (current != null) {
				if (current.element == e)
					return index;
				current = current.next;
				index++;
			}
		}
		return -1;
	}

	@Override
	public int lastIndexOf(E e) {
		int index = -1;
		Node<E> current = head;
		for (int i = 0; i < size; i++) {
			if (current.element == e)
				index = i;
			current = current.next;
		}
		return index;
	}
	
	public E removeFirst() {
		if (size == 0) {
			return null;
		} else {
			Node<E> tmp = head;
			head = head.next;
			size--;
			return tmp.element;
		}
	}	
	public E removeLast() {
		if (size == 0) {
			return null;
		} else if (size == 1) {
			Node<E> tmp = head;
			head = tail = null;
			size = 0;
			return tmp.element;
		} else {
			Node<E> current = head;
			for (int i = 0; i < size - 2; i++) 
				current = current.next;
			Node<E> tmp = tail;
			tail.next = null;
			size--;
			return tmp.element;
		}
	}	
	@Override
	public E remove(int index) {
		if (index < 0 || index >= size) {
			return null;
		} else if (index == 0) {
			return removeFirst();
		} else if (index == size -1) {
			return removeLast();
		} else {
			Node<E> previous = head;
			for (int i = 1; i < index; i++)
				previous = previous.next;
			Node<E> current = previous.next;
			previous.next = current.next;
			size--;
			return current.element;
		}
	}

	@Override
	public E set(int index, E e) {
		if (index < 0 || index > size -1) {
			return null;
		} else {
			Node<E> current = head;
			for (int i = 0; i < index; i++)
				current = current.next;
			
			current.element = e;
			return current.element;
		}
	}
	
	@Override
	public String toString() {
		StringBuilder res = new StringBuilder("[");
		Node<E> current = head;
		for (int i = 0; i < size; i++) {
			res.append(current.element);
			current = current.next;
			if (current != null) {
				res.append(", ");
			} else {
				res.append("]");
			}
		}
		return res.toString();
	}
	
	@Override
	public Iterator<E> iterator() {
		return new LinkedListIterator();
	}
	private class LinkedListIterator implements Iterator<E> {
		private Node<E> current = head;

		@Override
		public boolean hasNext() {
			return (current != null);
		}

		@Override
		public E next() {
			E e = current.element;
			current = current.next;
			return e;
		}
		@Override
		public void remove() {
			
		}
		
	}	
	
	// This class is only used in LinkedList, so it is private.
	// This class does not need to access any
	// instance members of LinkedList, so it is defined static.
	private static class Node<E> {
		E element;
		Node<E> next;
		public Node(E element) {
			this.element = element;
		}
	}

}

抽象类和接口

MyList接口

MyList接口
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
public interface MyList<E> extends Iterable<E> {
	void add(E e);
	
	void add(int index, E e);
	
	void clear();
	
	boolean contains(E e);
	
	E get(int index);
	
	int indexOf(E e);
	
	boolean isEmpty();
	
	int lastIndexOf(E e);
	
	boolean remove(E e);
	
	E remove(int index);
	
	Object set(int index, E e);
	
	int size();	
}

MyAbstractList抽象类

MyAbstractList抽象类
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
public abstract class MyAbstractList<E> implements MyList<E> {	
	protected int size = 0 ;
	
	protected MyAbstractList() {
		
	};	
	protected MyAbstractList(E[] objects) {
		for (int i = 0; i < objects.length; i++)
			add(objects[i]);
	}
	
	@Override
	public void add(E e) {
		add(size, e);
	}
	
	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public boolean remove(E e) {
		if (indexOf(e) >= 0) {
			remove(indexOf(e));
			return true;
		} else {
			return false;
		}
	}	

	@Override
	public int size() {
		return size;
	}
}
0%