继承关系
LinkedList继承关系
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
1
2
3
AbstractSequentialList继承关系
public abstract class AbstractSequentialList<E> extends AbstractList<E>
1
AbstractList继承关系
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>
1
AbstractCollection继承关系
public abstract class AbstractCollection<E> implements Collection<E>
1
List继承关系
public interface List<E> extends Collection<E>
1
Deque继承关系
public interface Deque<E> extends Queue<E>
1
Queue继承关系
public interface Queue<E> extends Collection<E>
1
Collection继承关系
public interface Collection<E> extends Iterable<E>
1
相关接口和类
Iterable接口：实现该接口的类就可以使用for (Suit suit : suits)来遍历
Collection接口：集合类的根接口
AbstractCollection类：提供Collection接口的基础实现，最大限度地减少实现此接口所需的工作量
List接口：有序集合、允许重复元素、允许空元素、控制元素的插入位置、通过索引访问元素、在列表里搜索元素。扩展了Collection接口，添加一些额外方法
AbstractList类：提供List接口的基础实现，以最大限度地减少随机访问列表(数组)实现此接口所需的工作量
AbstractSequentialList类：提供List的基础实现，以最大限度地减少顺序访问(链表)实现此接口所需的工作量，get、set、add和remove操作都是基于listIterator来操作的
Queue接口：通常是一个先进先出的一组集合
Deque接口：双端队列，支持两端插入和移出元素
Cloneable接口：可以调用clone方法进行对象的克隆
Serializable接口：可序列化
关于LinkedList
双向链表
不是线程安全的
iterator() 和 listIterator() 支持快速失败机制
字段
fields
父类AbstractList：
// 列表在结构上被改变的次数，结构改变是指列表大小改变或以其他方式的改变，可能使得正在进行的迭代产生不正确的结果
protected transient int modCount = 0;
子类ArrayList：
private static final long serialVersionUID = 876323262645176354L;
// 链表的大小
transient int size = 0;
// 指向头结点
// 保证：(first == null && last == null) || (first.prev == null && first.item != null)
transient Node<E> first;
// 指向尾节点
// 保证：(first == null && last == null) || (last.next == null && last.item != null)
transient Node<E> last;
LinkedList的数据结构，节点类：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
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
构造函数
constructors
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c); // 后面会介绍
}
1
2
3
4
5
6
7
相关方法
增删改查
link(add)
// 在头节点前插入元素
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f); // 构建新节点
first = newNode;
if (f == null) // 第一次插入节点
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
// 在尾节点后插入元素
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null); // 构建新节点
last = newNode;
if (l == null) // 第一次插入节点
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
// 在succ点后前插入元素
// 调用此方法时应该保证succ不为空
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null) // 如果succ是头结点
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
// 头结点前插入元素
public void addFirst(E e) {
linkFirst(e);
}
// 尾结点后插入元素
public void addLast(E e) {
linkLast(e);
}
// 尾结点后插入元素
public boolean add(E e) {
linkLast(e);
return true;
}
// 将集合插入到链表的尾部
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
// 检查是否越界
// 将集合插入到index位置
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null); // 构造新节点
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
// 在指定位置插入元素
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
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
unlink(remove)
// 删除头结点，并返回头结点的值
// 调用此方法时应该保证f执行头结点，并且头结点不为空
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null) // 只有一个节点的时候
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
// 删除尾结点，并返回尾结点的值
// 调用此方法时应该保证l执行尾结点，并且尾结点不为空
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null) // 只有一个节点的时候
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
// 删除节点x，并返回接单x的值
// 调用此方法时应该保证x不为空
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) { // 如果x为头结点
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) { // 如果x为尾结点
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
// 删除头结点
// 结点为空时抛错
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// 删除尾结点
// 结点为空时抛错
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
// 删除元素o
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) { // 链表访问也可以用for，以前都是用while，搞的一团糟
if (x.item == null) {
unlink(x); // 调用删除节点的函数，高手总是能把一个大问题分割成一个个很小很小的问题，然后就可以放心重复的调用
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
// 清空，遍历一遍是为了让虚拟机更好的回收内存
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
// 删除指定位置的元素
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
// 删除第一次出现value为o的元素
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
// 删除最后一次出现value为o的元素
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
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
get
// 得到头结点
// 结点为空时抛错
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
// 得到尾结点
// 结点为空时抛错
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
// 是否包含此元素
public boolean contains(Object o) {
return indexOf(o) != -1;
}
// 返回size
public int size() {
return size;
}
// 根据位置得到value
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
// 根据索引检索节点
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) { // 如果index在前半部分
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // 如果index在后半部分
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
// 根据valu检索第一次出现的位置
// 跟remove(Object)很类似
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
// 根据valu检索最后一次出现的位置
// 跟remove(Object)很类似
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
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
set
// 设置位置index上的value
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
1
2
3
4
5
6
7
8
越界判断
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Queue、Stack和Deque
Queue
// 返回头结点
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
// 返回头结点，如果头结点为空，抛错误
public E element() {
return getFirst();
}
// 返回头结点，并删除头结点
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
// 返回头结点，并删除头结点，头结点为空则抛错误
public E remove() {
return removeFirst();
}
// 尾节点后插入新元素
public boolean offer(E e) {
return add(e);
}
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
Stack
// 在头结点前插入
public void push(E e) {
addFirst(e);
}
// 返回头结点，并删除头结点，头结点为空则抛错误
public E pop() {
return removeFirst();
}
1
2
3
4
5
6
7
8
9
Deque
// 在头结点后插入
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
// 在尾结点后插入
public boolean offerLast(E e) {
addLast(e);
return true;
}
// 返回头结点
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
// 返回尾结点
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
// 返回头结点，并删除头结点
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
// 返回尾结点，并删除尾结点
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
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
toArray和iterator
toArray
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
iterator
// 调用父类AbstractSequentialList的iterator函数
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
// 逆序的iterator
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
ListItr和DescendingIterator都是LinkedList的私有内部类，继承结构如下：
private class ListItr implements ListIterator<E>
private class DescendingIterator implements Iterator<E>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
clone和序列化
clone
@SuppressWarnings("unchecked")
private LinkedList<E> superClone() {
try {
return (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
public Object clone() {
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
serialize
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in size
int size = s.readInt();
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}
---------------------
转载，仅作分享，侵删
作者：EagleLi1
原文：https://blog.csdn.net/qq_21687635/article/details/85067683
|
|
收藏
淘帖
踩
奈斯
