List is an important member of the Java Collection Framework, including List Interface and all its implementation classes. Since the List interface inherits the Collection interface, List has all the operations of Collection. At the same time, because List is a list type, List itself also provides some methods suitable for itself. ArrayList is a dynamic array, which realizes dynamic expansion of the array and has high random access efficiency; LinkedList is a doubly linked list, random insertion and Deletion is efficient and can be used as an implementation of queue.
List includes List interface and all implementation classes of List interface (ArrayList , LinkedList, Vector, Stack), where Vector and Stack are obsolete. Because the List interface implements the Collection interface (as shown in code 1), the List interface has all the common methods provided by the Collection interface. At the same time, because List is a list type, the List interface also provides some common methods suitable for itself. As shown in Table 1.
Replace the element at the specified position in the list with the specified element
Optional operation, set operation is for List Special operations
##void add(int index, E element)
Insert the specified element at the specified position in the list
Optional operations
E remove(int index)
Remove the element at the specified position in the list
Optional operations
int indexOf(
Object
o)Return to this list The
index
of the first occurrence of the specified element in the list; if this list does not contain the element, then -1 is returnedImplemented by default in AbstractList; overridden in ArrayList and LinkedList respectively;
int lastIndexOf(Object o)
Returns the index of the last occurrence of the specified element in this list; if the list does not contain this element, returns -1
Implemented by default in AbstractList; rewritten in ArrayList and LinkedList respectively;
##ListIterator listIterator()
Returns the list iteration of this list element Converters (in appropriate order)
are implemented by default in AbstractList, ArrayList, Vector and Stack use this default implementation, and LinkedList overrides this implementation;
ListIterator listIterator(int index)
Returns a list iterator of the elements in the list (in appropriate order), starting at the specified position in the list
The default implementation in AbstractList, ArrayList, Vector and Stack use this default implementation, LinkedList overrides this implementation
;
List subList (int fromIndex, int toIndex)
Returns the
view between the specified fromIndex (inclusive) and toIndex (exclusive) in the listThe default implementation in AbstractList (ArrayList, LinkedList uses this default implementation);
The reason why it is called a view is because the list actually returned is based on the original list supported;
Specifically, for List:
AbstractList provides a general implementation of the iterator() method, The next() and remove() methods are implemented by the get(int index) and remove(int index) methods respectively;
For the subList method, original list and sublist are made non-structural Sexual modifications (modifications that do not involve changes in the size of the list) will affect each other; For structural modifications:If structural modifications occur is the returned sublist, then the size of the original list will also change (modCount and expectedModCount change at the same time, the Fast-Fail mechanism will not be triggered); If a structural problem occurs The original list is modified (excluding changes caused by the returned sublist), then the judgment l.modCount != expectedModCount will return TRUE, trigger the Fast-Fail mechanism, and throw Concurrent ModificationException. Therefore, If you modify the size of the original list after calling sublist and returning the sublist, the previously generated sublist will be invalid;
Delete a section of a list: list.subList(from, to).clear();
## cco Numbers by List structure
The classes involved are introduced:
AbstractList is an
abstract class
, which implements the List interface and inherits from AbstractCollection.
For the requirement of "traversing and accessing elements in order", you can use List's Iterator. The abstract class AbstractList provides this implementation; while accessing elements at specific positions (that is, accessing by index), The addition and deletion of elements involves the connection relationship of each element in the List, and no implementation is provided in AbstractList (the types of List are different, and their implementation methods are also different, so the specific implementation is placed in subclasses);AbstractSequentialList is an abstract class that inherits from AbstractList
.
AbstractSequentialList implements "all
functions in the linked list that operate the linked list based on the index index value" through ListIterator. In addition, ArrayList implements "all functions in the sequence table to operate the sequence table according to the index index value" through System.arraycopy (complete the movement of elements); ArrayList, LinkedList, Vector, and Stack are the four implementation classes of List;
ArrayList is a
dynamic array
. It is implemented by an array, with high random access efficiency, but low random insertion and random deletion efficiency; LinkedList is a
doubly linked list (Sequence table)
.
LinkedList has low random access efficiency, but high random insertion and random deletion efficiency. It can be operated as a stack, queue or double-ended queue; Vector is a vector queue. Like ArrayList, it is also a dynamic array. Implemented by array
.
But ArrayList is non-threaded
safe, while Vector is thread-safe; Stack is a stack, which inherits in Vector.
Its characteristics are:
FILO, First In Last Out.
3. List characteristic:
List in Java is an effective extension of the array. It is a structure that can accommodate elements of any type if generics are not used. If generics are used, it can only Holds elements of the type specified by the generic. Compared with arrays (Arrays do not support generics), the capacity of List can be dynamically expanded;
## The elements in #List are "ordered".
The "ordered" here does not mean sorting, but means that we can specify the position of an element in the collection, Including pairs Precise control over the insertion position of each element in the list, accessing elements based on their integer index (position in the list) and searching for elements in the list;
The elements in List can be repeated because it is an ordered data structure;
The List interface provides a special iterator, called ListIterator, that allows, in addition to the normal operations provided by the Iterator interface,
The iterator also allows element insertion and replacement, as well as bidirectional access.
3. ArrayList
1. ArrayList basics
ArrayList implements all optional operations in List and allows all elements including NULL. In addition to implementing the List interface, this class also provides methods to manipulate the size of its supporting array. ArrayList is implemented based on arrays. It is a dynamic array whose capacity can grow automatically. The size attribute is used to identify the number of elements in the container, not the size of the packed array. Each ArrayList instance has a capacity, which is the size of the array used to store the list elements, and it is always at least equal to the size of the list. As elements are continuously added to the ArrayList, its capacity also grows automatically. Automatic growth will cause data to be re-copied to the new array. Therefore, if the amount of data can be predicted, you can specify its capacity when constructing the ArrayList. Applications can also use the ensureCapacity operation to increase the capacity of an ArrayList instance before adding a large number of elements, which can reduce the amount of incremental reallocation. Note that this implementation is not synchronous. If multiple threads access an ArrayList instance at the same time, and at least one of the threads structurally modifies it (structural modification refers to any operation that adds or removes one or more elements, or explicitly adjusts the size of the underlying array; Merely setting the value of an element is not a structural modification.) If the list is modified, it must be kept externally synchronized.
ArrayList implements the Serializable interface, so it supports serialization and can be transmitted through serialization. Reading the source code, you can find that the built-in array of ArrayList is modified with the transient keyword to indicate that it will not be serialized. Of course, the elements of the ArrayList will eventually be serialized. During serialization/deserialization, the writeObject()/readObject() method of the ArrayList will be called, and the elements in the ArrayList (i.e. 0 ...The element corresponding to the size-1 subscript) and capacity size are written to/read from the stream. The advantage of this is that only elements with practical significance are saved/transmitted, which saves storage, transmission and processing overhead to the greatest extent.
public ArrayList(int initialCapacity){ … } ： 给定初始容量的构造函数；
public ArrayList() { … } ：Java Collection Framework 规范-默认无参的构造函数 (初始容量指定为10)；
public ArrayList(Collectionc) { … } ：Java Collection Framework 规范-参数为指定容器的构造函数
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
private static final long serialVersionUID = 8683452581122892189L;
/**
* The array buffer into which the elements of the ArrayList are stored.（ArrayList 支撑数组）
* The capacity of the ArrayList is the length of this array buffer.（ArrayList 容量的定义）
*/
private transient Object[] elementData;
// 瞬时域
/**
* The size of the ArrayList (the number of elements it contains).（ArrayList 大小的定义）
*/
private int size; /**
* Constructs an empty list with the specified initial capacity
*/
public ArrayList(int initialCapacity) {
// 给定初始容量的构造函数
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
// 泛型与数组不兼容
} /**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
// Java Collection Framework 规范：默认无参的构造函数
this(10);
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*/
public ArrayList(Collection<? extends E> c) {
// Java Collection Framework 规范：参数为指定容器的构造函数
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
Copy after login
3、ArrayList 基本操作的保证
边界检查（即检查 ArrayList 的 Size）：涉及到 index 的操作
// 边界检查private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}
Copy after login
调整数组容量（增加容量）：向 ArrayList 中增加元素
// 调整数组容量
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
private class Itr implements Iterator<E> {
int cursor;
int lastRet = -1;
int expectedModCount = ArrayList.this.modCount;
public boolean hasNext() {
return (this.cursor != ArrayList.this.size);
}
public E next() {
checkForComodification();
/** 省略此处代码 */
}
public void remove() {
if (this.lastRet < 0)
throw new IllegalStateException();
checkForComodification();
/** 省略此处代码 */
}
final void checkForComodification() {
if (ArrayList.this.modCount == this.expectedModCount)
return;
throw new ConcurrentModificationException();
}
}
// 移除此列表中指定位置上的元素
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
Copy after login
remove(Object o)：
// 移除此列表中 “首次” 出现的指定元素（如果存在）。这是因为 ArrayList 中允许存放重复的元素。
public boolean remove(Object o) {
// 由于ArrayList中允许存放null，因此下面通过两种情况来分别处理。
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
// 类似remove(int index)，移除列表中指定位置上的元素。
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
}
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
private transient Entry header = new Entry(null, null, null);
private transient int size = 0; /**
* Constructs an empty list.
*/
public LinkedList() {
header.next = header.previous = header;
} /**
* 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 c) { this();
addAll(c);
}
public E get(int index) {
try {
return listIterator(index).next();
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
Copy after login
该方法涉及到 listIterator 的构造，我们再看listIterator 的源码。
listIterator 源码
private class ListItr implements ListIterator<E> {
// 最近一次返回的节点，也是当前持有的节点
private Entry<E> lastReturned = header;
// 对下一个元素的引用
private Entry<E> next;
// 下一个节点的index
private int nextIndex;
private int expectedModCount = modCount;
// 构造方法，接收一个index参数，返回一个ListItr对象
ListItr(int index) {
// 如果index小于0或大于size，抛出IndexOutOfBoundsException异常
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size); // 判断遍历方向
if (index < (size >> 1)) { // 相当于除法，但比除法效率高
// next赋值为第一个节点
next = header.next; // 获取指定位置的节点
for (nextIndex=0; nextIndex<index; nextIndex++)
next = next.next;
} else {// else中的处理和if块中的处理一致，只是遍历方向不同
next = header; for (nextIndex=size; nextIndex>index; nextIndex--)
next = next.previous;
}
} // 根据nextIndex是否等于size判断时候还有下一个节点（也可以理解为是否遍历完了LinkedList）
public boolean hasNext() { return nextIndex != size;
} // 获取下一个元素
public E next() {
checkForComodification();
// 如果nextIndex==size,则已经遍历完链表，即没有下一个节点了（实际上是有的，因为是循环链表，任何一个节点都会有上一个和下一个节点，
这里的没有下一个节点只是说所有节点都已经遍历完了）
if (nextIndex == size) throw new NoSuchElementException();
// 设置最近一次返回的节点为next节点
lastReturned = next; // 将next“向后移动一位”
next = next.next; // index计数加1
nextIndex++; // 返回lastReturned的元素
return lastReturned.element;
} public boolean hasPrevious() {
return nextIndex != 0;
}
// 返回上一个节点，和next()方法相似
public E previous() {
if (nextIndex == 0)
throw new NoSuchElementException();
lastReturned = next = next.previous;
nextIndex--;
checkForComodification();
return lastReturned.element;
} public int nextIndex() {
return nextIndex;
} public int previousIndex() {
return nextIndex-1;
} // 移除当前Iterator持有的节点
public void remove() {
checkForComodification();
Entry<E> lastNext = lastReturned.next;
try {
LinkedList.this.remove(lastReturned);
} catch (NoSuchElementException e) {
throw new IllegalStateException();
} if (next==lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = header;
expectedModCount++;
} // 修改当前节点的内容
public void set(E e) {
if (lastReturned == header)
throw new IllegalStateException();
checkForComodification();
lastReturned.element = e;
} // 在当前持有节点后面插入新节点
public void add(E e) {
checkForComodification();
// 将最近一次返回节点修改为header
lastReturned = header;
addBefore(e, next);
nextIndex++;
expectedModCount++;
}
// 判断expectedModCount和modCount是否一致，以确保通过ListItr的修改操作正确的反映在LinkedList中
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
Copy after login
由以上 get 和 listIterator 源码可知，与 ArrayList 比较而言，LinkedList的随机访问需要从头遍历到指定位置元素，而不像ArrayList直接通过索引取值，效率更低一些。
4、小结
关于LinkedList的源码，给出几点比较重要的总结：
LinkedList 本质是一个双向循环链表，可用作List，Queue，Stack和Deque；
LinkedList 并未实现 RandomAccess 接口；
相对于ArrayList，LinkedList有更好的增删效率，更差的随机访问效率；
The above is the detailed content of Java Collection Framework -List specific description. For more information, please follow other related articles on the PHP Chinese website!
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
