Collection series List LinkedList analysis

LinkedList is a classic implementation of LinkedList, and its underlying implementation is implemented in the form of LinkedList nodes.

As you can see from the class inheritance structure diagram, LinkedList implements not only the List interface, but also the Deque bidirectional queue interface.

The principle of

To understand how LinkedList works, we’ll go through class member variables, constructors, and core methods.

Class member variable

// list size transient int size = 0; // Transient Node<E> first; <E> last; //Node 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 code

It adopts the method of linked list nodes, and each node has a precursor and successor nodes.

A constructor

There are two constructors of LinkedList:

public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
}
Copy the code

Core method

At the heart of linkedList are the search, insert, delete, and expand methods.

To find the

LinkedList is based on a linkedList structure and does not randomly access elements in a given location as an ArrayList does. The linkedList lookup is a bit more cumbersome, going back from the top (or bottom) node of the list in O(N) time.

public E get(int index) { checkElementIndex(index); return node(index).item; } Node<E> node(int index) { // assert isElementIndex(index); If (index < (size >> 1)) {Node<E> x = first; // loop back until I == index 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; return x; }}Copy the code

The above code is relatively simple, mainly through traversal to locate the target location of the node. After obtaining the node, retrieve the value stored by the node and return it. There is a small optimization, which is to compare index with the number of nodes size/2 to determine whether the head node or the tail node is searched.

insert

In addition to implementing List interface related methods, LinkedList also implements many methods of the Deque interface, such as addFirst, addLast, offerFirst, offerLast, etc. But the idea is pretty much the same, so here’s how to implement the Add method.

Add has two methods, one is directly to the end of the queue, the other is to insert the specified position.

Straight into the back of the line

public boolean add(E e) {
        linkLast(e);
        return true;
}
Copy the code

You can see that it calls the linkLast method directly, which is actually a method of the Deque interface.

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 code

The code above creates nodes, changes references, and finally increases the list size.

Insert into the specified position

public void add(int index, E element) { checkPositionIndex(index); LinkLast (element); if (index == size) LinkBefore (Element, node(index)); }Copy the code

If we insert at the end of the list, the linkLast method is still called. Otherwise, the node method is called to fetch the node at the insertion position; otherwise, the linkBefore method is called to insert.

void linkBefore(E e, Node<E> succ) { // assert succ ! = null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }Copy the code

The code above creates nodes, changes references, and finally increases the list size.

delete

There are two ways to remove a node. The first is to remove a specific element, and the second is to remove an element at a location.

Let’s start with the first deletion method: remove a specific element.

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; }Copy the code

Iterate to find the deleted node, then call unlink() to dereference it.

E unlink(Node<E> x) { // assert x ! = null; 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 code

The unlink() code makes a series of reference changes.

conclusion

After the above analysis, we can know that the LinkedList has the following characteristics:

  • The bottom layer is realized based on linked list, which is fast to add and delete and slow to read
  • Not thread-safe.
  • Unlike ArrayList, LinkedList has no capacity limit, so there is no capacity expansion mechanism.

More information articles, public number “Java Road”