数据结构-02 LinkedList源码解析

时间:2021-09-09 10:17:55

本文根据Android API 21
LinkedList组成的元素是每个Link节点。所以要分析LinkedList首先要看Link。
LinkedList 内部类 Link< ET >

 private static final class Link<ET> {
ET data;

Link<ET> previous, next;

Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
previous = p;
next = n;
}
}

从这段代码中可以看出,每个link节点包含三个成员变量:

  • data:用来存储Link节点的数据
  • previous:用来指向前一个节点
  • next:用来指向下一个节点

接下来在看LinkedList
LinkedList

首先来看成员变量

size 用来记录节点的个数

transient int size = 0;

默认的头节点

transient Link<E> voidLink;

构造方法 LinkedList()

public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}

用来构造一个空的LinkedList对象
数据结构-02 LinkedList源码解析

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

构造方法中调用了addAll方法,下面看addAll()方法。
addAll(Collection< ? extends E> collection) 向LinkedList集合中添加集合

@Override
public boolean addAll(Collection<? extends E> collection) {
//要添加集合的数量
int adding = collection.size();
if (adding == 0) {
return false;
}
//如果被添加的集合的类型是LinkedList 那么elements = new ArrayList< E >();
Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;
//创建一个节点,并用头结点的previous指针指向这个节点(这里用指针来形容previous我觉得更形象)
Link<E> previous = voidLink.previous;
//遍历elements
for (E e : elements) {
//每遍历一次,就重新创建一个Link节点
Link<E> newLink = new Link<E>(e, previous, null);
previous.next = newLink;
previous = newLink;
}
previous.next = voidLink;
voidLink.previous = previous;
size += adding;
modCount++;
return true;
}

图形说明一切:

1.由于voidLink的previous指向的是自己。所以previous和voidLink表示的是同一个节点。
2.创建newLink节点,并把newLink节点的previous指针指向previous节点
3.把pevious节点的next指针指向newLink节点
数据结构-02 LinkedList源码解析

4.把newLink节点重新赋值给previous节点 2,3,4三个操作完成一次循环。

数据结构-02 LinkedList源码解析

5.经过多次循环后,最终形成了这种双向循环链表

数据结构-02 LinkedList源码解析
下面这段代码不是很理解,如果要添加的集合和自身相等,
那么 elements=new ArrayList< E >(collection)
否则 elements = collection 这是在搞什么? 我觉得这样做的目的是转成ArrayList遍历时候更快。

Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;

说到这里,LinkedList的构造方法就一目了然了。LinkedList(Collection< ? extends E> collection)方法会通过addAll()方法,将集合添加到LinkedList中。

下面继承自LinkedList爸爸的方法
继承AbstractSequentialList方法

在指定位置添加元素
1 add(int location, E object)

 @Override
public void add(int location, E object) {
//下标值必须不能为负数,且要小于节点的数量
if (location >= 0 && location <= size) {
//定义节点 并指向头结点
Link<E> link = voidLink;
//如果要插入的位置为LinkedList的前半部分
if (location < (size / 2)) {
//1 一个一个的找 直到找到下标值为location的节点 并把该节点赋给link
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {//如果要插入的位置为LinkedList的后半部分
//同上 从后往前找
for (int i = size; i > location; i--) {
link = link.previous;
}
}
//2 找到link的前一个节点previous
Link<E> previous = link.previous;
//创建newLink 并把newLink的previous指向previous,next指向link
Link<E> newLink = new Link<E>(object, previous, link);
//5 把prvious的next指向newLink
previous.next = newLink;
//6 把link的previous指向newLink
link.previous = newLink;
size++;
modCount++;
} else {
throw new IndexOutOfBoundsException();
}
}

数据结构-02 LinkedList源码解析
向LinkedList中添加集合
2 addAll(int location, Collection< ? extends E> collection)

 @Override
public boolean addAll(int location, Collection<? extends E> collection) {
if (location < 0 || location > size) {
throw new IndexOutOfBoundsException();
}
int adding = collection.size();
if (adding == 0) {
return false;
}
Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;

Link<E> previous = voidLink;
if (location < (size / 2)) {
for (int i = 0; i < location; i++) {
previous = previous.next;
}
} else {
for (int i = size; i >= location; i--) {
previous = previous.previous;
}
}
Link<E> next = previous.next;
for (E e : elements) {
Link<E> newLink = new Link<E>(e, previous, null);
previous.next = newLink;
previous = newLink;
}
previous.next = next;
next.previous = previous;
size += adding;
modCount++;
return true;
}

这个方法就像是add(Collection< ? extends E> collection)和add(int index,Object object)的结合体。首先找到要插入的位置。再遍历集合的元素,并插入到指定位置。

获取下标值为index的节点的数据
3 get(int location)

@Override
public E get(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
return link.data;
}
throw new IndexOutOfBoundsException();
}

