郑加威

# 数据结构

## 继承关系

``````java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.AbstractSequentialList<E>
``````

## 实现接口

``Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>``

## 基本属性

``````transient int size = 0;     //LinkedList中存放的元素个数
transient Node<E> first;    //头节点
transient Node<E> last;     //尾节点``````

## 什么是链表

链表是由一系列非连续的节点组成的存储结构，简单分下类的话，链表又分为单向链表和双向链表，而单向/双向链表又可以分为循环链表和非循环链表，下面简单就这四种链表进行图解说明。

### 1.单向链表

单向链表就是通过每个结点的指针指向下一个结点从而链接起来的结构，最后一个节点的next指向null。

# 源码解析

``````public class LinkedList<E>extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

transient int size = 0;   //LinkedList中存放的元素个数

transient Node<E> first;  //头节点

transient Node<E> last;   //尾节点

//构造方法，创建一个空的列表
}

public LinkedList(Collection<? extends E> c) {
this();
}

//插入头节点
final Node<E> f = first;  //将头节点赋值给f节点
//new 一个新的节点，此节点的data = e , pre = null , next - > f
final Node<E> newNode = new Node<>(null, e, f);
first = newNode; //将新创建的节点地址复制给first
if (f == null)  //f == null，表示此时LinkedList为空
last = newNode;  //将新创建的节点赋值给last
else
f.prev = newNode;  //否则f.前驱指向newNode
size++;
modCount++;
}

//插入尾节点
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节点前插入e节点，并修改各个节点之间的前驱后继
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)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

//删除头节点
// 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;
}

//删除尾节点
// 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;
}

//删除指定节点
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;  //获取指定节点的前驱
final Node<E> prev = x.prev;  //获取指定节点的后继

if (prev == null) {
first = next;   //如果前驱为null, 说明此节点为头节点
} else {
prev.next = next;  //前驱结点的后继节点指向当前节点的后继节点
x.prev = null;     //当前节点的前驱置空
}

if (next == null) {    //如果当前节点的后继节点为null ,说明此节点为尾节点
last = prev;
} else {
next.prev = prev;  //当前节点的后继节点的前驱指向当前节点的前驱节点
x.next = null;     //当前节点的后继置空
}

x.item = null;     //当前节点的元素设置为null ,等待垃圾回收
size--;
modCount++;
return element;
}

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 E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
}

//删除尾节点
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
}

}

}

public boolean contains(Object o) {
return indexOf(o) != -1;
}

//返回List中元素的数量
public int size() {
return size;
}

return true;
}

//删除指定的元素
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
return true;
}
}
}
return false;
}

//将集合中的元素添加到List中
public boolean addAll(Collection<? extends E> c) {
}

//将集合中的元素全部插入到List中，并从指定的位置开始
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);

Object[] a = c.toArray();  //将集合转化为数组
int numNew = a.length;  //获取集合中元素的数量
if (numNew == 0)   //集合中没有元素，返回false
return false;

Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index); //获取位置为index的结点元素，并赋值给succ
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;
}

//删除List中所有的元素
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 get(int index) {
checkElementIndex(index);
return node(index).item;
}

//将节点防止在指定的位置
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}

//将节点放置在指定的位置
public void add(int index, E element) {
checkPositionIndex(index);

if (index == size)
else
}

//删除指定位置的元素
public E remove(int index) {
checkElementIndex(index);
}

//判断索引是否合法
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));
}

//返回指定位置的节点信息
//为了提高效率，当前位置首先和元素数量的中间位置开始判断，小于中间位置，
//从头节点开始遍历，大于中间位置从尾节点开始遍历
Node<E> node(int index) {
// assert isElementIndex(index);

if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

//返回第一次出现指定元素的位置
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;
}

//返回最后一次出现元素的位置
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;
}

//弹出第一个元素的值
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) {
}

//添加到头部
public boolean offerFirst(E e) {
return true;
}

//插入到最后一个元素
public boolean offerLast(E 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);
}

//如队列，添加到头部
public void push(E e) {
}

//出队列删除第一个节点
public E pop() {
return removeFirst();
}

//删除指定元素第一次出现的位置
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}

//删除指定元素最后一次出现的位置
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
return true;
}
}
}
return false;
}

//遍历方法
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
//内部类，实现ListIterator接口
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned = null;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;

ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}

public boolean hasNext() {
return nextIndex < size;
}

public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();

lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}

public boolean hasPrevious() {
return nextIndex > 0;
}

public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();

lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}

public int nextIndex() {
return nextIndex;
}

public int previousIndex() {
return nextIndex - 1;
}

public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();

Node<E> lastNext = lastReturned.next;
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}

public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}

checkForComodification();
lastReturned = null;
if (next == null)
else
nextIndex++;
expectedModCount++;
}

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
//静态内部类，创建节点
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;
}
}

/**
* @since 1.6
*/
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}

/**
* Adapter to provide descending iterators via ListItr.previous
*/
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}

@SuppressWarnings("unchecked")
try {
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}

/**
* Returns a shallow copy of this {@code LinkedList}. (The elements
* themselves are not cloned.)
*
* @return a shallow copy of this {@code LinkedList} instance
*/
public Object clone() {

// 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)

return clone;
}

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

private static final long serialVersionUID = 876323262645176354L;

//将对象写入到输出流中
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);
}

//从输入流中将对象读出
@SuppressWarnings("unchecked")
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic

// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
}
}
``````

# 重要方法解析

## 构造方法

``````LinkedList()

## 添加方法

``````public boolean add(E e) {
return true;
}
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++;
}
``````

## 删除方法

``````public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
return true;
}
}
}
return false;
}
``````

# 总结

• LinkedList在1.8版本有添加了一点新的内容，添加了一个static final 修饰的内部类LLSpliterator 并实现了Spliterator ，为了实现并行遍历而新添加的功能，整体的变化并不是很大，感兴趣的可以自己去看一下。

# List实现类的使用场景

• 如果有多个线程需要同时访问List集合中的元素，开发者可以考虑使用Collections将集合包装成线程安全的集合。

# 补充说明

5. 注意源码中的Entry<E> entry(int index)方法。该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置出的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。源码中先将index与长度size的一半比较，如果index<size/2，就只从位置0往后遍历到位置index处，而如果index>size/2，就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历，从而提高一定的效率（实际上效率还是很低）。
6. 注意链表类对应的数据结构Entry
8. 要注意源码中还实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用。

### 评论(1)

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++;
}

Java Connection集合分析之List

Java Connection集合家庭分析 Java集合大致可以分为Set、List、Queue和Map四种体系，其中Set代表无序、不可重复的集合；List代表有序、重复的集合；而Map则代表具有映射关系的集合，Java 5 ...

11/14
0
0
Java核心（四）你不知道的数据集合

11/28
0
0
【转】115个Java面试题和答案——终极列表

2014/09/30
0
0
115个Java面试题和答案——终极列表（上）

LCZ777
2014/04/23
0
0
java.util包中集合详解

jacksu在简书
01/25
0
0

spark安装测试

-九天-
18分钟前
2
0

max佩恩
38分钟前
7
0
mybatis批量update操作的写法，及批量update报错的问题解决方法

mybatis的批量update操作写法很简单，如下： 如果想学习Java工程化、高性能及分布式、深入浅出。微服务、Spring，MyBatis，Netty源码分析的朋友可以加我的Java高级交流：854630135，群里有阿...

16
0
EOS怎样删除钱包

11
0
Java语言快速实现简单MQ消息队列服务

12
0