JDK 源码分析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public interface Iterator<E> {

    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    /**
     * @since 1.8
     */
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

1
2
3
4
5
6
public interface Enumeration<E> {

    boolean hasMoreElements();

    E nextElement();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public interface Iterable<T> {

    Iterator<T> iterator();

    /**
     * @since 1.8
     */
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    /**
     * @since 1.8
     */
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public interface ListIterator<E> extends Iterator<E> {
    // Query Operations

    boolean hasNext();

    E next();

    boolean hasPrevious();

    E previous();

    int nextIndex();

    int previousIndex();


    // Modification Operations

    void remove();

    void set(E e);

    void add(E 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
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
/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // defend against c.toArray (incorrectly) not returning Object[]
        // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

 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
package com.diguage.truman;

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Objects;

/**
 * @author D瓜哥, https://www.diguage.com/
 * @since 2020-03-03 11:10
 */
public class ArrayListBaseTest {
    /**
     * 通过反射查看 {@link ArrayList} 的内部属性
     */
    public void xray(ArrayList list) {
        Class clazz = list.getClass();
        try {
            Field elementData = clazz.getDeclaredField("elementData");
            elementData.setAccessible(true);
            Object[] objects = (Object[]) elementData.get(list);
            Field sizeField = clazz.getDeclaredField("size");
            sizeField.setAccessible(true);

            int size = 0;
            for (int i = 0; i < objects.length; i++) {
                if (Objects.nonNull(objects[i])) {
                    ++size;
                }
            }
            System.out.println("length = " + objects.length
                    + ", size = " + sizeField.get(list)
                    + ", arraySize = " + size);
        } catch (Throwable e) {
            e.printStackTrace();
        }
    }
}

1
2
3
4
5
6
7
8
9
    @Test
    public void testAddAtTail() {
        int initialCapacity = 8;
        ArrayList<Integer> integers = new ArrayList<>(initialCapacity);
        for (int i = 0; i < initialCapacity * 2; i++) {
            xray(integers);
            integers.add(i);
        }
    }

 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
/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 * @throws OutOfMemoryError if minCapacity is less than zero
 */
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

private Object[] grow() {
    return grow(size + 1);
}

/**
 * Returns a capacity at least as large as the given minimum capacity.
 * Returns the current capacity increased by 50% if that suffices.
 * Will not return a capacity greater than MAX_ARRAY_SIZE unless
 * the given minimum capacity is greater than MAX_ARRAY_SIZE.
 *
 * @param minCapacity the desired minimum capacity
 * @throws OutOfMemoryError if minCapacity is less than zero
 */
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}

/**
 * This helper method split out from add(E) to keep method
 * bytecode size under 35 (the -XX:MaxInlineSize default value),
 * which helps when add(E) is called in a C1-compiled loop.
 */
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

1
2
3
4
5
6
7
8
9
    @Test
    public void testAddAtHeader() {
        int initialCapacity = 8;
        ArrayList<Integer> integers = new ArrayList<>(initialCapacity);
        for (int i = 0; i < initialCapacity * 2; i++) {
            xray(integers);
            integers.add(0, i);
        }
    }

 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
/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}

/**
 * A version of rangeCheck used by add and addAll.
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        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
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
/**
 * Appends all of the elements in the specified collection to the end of
 * this list, in the order that they are returned by the
 * specified collection's Iterator.  The behavior of this operation is
 * undefined if the specified collection is modified while the operation
 * is in progress.  (This implies that the behavior of this call is
 * undefined if the specified collection is this list, and this
 * list is nonempty.)
 *
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    System.arraycopy(a, 0, elementData, s, numNew);
    size = s + numNew;
    return true;
}

/**
 * Inserts all of the elements in the specified collection into this
 * list, starting at the specified position.  Shifts the element
 * currently at that position (if any) and any subsequent elements to
 * the right (increases their indices).  The new elements will appear
 * in the list in the order that they are returned by the
 * specified collection's iterator.
 *
 * @param index index at which to insert the first element from the
 *              specified collection
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);

    int numMoved = s - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index,
                         elementData, index + numNew,
                         numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    size = s + numNew;
    return true;
}

 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
package com.diguage.truman;

import org.openjdk.jmh.annotations.*;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * @author D瓜哥, https://www.diguage.com/
 * @since 2020-03-03 13:09
 */
@BenchmarkMode(Mode.Throughput)
@Warmup(iterations = 3)
@State(Scope.Benchmark)
@Threads(8)
public class ArrayListIteratorSpeedTest {

    private ArrayList<Integer> arrayList = null;

    @Setup(Level.Iteration)
    public void setup() {
        int capacity = 1_000_000;
        arrayList = new ArrayList<>(capacity);
        for (int i = 0; i < capacity; i++) {
            arrayList.add(i);
        }
    }

    @Benchmark
    public void testIterator() {
        Integer iteratorValue = null;
        Iterator<Integer> iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            iteratorValue = iterator.next();
        }
    }

    @Benchmark
    public void testRandomAccess() {
        Integer randomAccessValue = null;
        int size = arrayList.size();
        for (int i = 0; i < size; i++) {
            randomAccessValue = arrayList.get(i);
        }
    }

    @Benchmark
    public void testForEachLambda() {
        arrayList.forEach(this::devnull);
    }

    public void devnull(Integer value) {
        Integer forEachLambdaValue = value;
    }

    @Benchmark
    public void testForEach() {
        Integer forEachValue = null;
        for (Integer integer : arrayList) {
            forEachValue = integer;
        }
    }
}

//更新
public E set(int index, E element) {
	rangeCheck(index);

	E oldValue = elementData(index);
	elementData[index] = element;
	return oldValue;
}
//查找

public E get(int index) {
	rangeCheck(index);

	return elementData(index);
}

//是否包含
public boolean contains(Object o) {
	return indexOf(o) >= 0;
}

public int indexOf(Object o) {
	if (o == null) {
		for (int i = 0; i < size; i++)
			if (elementData[i]==null)
				return i;
	} else {
		for (int i = 0; i < size; i++)
			if (o.equals(elementData[i]))
				return i;
	}
	return -1;
}
//反向查找
public int lastIndexOf(Object o) {
	if (o == null) {
		for (int i = size-1; i >= 0; i--)
			if (elementData[i]==null)
				return i;
	} else {
		for (int i = size-1; i >= 0; i--)
			if (o.equals(elementData[i]))
				return i;
	}
	return -1;
}
//容量判断

public int size() {
	return size;
}

public boolean isEmpty() {
	return size == 0;
}

public Object clone() {
	try {
		ArrayList<?> v = (ArrayList<?>) super.clone();
		v.elementData = Arrays.copyOf(elementData, size);
		v.modCount = 0;
		return v;
	} catch (CloneNotSupportedException e) {
		// this shouldn't happen, since we are Cloneable
		throw new InternalError(e);
	}
}

public Object[] toArray() {
	return Arrays.copyOf(elementData, size);
}

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
	if (a.length < size)
		// Make a new array of a's runtime type, but my contents:
		return (T[]) Arrays.copyOf(elementData, size, a.getClass());
	System.arraycopy(elementData, 0, a, 0, size);
	if (a.length > size)
		a[size] = null;
	return a;
}

// Positional Access Operations
//得到指定索引处的元素
@SuppressWarnings("unchecked")
E elementData(int index) {
	return (E) elementData[index];
}
//清空
public void clear() {
	modCount++;

	// clear to let GC do its work
	for (int i = 0; i < size; i++)
		elementData[i] = null;

	size = 0;
}


protected void removeRange(int fromIndex, int toIndex) {
	modCount++;
	int numMoved = size - toIndex;
	System.arraycopy(elementData, toIndex, elementData, fromIndex,
					 numMoved);

	// clear to let GC do its work
	int newSize = size - (toIndex-fromIndex);
	for (int i = newSize; i < size; i++) {
		elementData[i] = null;
	}
	size = newSize;
}

 //检查数否超出数组长度 用于添加元素时
private void rangeCheck(int index) {
	if (index >= size)
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//检查是否溢出
private void rangeCheckForAdd(int index) {
	if (index > size || index < 0)
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private String outOfBoundsMsg(int index) {
	return "Index: "+index+", Size: "+size;
}
//删除指定集合的元素
public boolean removeAll(Collection<?> c) {
	Objects.requireNonNull(c);
	return batchRemove(c, false);
}
//仅保留指定集合的元素
public boolean retainAll(Collection<?> c) {
	Objects.requireNonNull(c);
	return batchRemove(c, true);
}
* @param complement true时从数组保留指定集合中元素的值，为false时从数组删除指定集合中元素的值。
* @return 数组中重复的元素都会被删除(而不是仅删除一次或几次)，有任何删除操作都会返回true
private boolean batchRemove(Collection<?> c, boolean complement) {
	final Object[] elementData = this.elementData;
	int r = 0, w = 0;
	boolean modified = false;
	try {
		for (; r < size; r++)
			if (c.contains(elementData[r]) == complement)
				elementData[w++] = elementData[r];
	} finally {
		// Preserve behavioral compatibility with AbstractCollection,
		// even if c.contains() throws.
		if (r != size) {
			System.arraycopy(elementData, r,
							 elementData, w,
							 size - r);
			w += size - r;
		}
		if (w != size) {
			// clear to let GC do its work
			for (int i = w; i < size; i++)
				elementData[i] = null;
			modCount += size - w;
			size = w;
			modified = true;
		}
	}
	return modified;
}
 //保存数组实例的状态到一个流（即它序列化）。写入过程数组被更改会抛出异常
private void writeObject(java.io.ObjectOutputStream s)
	throws java.io.IOException{
	// Write out element count, and any hidden stuff
	int expectedModCount = modCount;
	s.defaultWriteObject();

	// Write out size as capacity for behavioural compatibility with clone()
	s.writeInt(size);

	// Write out all elements in the proper order.
	for (int i=0; i<size; i++) {
		s.writeObject(elementData[i]);
	}

	if (modCount != expectedModCount) {
		throw new ConcurrentModificationException();
	}
}
//上面是写，这个就是读了。
private void readObject(java.io.ObjectInputStream s)
	throws java.io.IOException, ClassNotFoundException {
	elementData = EMPTY_ELEMENTDATA;

	// Read in size, and any hidden stuff
	s.defaultReadObject();

	// Read in capacity
	s.readInt(); // ignored

	if (size > 0) {
		// be like clone(), allocate array based upon size not capacity
		ensureCapacityInternal(size);

		Object[] a = elementData;
		// Read in all elements in the proper order.
		for (int i=0; i<size; i++) {
			a[i] = s.readObject();
		}
	}
}

public ListIterator<E> listIterator(int index) {
	if (index < 0 || index > size)
		throw new IndexOutOfBoundsException("Index: "+index);
	return new ListItr(index);
}
实现Iterable
public ListIterator<E> listIterator() {
	return new ListItr(0);
}
实现Iterable
public Iterator<E> iterator() {
	return new Itr();
}

private class Itr implements Iterator<E> {
	int cursor;       // index of next element to return
	int lastRet = -1; // index of last element returned; -1 if no such
	int expectedModCount = modCount;

	public boolean hasNext() {
		return cursor != size;
	}

	@SuppressWarnings("unchecked")
	public E next() {
		checkForComodification();
		int i = cursor;
		if (i >= size)
			throw new NoSuchElementException();
		Object[] elementData = ArrayList.this.elementData;
		if (i >= elementData.length)
			throw new ConcurrentModificationException();
		cursor = i + 1;
		return (E) elementData[lastRet = i];
	}

	public void remove() {
		if (lastRet < 0)
			throw new IllegalStateException();
		checkForComodification();

		try {
			ArrayList.this.remove(lastRet);
			cursor = lastRet;
			lastRet = -1;
			expectedModCount = modCount;
		} catch (IndexOutOfBoundsException ex) {
			throw new ConcurrentModificationException();
		}
	}

	@Override
	@SuppressWarnings("unchecked")
	public void forEachRemaining(Consumer<? super E> consumer) {
		Objects.requireNonNull(consumer);
		final int size = ArrayList.this.size;
		int i = cursor;
		if (i >= size) {
			return;
		}
		final Object[] elementData = ArrayList.this.elementData;
		if (i >= elementData.length) {
			throw new ConcurrentModificationException();
		}
		while (i != size && modCount == expectedModCount) {
			consumer.accept((E) elementData[i++]);
		}
		// update once at end of iteration to reduce heap write traffic
		cursor = i;
		lastRet = i - 1;
		checkForComodification();
	}

	final void checkForComodification() {
		if (modCount != expectedModCount)
			throw new ConcurrentModificationException();
	}
}

private class ListItr extends Itr implements ListIterator<E> {
	ListItr(int index) {
		super();
		cursor = index;
	}

	public boolean hasPrevious() {
		return cursor != 0;
	}

	public int nextIndex() {
		return cursor;
	}

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

	@SuppressWarnings("unchecked")
	public E previous() {
		checkForComodification();
		int i = cursor - 1;
		if (i < 0)
			throw new NoSuchElementException();
		Object[] elementData = ArrayList.this.elementData;
		if (i >= elementData.length)
			throw new ConcurrentModificationException();
		cursor = i;
		return (E) elementData[lastRet = i];
	}

	public void set(E e) {
		if (lastRet < 0)
			throw new IllegalStateException();
		checkForComodification();

		try {
			ArrayList.this.set(lastRet, e);
		} catch (IndexOutOfBoundsException ex) {
			throw new ConcurrentModificationException();
		}
	}

	public void add(E e) {
		checkForComodification();

		try {
			int i = cursor;
			ArrayList.this.add(i, e);
			cursor = i + 1;
			lastRet = -1;
			expectedModCount = modCount;
		} catch (IndexOutOfBoundsException ex) {
			throw new ConcurrentModificationException();
		}
	}
}
//返回指定范围的子数组
public List<E> subList(int fromIndex, int toIndex) {
	subListRangeCheck(fromIndex, toIndex, size);
	return new SubList(this, 0, fromIndex, toIndex);
}

static void subListRangeCheck(int fromIndex, int toIndex, int size) {
	if (fromIndex < 0)
		throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
	if (toIndex > size)
		throw new IndexOutOfBoundsException("toIndex = " + toIndex);
	if (fromIndex > toIndex)
		throw new IllegalArgumentException("fromIndex(" + fromIndex +
										   ") > toIndex(" + toIndex + ")");
}

private class SubList extends AbstractList<E> implements RandomAccess {
	private final AbstractList<E> parent;
	private final int parentOffset;
	private final int offset;
	int size;

	SubList(AbstractList<E> parent,
			int offset, int fromIndex, int toIndex) {
		this.parent = parent;
		this.parentOffset = fromIndex;
		this.offset = offset + fromIndex;
		this.size = toIndex - fromIndex;
		this.modCount = ArrayList.this.modCount;
	}

	public E set(int index, E e) {
		rangeCheck(index);
		checkForComodification();
		E oldValue = ArrayList.this.elementData(offset + index);
		ArrayList.this.elementData[offset + index] = e;
		return oldValue;
	}

	public E get(int index) {
		rangeCheck(index);
		checkForComodification();
		return ArrayList.this.elementData(offset + index);
	}

	public int size() {
		checkForComodification();
		return this.size;
	}

	public void add(int index, E e) {
		rangeCheckForAdd(index);
		checkForComodification();
		parent.add(parentOffset + index, e);
		this.modCount = parent.modCount;
		this.size++;
	}

	public E remove(int index) {
		rangeCheck(index);
		checkForComodification();
		E result = parent.remove(parentOffset + index);
		this.modCount = parent.modCount;
		this.size--;
		return result;
	}

	protected void removeRange(int fromIndex, int toIndex) {
		checkForComodification();
		parent.removeRange(parentOffset + fromIndex,
						   parentOffset + toIndex);
		this.modCount = parent.modCount;
		this.size -= toIndex - fromIndex;
	}

	public boolean addAll(Collection<? extends E> c) {
		return addAll(this.size, c);
	}

	public boolean addAll(int index, Collection<? extends E> c) {
		rangeCheckForAdd(index);
		int cSize = c.size();
		if (cSize==0)
			return false;

		checkForComodification();
		parent.addAll(parentOffset + index, c);
		this.modCount = parent.modCount;
		this.size += cSize;
		return true;
	}

	public Iterator<E> iterator() {
		return listIterator();
	}

	public ListIterator<E> listIterator(final int index) {
		checkForComodification();
		rangeCheckForAdd(index);
		final int offset = this.offset;

		return new ListIterator<E>() {
			int cursor = index;
			int lastRet = -1;
			int expectedModCount = ArrayList.this.modCount;

			public boolean hasNext() {
				return cursor != SubList.this.size;
			}

			@SuppressWarnings("unchecked")
			public E next() {
				checkForComodification();
				int i = cursor;
				if (i >= SubList.this.size)
					throw new NoSuchElementException();
				Object[] elementData = ArrayList.this.elementData;
				if (offset + i >= elementData.length)
					throw new ConcurrentModificationException();
				cursor = i + 1;
				return (E) elementData[offset + (lastRet = i)];
			}

			public boolean hasPrevious() {
				return cursor != 0;
			}

			@SuppressWarnings("unchecked")
			public E previous() {
				checkForComodification();
				int i = cursor - 1;
				if (i < 0)
					throw new NoSuchElementException();
				Object[] elementData = ArrayList.this.elementData;
				if (offset + i >= elementData.length)
					throw new ConcurrentModificationException();
				cursor = i;
				return (E) elementData[offset + (lastRet = i)];
			}

			@SuppressWarnings("unchecked")
			public void forEachRemaining(Consumer<? super E> consumer) {
				Objects.requireNonNull(consumer);
				final int size = SubList.this.size;
				int i = cursor;
				if (i >= size) {
					return;
				}
				final Object[] elementData = ArrayList.this.elementData;
				if (offset + i >= elementData.length) {
					throw new ConcurrentModificationException();
				}
				while (i != size && modCount == expectedModCount) {
					consumer.accept((E) elementData[offset + (i++)]);
				}
				// update once at end of iteration to reduce heap write traffic
				lastRet = cursor = i;
				checkForComodification();
			}

			public int nextIndex() {
				return cursor;
			}

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

			public void remove() {
				if (lastRet < 0)
					throw new IllegalStateException();
				checkForComodification();

				try {
					SubList.this.remove(lastRet);
					cursor = lastRet;
					lastRet = -1;
					expectedModCount = ArrayList.this.modCount;
				} catch (IndexOutOfBoundsException ex) {
					throw new ConcurrentModificationException();
				}
			}

			public void set(E e) {
				if (lastRet < 0)
					throw new IllegalStateException();
				checkForComodification();

				try {
					ArrayList.this.set(offset + lastRet, e);
				} catch (IndexOutOfBoundsException ex) {
					throw new ConcurrentModificationException();
				}
			}

			public void add(E e) {
				checkForComodification();

				try {
					int i = cursor;
					SubList.this.add(i, e);
					cursor = i + 1;
					lastRet = -1;
					expectedModCount = ArrayList.this.modCount;
				} catch (IndexOutOfBoundsException ex) {
					throw new ConcurrentModificationException();
				}
			}

			final void checkForComodification() {
				if (expectedModCount != ArrayList.this.modCount)
					throw new ConcurrentModificationException();
			}
		};
	}

	public List<E> subList(int fromIndex, int toIndex) {
		subListRangeCheck(fromIndex, toIndex, size);
		return new SubList(this, offset, fromIndex, toIndex);
	}

	private void rangeCheck(int index) {
		if (index < 0 || index >= this.size)
			throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
	}

	private void rangeCheckForAdd(int index) {
		if (index < 0 || index > this.size)
			throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
	}

	private String outOfBoundsMsg(int index) {
		return "Index: "+index+", Size: "+this.size;
	}

	private void checkForComodification() {
		if (ArrayList.this.modCount != this.modCount)
			throw new ConcurrentModificationException();
	}

	public Spliterator<E> spliterator() {
		checkForComodification();
		return new ArrayListSpliterator<E>(ArrayList.this, offset,
										   offset + this.size, this.modCount);
	}
}

//按照比较器的判断逻辑进行排序
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
	final int expectedModCount = modCount;
	Arrays.sort((E[]) elementData, 0, size, c);
	if (modCount != expectedModCount) {
		throw new ConcurrentModificationException();
	}
	modCount++;
}
 以下基于 1.8，和函数式编程相关的方法
@Override
public void forEach(Consumer<? super E> action) {
	Objects.requireNonNull(action);
	final int expectedModCount = modCount;
	@SuppressWarnings("unchecked")
	final E[] elementData = (E[]) this.elementData;
	final int size = this.size;
	for (int i=0; modCount == expectedModCount && i < size; i++) {
		action.accept(elementData[i]);
	}
	if (modCount != expectedModCount) {
		throw new ConcurrentModificationException();
	}
}

@Override
public Spliterator<E> spliterator() {
	return new ArrayListSpliterator<>(this, 0, -1, 0);
}

static final class ArrayListSpliterator<E> implements Spliterator<E> {


	private final ArrayList<E> list;
	private int index; // current index, modified on advance/split
	private int fence; // -1 until used; then one past last index
	private int expectedModCount; // initialized when fence set

	/** Create new spliterator covering the given  range */
	ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
						 int expectedModCount) {
		this.list = list; // OK if null unless traversed
		this.index = origin;
		this.fence = fence;
		this.expectedModCount = expectedModCount;
	}

	private int getFence() { // initialize fence to size on first use
		int hi; // (a specialized variant appears in method forEach)
		ArrayList<E> lst;
		if ((hi = fence) < 0) {
			if ((lst = list) == null)
				hi = fence = 0;
			else {
				expectedModCount = lst.modCount;
				hi = fence = lst.size;
			}
		}
		return hi;
	}

	public ArrayListSpliterator<E> trySplit() {
		int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
		return (lo >= mid) ? null : // divide range in half unless too small
			new ArrayListSpliterator<E>(list, lo, index = mid,
										expectedModCount);
	}

	public boolean tryAdvance(Consumer<? super E> action) {
		if (action == null)
			throw new NullPointerException();
		int hi = getFence(), i = index;
		if (i < hi) {
			index = i + 1;
			@SuppressWarnings("unchecked") E e = (E)list.elementData[i];
			action.accept(e);
			if (list.modCount != expectedModCount)
				throw new ConcurrentModificationException();
			return true;
		}
		return false;
	}

	public void forEachRemaining(Consumer<? super E> action) {
		int i, hi, mc; // hoist accesses and checks from loop
		ArrayList<E> lst; Object[] a;
		if (action == null)
			throw new NullPointerException();
		if ((lst = list) != null && (a = lst.elementData) != null) {
			if ((hi = fence) < 0) {
				mc = lst.modCount;
				hi = lst.size;
			}
			else
				mc = expectedModCount;
			if ((i = index) >= 0 && (index = hi) <= a.length) {
				for (; i < hi; ++i) {
					@SuppressWarnings("unchecked") E e = (E) a[i];
					action.accept(e);
				}
				if (lst.modCount == mc)
					return;
			}
		}
		throw new ConcurrentModificationException();
	}

	public long estimateSize() {
		return (long) (getFence() - index);
	}

	public int characteristics() {
		return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
	}
}

@Override
public boolean removeIf(Predicate<? super E> filter) {
	Objects.requireNonNull(filter);
	// figure out which elements are to be removed
	// any exception thrown from the filter predicate at this stage
	// will leave the collection unmodified
	int removeCount = 0;
	final BitSet removeSet = new BitSet(size);
	final int expectedModCount = modCount;
	final int size = this.size;
	for (int i=0; modCount == expectedModCount && i < size; i++) {
		@SuppressWarnings("unchecked")
		final E element = (E) elementData[i];
		if (filter.test(element)) {
			removeSet.set(i);
			removeCount++;
		}
	}
	if (modCount != expectedModCount) {
		throw new ConcurrentModificationException();
	}

	// shift surviving elements left over the spaces left by removed elements
	final boolean anyToRemove = removeCount > 0;
	if (anyToRemove) {
		final int newSize = size - removeCount;
		for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
			i = removeSet.nextClearBit(i);
			elementData[j] = elementData[i];
		}
		for (int k=newSize; k < size; k++) {
			elementData[k] = null;  // Let gc do its work
		}
		this.size = newSize;
		if (modCount != expectedModCount) {
			throw new ConcurrentModificationException();
		}
		modCount++;
	}

	return anyToRemove;
}