没什么可解释的。和add(int index,E object)差不多。不同的是找到下标值为index的节点后,直接将此节点的data返回。

下个方法是 listIterator(int location) 所以先看下迭代器LinkIterator的实现
LinkIterator
LinkIterator的成员变量
pos表示当前遍历的位置,expectedModCount表示集合被操作的次数

int pos, expectedModCount;

list表示将要遍历的LinkedList

final LinkedList<ET> list;

link表示当前遍历到的节点,lastLink节点也表示当前遍历到的节点。但是必须调用next方法才会有lastLink=link.并且每次remove后,lastLink=null;

Link<ET> link, lastLink;

LinkIterator的构造方法

LinkIterator(LinkedList<ET> object, int location) {
//把需要遍历的LinkedList赋给成员变量list
list = object;
//被操作的次数
expectedModCount = list.modCount;
//判断开始遍历的位置是否是非负数,并在集合长度的范围内
if (location >= 0 && location <= list.size) {
// pos ends up as -1 if list is empty, it ranges from -1 to
// list.size - 1
// if link == voidLink then pos must == -1
link = list.voidLink;
//如果开始遍历的位置在集合前半部分
if (location < list.size / 2) {
//从头结点开始遍历 遍历找到下标为location的节点
for (pos = -1; pos + 1 < location; pos++) {
link = link.next;
}
} else {//从头结点向后遍历,找到下标为location的节点
for (pos = list.size; pos >= location; pos--) {
link = link.previous;
}
}
} else {
throw new IndexOutOfBoundsException();
}
}

添加一个元素
1 add(ET object)
此方法和LinkedList的方法基本一样,插入的位置是下表为location的下一个节点。首先找到将要被插入位置的及诶单

public void add(ET object) {
if (expectedModCount == list.modCount) {
//被添加节点下一个节点
Link<ET> next = link.next;
//被插入的新节点位于link的下个节点,next的前一个节点。
Link<ET> newLink = new Link<ET>(object, link, next);
//给
link.next = newLink;
next.previous = newLink;
//给插入节点的位置重新赋值
link = newLink;
lastLink = null;
pos++;
expectedModCount++;
//结合节点数加1
list.size++;
list.modCount++;
} else {
throw new ConcurrentModificationException();
}
}

不明白这段的含义
if (expectedModCount == list.modCount)

从前往后遍历时,判断是否还有下一个节点
2 hasNext()

public boolean hasNext() {
return link.next != list.voidLink;
}

从后往前遍历时,判断是否还有前一个节点
3 hasPrevious()

public boolean hasPrevious() {
return link != list.voidLink;
}

返回遍历到的当前节点的下一个节点的data属性。即返回节点的数据。
4 next()

