This article is participating in the Java Theme Month – Java Debug Notes EventActive link

Following on from ArrayList, we’re going to talk about the List family code, and today we’re going to look at LinkedList, and as members of the family LinkedList and ArrayList are used in different scenarios, they shine in their own domains, Speaking of which, I actually think it’s time to throw up the first question of this article, when should we use ArrayList and when should we use LinkedList? .

The data structure

We all know that the data structure of an ArrayList is an array, but what is the data structure of a LinkedList? 1. All of the operations perform as could be expected for a newly-linked list. In short, everything behaves like a double-linked list, and the code structure is as follows.

// Initial capacity
transient int size = 0;
// A pointer to the previous one
transient Node<E> first;
// a pointer to the next one
transient Node<E> last;
Copy the code

It can be seen that there are two Pointers to the nodes of first and last respectively, which is a typical structure of bidirectional linked list. As for transient, we will supplement and expand it in the following chapters of basic knowledge of multi-threading.

The diagram above illustrates this structure well.

Key source

In fact LinkedList implementation is not much to discuss, is a more complete double LinkedList operation class, here we focus on new and query.

new

In this case, the operation of adding, deleting and modifying a double linked list is actually the operation of adding, deleting and modifying a double linked list.

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

Above is the new code, which relies on the linkLast implementation. The implementation principle is very simple, is to add a data at the end of the list, and use a pointer to associate.

void linkLast(E e) {
  	// Get the tail pointer
    final Node<E> l = last;
    // Create a pointer based on the data
    final Node<E> newNode = new Node<>(l, e, null);
    // New node access pointer
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    // This is why LinkedList and arrayList are not supported.
    modCount++;
}
Copy the code

The reason why concurrency is not supported is that modCount changes in all operations. If multiple threads are operating, modCount changes irregularly. In ArrayList and LinkedList, modCount values are checked before certain operations are performed. If the check is not through will throw ConcurrentModificationException.

The query

Node<E> node(int index) {
    // assert isElementIndex(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 code

Pictured above is a find corresponding node according to the index method, can be very straightforward to see a problem, that is what I find a node energy is very big, although has done binary (index > 1/2 * size, begin from the tail pointer iteration), but the efficiency is too low, if I have 1 w a node, And the node I’m looking for is 5001 digit? So we can see from this that LinkedList is not a good place to store data that requires frequent lookups.

Finally, I can answer the question I raised at the beginning of this article. LinkedList’s data structure is a LinkedList. Linked lists have the advantage of being quick to add and delete, especially bidirectional lists, whereas arraylists are arrays. So to sum up:

  • ArrayList is used when there are many queries but few inserts and deletions.
  • LinkedList is used when there are fewer queries and more inserts and deletions.

conclusion

That said, the thread-safe brothers of the List family are done, and the next article is to analyze Vector, a thread-safe collection framework that is essentially the same as ArrayList, The only difference is that vectors use the synchronized keyword to ensure thread-safety, which will be covered in this thread series. Thank you for reading.