@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
	Objects.requireNonNull(operator);
	final int expectedModCount = modCount;
	final int size = this.size;
	for (int i=0; modCount == expectedModCount && i < size; i++) {
		elementData[i] = operator.apply((E) elementData[i]);
	}
	if (modCount != expectedModCount) {
		throw new ConcurrentModificationException();
	}
	modCount++;
}

}

 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
transient int size = 0;

/**
 * Pointer to first node.
 */
transient Node<E> first;

/**
 * Pointer to last node.
 */
transient Node<E> last;

/*
void dataStructureInvariants() {
    assert (size == 0)
        ? (first == null && last == null)
        : (first.prev == null && last.next == null);
}
*/

/**
 * Constructs an empty list.
 */
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package com.diguage.truman;

import java.lang.reflect.Field;
import java.util.LinkedList;
import java.util.Objects;

/**
 * @author D瓜哥, https://www.diguage.com/
 * @since 2020-03-03 16:16
 */
public class LinkedListBaseTest {
    /**
     * 使用反射读取 LinkedList 内部属性
     */
    public void xray(LinkedList<?> list) {
        Class<? extends LinkedList> clazz = list.getClass();
        try {
            Field nodeField = clazz.getDeclaredField("first");
            nodeField.setAccessible(true);
            Object node = nodeField.get(list);
            System.out.println("length=" + length(node) + ", size=" + list.size());
        } catch (Throwable e) {
            e.printStackTrace();
        }
    }