public ET next() {
if (expectedModCount == list.modCount) {
LinkedList.Link<ET> next = link.next;
if (next != list.voidLink) {
lastLink = link = next;
pos++;
return link.data;
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}

返回遍历到的当前节点的下一个节点的下标值。
5 nextIndex()

public int nextIndex() {
return pos + 1;
}

返回当前节点的前一个节点的data属性。和next()方法基本一样,只是遍历的方向相反。
6 previous()

 public ET previous() {
if (expectedModCount == list.modCount) {
if (link != list.voidLink) {
lastLink = link;
link = link.previous;
pos--;
return lastLink.data;
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}

返回当前遍历节点的前一个节点的下标值。
7 previousIndex()

public int previousIndex() {
return pos;
}

移除当前遍历的节点
8 remove()

 public void remove() {
if (expectedModCount == list.modCount) {
if (lastLink != null) {
Link<ET> next = lastLink.next;
Link<ET> previous = lastLink.previous;
next.previous = previous;
previous.next = next;
if (lastLink == link) {
pos--;
}
link = previous;
lastLink = null;
expectedModCount++;
list.size--;
list.modCount++;
} else {
throw new IllegalStateException();
}
} else {
throw new ConcurrentModificationException();
}
}

重新给当前节点的数据赋值
9 set(ET object)

public void set(ET object) {
if (expectedModCount == list.modCount) {
if (lastLink != null) {
lastLink.data = object;
} else {
throw new IllegalStateException();
}
} else {
throw new ConcurrentModificationException();
}
}

接着继承自AbstractSequentialList的方法。

返回当前集合的迭代器。并且迭代器从location开始遍历
4 listIterator(int location)

@Override
public ListIterator<E> listIterator(int location) {
return new LinkIterator<E>(this, location);
}

移除下标为location的节点。
5 remove(int location)

 @Override
public E remove(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}

执行过程为:

  • 先找到需要移除的节点link
  • 再分别找到将被移除的节点link的前一个节点和后一个节点
  • 在把link的前一个节点的next指针指向link的后一个节点。把link的后一个节点的previous指针指向link的前一个节点

    将下标值为location的节点的data属性替换成object
    6 set(int location, E object)

@Override
public E set(int location, E object) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
E result = link.data;
link.data = object;
return result;
}
throw new IndexOutOfBoundsException();
}

下面继承自LinkedList爷爷的方法
继承自AbstractList的方法

把新节点添加到末尾
1 add(E object)

@Override
public boolean add(E object) {
return addLastImpl(object);
}

清空所有节点
2 clear()

@Override
public void clear() {
if (size > 0) {
size = 0;
voidLink.next = voidLink;
voidLink.previous = voidLink;
modCount++;
}
}

找到节点的data和object相等的节点的下标值
3 indexOf(Object object)

  @Overrid
public int indexOf(Object object) {
int pos = 0;
Link<E> link = voidLink.next;
if (object != null) {
while (link != voidLink) {
if (object.equals(link.data)) {
return pos;
}
link = link.next;
pos++;
}
} else {
while (link != voidLink) {
if (link.data == null) {
return pos;
}
link = link.next;
pos++;
}
}
return -1;
}

从上述代码可以看出,如果要找的data不是空,那么就从前往后找到第一个data符合的下标值.如果是空,也是从前往后,找到第一个data为空的节点的下标值。

从后往前找到LinkedList中第一个节点中的data和object相等的节点下标值。和前一个indexOf()方法找的方向正相反。
4 lastIndexOf(Object object)

 @Override
public int lastIndexOf(Object object) {
int pos = size;
Link<E> link = voidLink.previous;
if (object != null) {
while (link != voidLink) {
pos--;
if (object.equals(link.data)) {
return pos;
}
link = link.previous;
}
} else {
while (link != voidLink) {
pos--;
if (link.data == null) {
return pos;
}
link = link.previous;
}
}
return -1;
}

下面继承自LinkedList祖爷爷的方法
继承自AbstractCollection< E>的方法

在LinkedList的构造方法中曾经调用过这个方法。不再解释。
1 addAll(Collection< ? extends E> collection)

@Override
public boolean addAll(Collection<? extends E> collection) {
int adding = collection.size();
if (adding == 0) {
return false;
}
Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;

Link<E> previous = voidLink.previous;
for (E e : elements) {
Link<E> newLink = new Link<E>(e, previous, null);
previous.next = newLink;
previous = newLink;
}
previous.next = voidLink;
voidLink.previous = previous;
size += adding;
modCount++;
return true;
}

判断集合的节点中是否有包含object的节点
2 contains(Object object)

@Override
public boolean contains(Object object) {
Link<E> link = voidLink.next;
if (object != null) {
while (link != voidLink) {
if (object.equals(link.data)) {
return true;
}
link = link.next;
}
} else {
while (link != voidLink) {
if (link.data == null) {
return true;
}
link = link.next;
}
}
return false;
}

从前往后找到节点的data和object相等的节点

移除集合中节点的数据和object相等的节点
3 remove(Object object)

@Override
public boolean remove(Object object) {
return removeFirstOccurrenceImpl(object);
}

返回LinkedList集合的长度
4 size()

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

把集合转成数组
5 toArray()

@Override
public Object[] toArray() {
int index = 0;
Object[] contents = new Object[size];
Link<E> link = voidLink.next;
while (link != voidLink) {
contents[index++] = link.data;
link = link.next;
}
return contents;
}

遍历Linked集合,并把集合的每个数据添加到一个数组中。

把集合转成指定的数组
6 toArray(T[] contents)

 @Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] contents) {
int index = 0;
//如果指定的数组比集合的长度小
if (size > contents.length) {
//获取创建数组的类型
Class<?> ct = contents.getClass().getComponentType();
//重新创建一个和集合的长度同样大数组
contents = (T[]) Array.newInstance(ct, size);
}
Link<E> link = voidLink.next;
//遍历集合的元素,并添加到数组中
while (link != voidLink) {
contents[index++] = (T) link.data;
link = link.next;
}
//(应该有index==contents.length) 这里表示指定的数组比集合长度大 把数组被遍历赋值的最后的一个元素后的第一个元素置为空。
if (index < contents.length) {
contents[index] = null;
}
return contents;
}

