Follow the public account: Java big data and data warehouse, learn big data technology
Initial LinkedList
LinkedList, like ArrayList, is an implementation class for collection Lists. Although it is used in fewer scenarios than ArrayList, it is also useful. So let’s look at it. In fact, they both belong to the same camp of lists, but the implementation is different. ArrayList is implemented with Array, and LinkedList is implemented with bidirectly-linked lists
First of all, let’s go back to an ArrayList, and an ArrayList is an array at the bottom, and you add or remove elements that are indexed on an array, but you remember that the underlying implementation depends on arrays.
The LinkedList class is a two-way list, with each node in the list containing references to the previous and the next element. Because it is a two-way linked list as the main structure, so there is no longer dependent on the array, the data is encapsulated in a node, the node and the relationship between the nodes, is through the node pointer said, between the elements in the ArrayList section is actually more accurate data, or is the element itself) has not been encapsulated into a node, but naked, Because the relationship between nodes is represented by the properties of the array container, the main subscript maintains the order.
The final LinkedList looks like this
1. Prospectus for LinkedList
Before looking at the specification, let’s look at the inheritance of the entire class
AbstractSequentialList LinkedList extends AbstractSequentialList class and implements the List interface. AbstractSequentialList has implemented many methods. Such as get(int index), set(int index, E element), add(int index, E element) and remove(int index), these are the most commonly used methods for collection operations. However, these methods have been overwritten in the LinkedList, while the abstract methods are implemented in the LinkedList.
Following the international convention, let’s first look at the description of LinkedList, or class annotation, to give us an idea of the class
/**
* Doubly-linked list implementation of the {@code List} and {@code Deque} interfaces. Implements all optional list operations, and permits all elements (including {@code* Doubly-linked List implements the newkey interface. It does everything from the List interface to the Deque interface, and allows all values. Including null * All of the operations perform as could be expected for a key -linked list. Operations that index into the list will traverse the list from the beginning or the end, The specified index will be iterated from the beginning of the list or from the tail of the list. Until traversing to this subscript * <p><strong>Note that this implementation is not synchronized.</strong> * If multiple threads access a linked list concurrently, and at least * one of the threads modifies the list structurally, it <i>must</i> be * synchronized externally. (A structural modification is any operation * that adds or deletes one or more elements; merely setting the value of * an element is not a structural modification.) This is typically * accomplished by Synchronizing on some object that naturally * encapsulates the list. Synchronizing on some object that naturally * encapsulates the list. If no such object exists, the list should be "wrapped" using the * {@linkCollections#synchronizedList Collections.synchronizedList} * method. This is best done at creation time, to prevent accidental * unsynchronized access to the list:<pre> List list = Collections.synchronizedList(new LinkedList(...) ); </pre> * This follows the previous paragraph. If you don't have such a lockable object, you can use the LinkedList wrapper object, Is the call List List = Collections. SynchronizedList (new LinkedList (...). * <p>The iterators returned by this class's {@code iterator} and
* {@code listIterator} methods are <i>fail-fast</i>: if the list is
* structurally modified at any time after the iterator is created, in
* any way except through the Iterator's own {@code remove} or
* {@code add} methods, the iterator will throw a {@link* ConcurrentModificationException}. Thus, in the face of concurrent * modification, the iterator fails quickly and cleanly, rather than * risking arbitrary, Non-deterministic behavior at an undetermined * time in the future. * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. Fail-fast iterators * throw {@code ConcurrentModificationException} on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <i>the fail-fast behavior of iterators
* should be used only to detect bugs.</i>
* @author Josh Bloch
* @see List
* @see ArrayList
* @since 1.2
* @param <E> the type of elements held in this collection
*/
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable.java.io.Serializable
{... . }Copy the code2. Internal composition of LinkedList
size
transient int size = 0;
Copy the codeThis is how many elements the LinkedList stores, or the length of the collection
Node
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; }}Copy the codeLinkedList is implemented through a bidirectional LinkedList, which is represented by the Node class, with the next variable pointing to the next Node and the prev variable pointing to the previous Node
LinkedList encapsulates data into Node objects, where the item variable holds the value of the current Node. ArrayList is the real data stored (in its original form) without encapsulation
Therefore, ArrayList consumes less space than LinkedList because LinkedList maintains front and back Pointers and encapsulates data
first last
/** * Pointer to first node. */
transient Node<E> first;
/** * Pointer to last node. */
transient Node<E> last;
Copy the codeSince it is a bidirectional list, we refer to the top and bottom nodes of the bidirectional list
The node method
NodeAtIndex () returns a node at a specific location. NodeAtIndex () returns a node at a specific location. NodeAtIndex () returns a node at a specific location. NodeAtIndex () returns a node at a specific location
/** * Returns the (non-null) Node at the specified element index. It's a node that returns a particular location, a node in a linked list, so it can't be empty */
Node<E> node(int index) {
// If 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;
returnx; }}Copy the code3. Constructor of LinkedList
There is no such thing as an initial size for LinkedList, since the underlying level does not rely on array support
No arguments structure
/** * Constructs an empty list. Create an empty */
public LinkedList(a) {}Copy the codeSet based construction
/** * 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(a); addAll(c); }Copy the codeCommon methods of LinkedList
1. add(E e)
Everyone talks about how efficient LinkedList inserts and deletes are. What’s going on with stringList.add?
@Test
public void add(a) {
LinkedList xiyouList = new LinkedList();
xiyouList.add("Pig Eight Quit");
}
Copy the codeIn LinkedList we find the source code for the Add (E E) method
public boolean add(E e) {
linkLast(e);
return true;
}
/** * sets element e as the last element. This method is also called when adding elements to the specified location */
void linkLast(E e) {
final Node<E> l = last;
// Add e to the end of the list so that last precedes e and e is null
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
// If last is null, the table is empty, and e(newNode) becomes first
first = newNode;
else
// Otherwise e(newNode) becomes the suffix of last
l.next = newNode;
// Record the current number of elements and record the modification
size++;
modCount++;
}
Copy the codeFor the if-else two cases above, let’s comb them separately:
Case 1: If xiyouList is empty, then the added node is first and last, and the prev and next of this node are both null.
Case 2: If xiyouList is not empty, then the added node is last, the prev of node points to the last element before, and the next element is null. And the last element before next.
2. add(int index, E element)
Let’s look at a variation of add(int index, E element), such as xiyouList(1, “Pig Eight Quits”).
@Test
public void add(a) {
LinkedList xiyou = new LinkedList();
xiyou.add(1."Pig Eight Quit");
}
Copy the codeBy tracing the source code, you can see that it calls this method
/** * 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). * Insert the specified element at the specified position in this list. Move the element currently in that position (if any) and any subsequent elements to the right, and then insert the element to be inserted *@param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc} * /
// Add an element at the specified location
public void add(int index, E element) {
// Check the validity of the subscript
checkPositionIndex(index);
// if index=size, add to the end of the set
if (index == size)
linkLast(element);
// Otherwise, the index position added to the collection (index is not the last position)
else
// Since it is not added to the end, we can get the current element in this position, node(index).
linkBefore(element, node(index));
}
Copy the codecheckPositionIndex
So let’s first look at this method of checking the validity of subscripts
private void checkPositionIndex(int index) {
if(! isPositionIndex(index))// This is the exception thrown if the subscript is illegal
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
** * Tells if the argument is the index of a valid position for an iterator or an add operation. * Tells if the argument is the index of a valid position for an iterator or an add operation. Determine if a subscript is valid */
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
Copy the codelinkLast
At this point, it’s the same as adding (E Element) because index=size is essentially adding to the end of the list
/** * Links e as last element. To concatenate e as last is to add it to the end of the list */
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++;
}
Copy the codelinkBefore
Because at this point, it is already known that it was not added at last, so it must have been added before the non-empty node
/** * Inserts an element in front of a non-empty node. Succ is an element that already exists at the current location passed in. The next thing to do is to concatenate e with succ */
void linkBefore(E e, Node<E> succ) {
// assert succ ! = null;
// succ prefix
final Node<E> pred = succ.prev;
Succ_pree <->succ <-> succ_next <-> e <->succ <-> succ_next
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
// If pree is null, e replaces succ as the new first
if (pred == null)
first = newNode;
else
// Otherwise, e becomes the afterposition of succ
pred.next = newNode;
// Record modification
size++;
modCount++;
}
Copy the codeAdd (E, E) creates a new Node entity and specifies its prev and next. The difference is that Node (int index) needs to be called to locate the insertion position through the incoming index, which is also time-consuming
In fact, when you look at this, you also understand.
The efficiency of LinkedList insertion is relative because it eliminates the overhead of array expansion and data element movement that ArrayList inserts may incur, but data expansion and data element movement do not happen all the time.
3. get(int index)
We know that random reading of elements is not what LinkedList is good at, and it’s much less efficient than ArrayList, so let’s see why, and we can probably guess why before we get started, because we explained it in part in the class specification because it’s essentially a traversal operation, It’s an O(n) operation instead of an O(1) operation
So let’s look at it more concretely
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Copy the codeThe checkElementIndex method checks if the index is valid, and the Node method checks if the index is valid, so let’s see how this checks
private void checkElementIndex(int index) {
if(! isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/** * Tells if the argument is the index of an existing element. */
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
Copy the codeIt actually limits the range of subscripts, and in fact if you look closely at the add part of the code, you’ll see that this part of the code is very similar to the above, the only difference is the purpose, one is to check whether the insert position is valid, and this method is to check whether the fetch position is valid, So it’s called isElementIndex instead of isPositionIndex, because the purpose is different and the condition is different, index must be less than size, because size is empty, but it can be inserted
Get (int index) is implemented by node(int index).
Compare the index parameter passed in with the set length size/2. If index is small, then loop through the first one until it is found. If index is large, then loop from the last one in reverse order until it is found. That is, the closer you get to the middle element, the more times you call get(int index), the less efficient it becomes, and the performance of get(int index) decreases exponentially as the set gets larger and larger.
Therefore, we do not recommend reading data in this way when using LinkedList. Instead, we can use the **getFirst(), getLast()** methods, which directly use the first and last variables in the class.
4. RemoveFirst () and removeLast ()
RemoveFirst () is very similar to removeLast() in that it uses the first and last variables defined in the class, so we’ll just say removeFirst. You can look at removeLast for yourself
/** * Removes and returns the first element from this list. Removes the first element in the list * *@return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst(a) {
final Node<E> f = first;
// If f is null, throw an exception. You should not throw an exception, just return null, otherwise you will have to check if the list is empty every time you call this method
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/** * Unlinks non-null first node f. Unconnect first */
private E unlinkFirst(Node<E> f) {
// assert f == first && f ! = null;
final E element = f.item;
final Node<E> next = f.next;
// help GC, why f is not directly assigned to null
f.item = null;
f.next = null;
first = next;
if (next == null)
last = null;
else
// Since next has become first, there should be no front-loading
next.prev = null;
size--;
modCount++;
return element;
}
Copy the code5. Remove (Object o) and remove(int index)
We look at remove(Object O) and remove(int index) source code
// Delete an object
public boolean remove(Object o) {
if (o == null) {
for(Node<E> x = first; x ! =null; x = x.next) {
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;
}
// Remove the element at a location
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
// Delete a node and associate its previous node (if any) with its next node (if any)
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
Copy the codeRemove (Object o) ¶ Remove (Object o) ¶ Remove (Object O) ¶ Remove (int index) Uses the node(index) method.
6. LinkedList Traverses the performance comparison
We enumerate the three methods commonly used traversal, common for loop, enhanced for loop, the Iterator iterators, traverse cnooc, of course, a problem is the rapid failure of the problem, but there is no longer for example, because the previous articles have been written better, you can try this, also can refer to other collections in front of the article
public static void main(String[] args) {
LinkedList<Integer> list = getLinkedList();
// Iterate through the LinkedList with a quick random access
listByNormalFor(list);
// Iterate through the LinkedList by enhancing the for loop
listByStrengThenFor(list);
// Iterate through the LinkedList with a fast iterator
listByIterator(list);
}
/** * Build a collection of LinkedList containing 50000 elements *@return* /
private static LinkedList<Integer> getLinkedList(a) {
LinkedList list = new LinkedList();
for (int i = 0; i < 50000; i++){
list.add(i);
}
return list;
}
/** * traverses the LinkedList */ with a quick random access
private static void listByNormalFor(LinkedList<Integer> list) {
// Record the start time
long start = System.currentTimeMillis();
int size = list.size();
for (int i = 0; i < size; i++) {
list.get(i);
}
// Record the time
long interval = System.currentTimeMillis() - start;
System.out.println("listByNormalFor：" + interval + " ms");
}
/** * Iterate through the LinkedList * by enhancing the for loop@param list
*/
public static void listByStrengThenFor(LinkedList<Integer> list){
// Record the start time
long start = System.currentTimeMillis();
for (Integer i : list) { }
// Record the time
long interval = System.currentTimeMillis() - start;
System.out.println("listByStrengThenFor：" + interval + " ms");
}
/** * iterates through LinkedList */
private static void listByIterator(LinkedList<Integer> list) {
// Record the start time
long start = System.currentTimeMillis();
for(Iterator iter = list.iterator(); iter.hasNext();) {
iter.next();
}
// Record the time
long interval = System.currentTimeMillis() - start;
System.out.println("listByIterator：" + interval + " ms");
}
Copy the codeThe result is as follows:
ListByNormalFor:1067Ms listByStrengThenFor:3Ms listByIterator:2 ms
Copy the codeWe can understand that random access through a regular for loop takes much longer than iterator access, as we saw earlier in the get(int index) method. So why does enhanced for loop make iterator traversal almost as efficient?
Using the decompiler tool, you get the following code
public static void listByStrengThenFor(LinkedList<Integer> list)
{
long start = System.currentTimeMillis();
Integer localInteger;
for (Iterator localIterator = list.iterator(); localIterator.hasNext();
localInteger = (Integer)localIterator.next()) {}
long interval = System.currentTimeMillis() - start;
System.out.println("listByStrengThenFor：" + interval + " ms");
}
Copy the codeObviously, enhanced for loop traversal also calls the Iterator, but with an assignment.
Methods such as pollFirst() and pollLast() delete can also achieve partial traversal.
ArrayList vs. LinkedList
As mentioned earlier, ArrayList and LinkedList belong to the List camp and both implement the List interface, while LinkedList implements the Deque interface. ArrayList is used in many scenarios and can well meet our needs
Realize the principle of
LinkedList is designed to accommodate a double-linked list, whereas ArrayList is implemented using an array that can be dynamically expanded. So there is no initial capacity or default capacity in LinkedList
performance
Considerations of performance and usage scenarios capture the main factors we choose in daily use. Let’s talk about both from the perspective of storage, add, insert, and delete
storage
LinkedList storage is higher than ArrayList because each inserted data needs to be wrapped and Pointers are maintained, and Pointers have storage overhead
insert
LinkedList has high insertion performance because it only needs to break the existing LinkedList structure and then reconnect. But when you add to a specific location, it involves walking through and then determining the location
ArrayList inserts are also inserted to the tail by default, but when scaling up involves data migration; Data migration is involved when you insert into a specific location
To obtain
The reading of LinkedList involves traversal of the LinkedList, so the performance is not high and the time complexity is O(n).
ArrayList takes advantage of the properties of arrays to directly retrieve data at specified subscripts. Time complexity O(1)
delete
LinkedList deletion, either subindex deletion or by element deletion, involves list traversal, so the average time complexity is O(n)
ArrayList deletion involves the migration of elements, so the average time complexity is O(n).
4. To summarize
Previously, we studied ArrayList and LinkedList, and explored their principles, underlying implementation, and method usage, and performance comparison, respectively
Is there anything you think could be improved on LinkedList
As in the last video, I’m going to present the same question here, and while we may be wrong, and we may never reach the heights of source code writers, we’re still thinking positively and discussing boldly
Although the mountain of Java source code is high, if you want to climb it, at least you have to have the courage to climb it, here I give my own little advice, I hope you don’t hesitate to teach
Node (index) is a noncanonical name
The following code can be refactored, but the similarity is too high and the name is not very clear
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));
}
/** * Tells if the argument is the index of a valid position for an * iterator or an add operation. */
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
/** * Tells if the argument is the index of an existing element. */
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
Copy the codeThe remove method below should not throw an exception, but should return null. The client can do business with null or not, otherwise I think your iteration method should also throw an exception
public E removeFirst(a) {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
Copy the code