LinkedList source code analysis

1. Structure

1. Succession

  this class inherits from abstractsequentiallist because it is a sequential list, so it inherits a sequential list

2. Realization

This class implements many interfaces, as follows:

3. Main fields

1. Attribute field

    transient int size = 0;
    //指向链表的头指针和尾指针
    transient Node<E> first;
    transient Node<E> last;

2. Node

The node node is the main place to store data. The data structure of this node is also relatively simple, that is, a generic type plus a precursor and successor pointer. That is, a two-way linked list.

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

4. Overview of main methods

2. Analysis of construction method

There are only two construction methods. One is the default empty structure, that is to generate an empty LinkedList, and the other is to accept a collection interface. Putall method is called inside.

    public LinkedList() {
    }

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

3. Analysis of main methods

1. add

This method directly calls linklast, which directly adds the element to the end of the element.

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

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

2. addFrist/Last

The above two methods call linkfirst and linklast, so these methods for adding and modifying are basically implemented by the same method at the bottom.

public void addFirst(E e) {
   linkFirst(e);
}

public void addLast(E e) {
   linkLast(e);
}

3. addAll

We have also seen this method in the construction method. When implemented in it, like ArrayList, it directly converts the collection into an array, and then creates a new node to insert.

public boolean addAll(int index,Collection<? extends E> c) {
       checkPositionIndex(index);

       Object[] a = c.toArray();
       int numNew = a.length;
       if (numNew == 0)
           return false;

       Node<E> pred,succ;
       if (index == size) {
           succ = null;
           pred = last;
       } else {
           succ = node(index);
           pred = succ.prev;
       }

       for (Object o : a) {
           @SuppressWarnings("unchecked") E e = (E) o;
           Node<E> newNode = new Node<>(pred,null);
           if (pred == null)
               first = newNode;
           else
               pred.next = newNode;
           pred = newNode;
       }

       if (succ == null) {
           last = pred;
       } else {
           pred.next = succ;
           succ.prev = pred;
       }

       size += numNew;
       modCount++;
       return true;
   }

4. indexOf

This method uses for loop traversal. When traversing, it starts from the node. As long as it finds the element, it returns immediately without continuing.

public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

5. lastIndexOf

This method is implemented in the same way as the above method, but note that this method means to find the last matching element. It does not find it from scratch, but directly traverse from the tail node. In the same way, stop when you find it.

6. peek/peekFirst/peekLast

The peek method means to return the topmost element. If this element does not exist, it will directly return null. Then there are peekfirst, which means to return the first one. The bottom layer calls the properties of the header node. In fact, these methods do not exist in the collection interface, mainly because they implement the new features brought by deque.

7. poll/pollFirst/pollLast

Poll is used to delete the header node and return it. If it does not exist, it returns null. The same is true for the remaining two methods.

8. offer/offerFirst/offerLast

Insert header node.

9. push/pop

The underlying methods are addfirst and removefirst

10. remove(noargs)/remove(E e)

The parameterless call removefirst has parameters to find and delete.

11. read/writeObject

Here, it is serialized manually with ArrayList. When serializing, only the elements in the node are serialized, and the predecessor and successor are directly omitted, which is also an idea to save space.

4. Summary

OK, in fact, based on a complete understanding of ArrayList, it is easier to understand this article, and the operation is simpler. Just pay attention to the difference between the two and realize many new methods brought by deque.