不明白这里为啥要置空
contents[index] = null;
/**
* Returns an array containing all elements contained in this
* {@code LinkedList}. If the specified array is large enough to hold the
* elements, the specified array is used, otherwise an array of the same
* type is created. If the specified array is used and is larger than this
* {@code LinkedList}, the array element following the collection elements
* is set to null.
*
* @param contents
* the array.
* @return an array of the elements from this {@code LinkedList}.
* @throws ArrayStoreException
* if the type of an element in this {@code LinkedList} cannot
* be stored in the type of the specified array.
*/
这是官方的注释,我自己翻译后的意思是:
返回一个数组,这个数组包含LinkedList的所有元素。如果传入的指定数组比集合的数组大。那么这个指定的数组将被使用,否则的话,将会创建一个和指定数组类型一样的数组。如果指定的数组被使用,并且比LinkedList的长度大,那么这个数组被添加的集合元素后的元素将被置空。

下面实现Deque接口的方法
实现 Deque 的方法

把新节点插入到集合的头部,其data为object.
1 addFirst(E object)

public void addFirst(E object) {
addFirstImpl(object);
}

把新节点插入到集合的头部,其data为object.
2 addLast(E object)

public void addLast(E object) {
addLastImpl(object);
}

返回集合的第一个节点的data
3 getFirstImpl()

private E getFirstImpl() {
Link<E> first = voidLink.next;
if (first != voidLink) {
return first.data;
}
throw new NoSuchElementException();
}

返回集合的最后一个节点的data
4 getLast()

public E getLast() {
Link<E> last = voidLink.previous;
if (last != voidLink) {
return last.data;
}
throw new NoSuchElementException();
}

移除集合的第一个节点,并返回该节点的data
5 removeFirst()

public E removeFirst() {
return removeFirstImpl();
}
private E removeFirstImpl() {
Link<E> first = voidLink.next;
if (first != voidLink) {
Link<E> next = first.next;
voidLink.next = next;
next.previous = voidLink;
size--;
modCount++;
return first.data;
}
throw new NoSuchElementException();
}

移除头节点的前一个节点,并返回该节点的data
6 removeLast()