    public int length(Object node) {
        int result = 0;
        if (Objects.isNull(node)) {
            return result;
        }
        try {
            Class<?> nodeClass = node.getClass();
            Field nextField = nodeClass.getDeclaredField("next");
            nextField.setAccessible(true);
            while (Objects.nonNull(node)) {
                node = nextField.get(node);
                result++;
            }
        } catch (Throwable e) {
            e.printStackTrace();
        }
        return result;
    }
}

1
2
3
4
5
6
7
8
    @Test
    public void testAddAtTail() {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < 16; i++) {
            xray(list);
            list.add(i);
        }
    }

 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
/**
 * Links e as last element.
 */
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++;
}

/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

1
2
3
4
5
6
7
8
    @Test
    public void testAddAtHeader() {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < 16; i++) {
            xray(list);
            list.addFirst(i);
        }
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Links e as first element.
 */
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++;
}

/**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
public void addFirst(E e) {
    linkFirst(e);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
typedef struct listNode {
    struct listNode prev;
    struct listNode next;
    void value;
} listNode;

typedef struct listIter {
    listNode next;
    int direction;
} listIter;

typedef struct list {
    listNode head;
    listNode tail;
    void (dup)(void ptr);
    void (free)(void ptr);
    int (match)(void ptr, void key);
    unsigned long len;
} list;

The general layout of the ziplist is as follows:

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

NOTE: all fields are stored in little endian, if not specified otherwise.

<prevlen> <encoding> <entry-data> (1)

list-max-ziplist-size -2

list-compress-depth 0 // 0 是特殊值，表示都不压缩，默认值。

 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
/* Node, quicklist, and Iterator are the only data structures used currently. /

/ quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
 * We use bit fields keep the quicklistNode at 32 bytes.
 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
 * encoding: 2 bits, RAW=1, LZF=2.
 * container: 2 bits, NONE=1, ZIPLIST=2.
 * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
 * attempted_compress: 1 bit, boolean, used for verifying during testing.
 * extra: 10 bits, free for future use; pads out the remainder of 32 bits /
typedef struct quicklistNode {
    struct quicklistNode prev;
    struct quicklistNode next;
    unsigned char zl;
    unsigned int sz;             /* ziplist size in bytes /
    unsigned int count : 16;     / count of items in ziplist /
    unsigned int encoding : 2;   / RAW==1 or LZF==2 /
    unsigned int container : 2;  / NONE==1 or ZIPLIST==2 /
    unsigned int recompress : 1; / was this node previous compressed? /
    unsigned int attempted_compress : 1; / node can't compress; too small /
    unsigned int extra : 10; / more bits to steal for future usage /
} quicklistNode;

/ quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.
 * 'sz' is byte length of 'compressed' field.
 * 'compressed' is LZF data with total (compressed) length 'sz'
 * NOTE: uncompressed length is stored in quicklistNode->sz.
 * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF /
typedef struct quicklistLZF {
    unsigned int sz; / LZF size in bytes*/
    char compressed[];
} quicklistLZF;

