LinkedList source code analysis

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

1. LinkedList implements the Deque interface and can be used as a queue; Implementation of cloneABLE indicates that can be cloned, implementation of Serializable interface indicates that support serialization.
2. LinkedList is based on a two-way LinkedList, implements all List operations and allows all elements to include null values, and can be treated as a double-ended queue.
3. LinkedList sequential access is very efficient, while random access is inefficient.
4. LinkedList thread safe, you can use the Collections. SynchronizedList make it thread safe.

1. Member variables

transient int size = 0;

transient Node<E> first;

transient Node<E> last;
Copy the code

/ / the node class
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 code

Size: indicates the number of current nodes

First: refers to the starting element of the list

Last: refers to the last element in the list.

Node: bidirectional linked list

2. Construction method

public LinkedList(a) {}// The parameter construct can convert a collection class to LinkedList
public LinkedList(Collection<? extends E> c) {
    this(a); addAll(c); }public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
Copy the code

The addAll method inserts the Collection Collection into the linked list. Let’s take a closer look at the whole process (which involves a lot of pointer manipulation).

• First, the code checks the index value for correctness, and throws an exception if the index position is ignored.
• Then convert the set to be inserted into an array to determine the length of the set.
• Set pred and SUCC Pointers, respectively, based on the index value. If the insertion position is at the end of the current list, pred points to the last element and succ is temporarily set to NULL. If the insertion position is in the middle of the list, the node method is used to find the element at the index position of the current list, and succ points to it. Pred points to the previous node, succ points to the node at the current index, and the newly inserted node is between the pred and succ nodes.
• Next points to the newly created Node, and then pred points back to the newly created Node. Repeat the process so that each Node is created and linked.
• Finally, the node that succ points to is the last node, depending on the situation, and of course, if succ is NULL, the last pointer points to pred.

3. Basic methods

The following methods are relatively simple and do not require much implementation detail

3.1. Add method

Add a node after last

3.2. Remove method

Deleting a node

3.4. Clear method

empty

3.4. Queue related methods

Because you implement a Deque, you can use the following method

Note the differences between the two groups of methods as queues

4. Compare with ArrayList

4.1. Main differences

1. ArrayList is a data structure based on dynamic arrays, and LinkedList is a data structure based on linked lists. (LinkedList is a two-way LinkedList, with next and previous)

2. ArrayList feels superior to LinkedList for random access to GET and set because LinkedList moves the pointer.

3. For add and remove operations, LinedList has an advantage because ArrayList moves data.

4.2 Time complexity comparison:

• The first key point is that the internal implementation of ArrayList is based on an underlying array of objects, so it is faster than LinkedList (O1) when accessing random access to any element in the list using the GET method. The GET method in the LinkedList is checked sequentially from one end of the list to the other (On). There is no faster way for a LinkedList to access a given element in a list

• But in some cases LinkedList performs better than ArrayList, and some algorithms are more efficient when implemented in LinkedList. For example, the performance is better when the collections. reverse method is used to reverse the list. LinkedList is also a good choice when you want to do a lot of inserts and deletions on lists.

4.3,

ArrayList and LinkedList have their own advantages and disadvantages in terms of performance. In general, they can be described as follows:

1. For both ArrayList and LinkedList, the cost of adding an element to the end of the list is fixed. With an ArrayList, it is essentially adding an entry to the internal array that points to the added element, occasionally causing the array to be reallocated. For LinkedList, this overhead is uniform, assigning an internal Entry object.

2. Inserting or deleting an element in the middle of an ArrayList means that the rest of the list is moved; The overhead of inserting or deleting an element in the middle of a LinkedList is fixed.

3. LinkedList does not support efficient random element access.

4. The space waste of ArrayList is mainly reflected in reserving a certain amount of space at the end of list, while the space cost of LinkedList is reflected in that each element of it needs to consume a certain amount of space

Suffice it to say that ArrayList provides better performance when the operation is to add data to the end of a column rather than in the front or middle, and you need to access elements randomly. Use LinkedList when you are adding or removing data in front or in the middle of a column and accessing elements in order