public E removeLast() {
return removeLastImpl();
}
private E removeLastImpl() {
Link<E> last = voidLink.previous;
if (last != voidLink) {
Link<E> previous = last.previous;
voidLink.previous = previous;
previous.next = voidLink;
size--;
modCount++;
return last.data;
}
throw new NoSuchElementException();
}

这里的ReverseLinkIterator和之前的LinkIterator一样,只是迭代的方向是相反的。
获得一个反向迭代器的实例
7 descendingIterator()

public Iterator<E> descendingIterator() {
return new ReverseLinkIterator<E>(this);
}

8 offerFirst(E e)

public boolean offerFirst(E e) {
return addFirstImpl(e);
}
private boolean addFirstImpl(E object) {
Link<E> oldFirst = voidLink.next;
Link<E> newLink = new Link<E>(object, voidLink, oldFirst);
voidLink.next = newLink;
oldFirst.previous = newLink;
size++;
modCount++;
return true;
}

8 offerLast(E e)

 public boolean offerLast(E e) {
return addLastImpl(e);
}
private boolean addLastImpl(E object) {
Link<E> oldLast = voidLink.previous;
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
voidLink.previous = newLink;
oldLast.next = newLink;
size++;
modCount++;
return true;
}

返回第一个节点的数据,如果是空集合,返回null
9 peekFirst(E e)

public E peekFirst() {
return peekFirstImpl();
}
private E peekFirstImpl() {
Link<E> first = voidLink.next;
return first == voidLink ? null : first.data;
}

返回集合的最后一个节点的数据,如果是空集合,返回null
9 peekLast

public E peekLast() {
Link<E> last = voidLink.previous;
return (last == voidLink) ? null : last.data;
}

返回第一个节点的数据,如果是空集合,返回null.并把第一个节点移出集合
10 pollFirst()

 public E pollFirst() {
return (size == 0) ? null : removeFirstImpl();
}

返回最后一个节点的数据,如果是空集合,返回null.并把最后一个节点移出集合
11 pollFirst()

public E pollLast() {
return (size == 0) ? null : removeLastImpl();
}

和pollFirst()一样,不同的是如果集合为空,这里会抛异常,而不是返回一个null
12 pop()

public E pop() {
return removeFirstImpl();
}

添加一个节点到集合的头部
12 push()

public void push(E e) {
addFirstImpl(e);
}

移除第一个不为null的节点
13 removeFirstOccurrence(Object o)

public boolean removeFirstOccurrence(Object o) {
return removeFirstOccurrenceImpl(o);
}
private boolean removeFirstOccurrenceImpl(Object o) {
Iterator<E> iter = new LinkIterator<E>(this, 0);
return removeOneOccurrence(o, iter);
}
private boolean removeOneOccurrence(Object o, Iterator<E> iter) {
while (iter.hasNext()) {
E element = iter.next();
if (o == null ? element == null : o.equals(element)) {
iter.remove();
return true;
}
}
return false;
}

移除最后一个不为null的节点
14 removeLastOccurrence(Object o)

public boolean removeLastOccurrence(Object o) {
Iterator<E> iter = new ReverseLinkIterator<E>(this);
return removeOneOccurrence(o, iter);
}

在集合的尾部增加一个节点
15 offer(E o)

public boolean offer(E o) {
return addLastImpl(o);
}

移除第一个元素并返回 如果集合元素为空,返回null
16 poll()

public E poll() {
return size == 0 ? null : removeFirst();
}

移除第一个节点
17 remove()

public E remove() {
return removeFirstImpl();
}

返回第一个节点的data,如果集合为空,返回null
18 peek()

public E peek() {
return peekFirstImpl();
}

返回第一个节点 要讲求集合不能为空,否则会报异常
19 element()

public E element() {
return getFirstImpl();
}

总结:

  • LinkedList是一种线性的双向回环的链表结构。
  • 相对于ArrayList,LinkedList的删除效率较高,因为通过指针的改变来实现。查找效率较慢。因为LinkedList的存储位置不是连续的。