/* Bookmarks are padded with realloc at the end of of the quicklist struct.
 * They should only be used for very big lists if thousands of nodes were the
 * excess memory usage is negligible, and there's a real need to iterate on them
 * in portions.
 * When not used, they don't add any memory overhead, but when used and then
 * deleted, some overhead remains (to avoid resonance).
 * The number of bookmarks used should be kept to minimum since it also adds
 * overhead on node deletion (searching for a bookmark to update). /
typedef struct quicklistBookmark {
    quicklistNode node;
    char name;
} quicklistBookmark;

/ quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
 * 'count' is the number of total entries.
 * 'len' is the number of quicklist nodes.
 * 'compress' is: -1 if compression disabled, otherwise it's the number
 *                of quicklistNodes to leave uncompressed at ends of quicklist.
 * 'fill' is the user-requested (or default) fill factor.
 * 'bookmakrs are an optional feature that is used by realloc this struct,
 *      so that they don't consume memory when not used. /
typedef struct quicklist {
    quicklistNode head;
    quicklistNode tail;
    unsigned long count;        / total count of all entries in all ziplists /
    unsigned long len;          / number of quicklistNodes /
    int fill : QL_FILL_BITS;              / fill factor for individual nodes /
    unsigned int compress : QL_COMP_BITS; / depth of end nodes not to compress;0=off /
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistIter {
    const quicklist quicklist;
    quicklistNode current;
    unsigned char zi;
    long offset; /* offset in current ziplist /
    int direction;
} quicklistIter;

typedef struct quicklistEntry {
    const quicklist quicklist;
    quicklistNode node;
    unsigned char zi;
    unsigned char *value;
    long long longval;
    unsigned int sz;
    int offset;
} quicklistEntry;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
$ redis-cli --raw

127.0.0.1:6379> RPUSH names diguage "D瓜哥" "https://www.diguage.com/"
2

127.0.0.1:6379> LRANGE names 0 -1
diguage
D瓜哥
https://www.diguage.com/

127.0.0.1:6379> TYPE names
list

127.0.0.1:6379> OBJECT encoding names
quicklist

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

package java.util;

import java.util.function.Consumer;

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