preface

For the record, this article uses JDK1.8

The previous article covered the overview of Collection: The Overview of Collection, which introduced some of the basics.

List subclasses List subclasses List subclasses

  • ArrayList
    • The underlying data structure is an array. Thread insecurity
  • LinkedList
    • The underlying data structure is a linked list. Thread insecurity
  • Vector
    • The underlying data structure is an array. Thread safety

This article is mainly to see how they are more important methods are implemented, what to pay attention to, and finally compare when to use which ~

It’s a good idea to start with some data structure basics: Java implements one-way linked lists, stacks and queues as simple as that, and binary trees as simple as that

Of course, if there is something wrong, please bear with me and correct me in the comments

ArrayList parsing

First, we’ll look at the ArrayList collection, which is a collection we use a lot

First, let’s look at the properties of an ArrayList:

The bottom of an ArrayList is an array, and there is a concept called expansion in an ArrayList. Because of the expansion, it can achieve “dynamic” growth

1.2 Construction method

Let’s look at the constructor to verify that we are right:

1.3 the Add method

The add method is arguably the most important method of ArrayList, so let’s take a look at it:

1.3.1 the add (E, E)

Steps:

  • Check whether the capacity needs to be expanded
  • Insert elements

First, let’s look at this method:


    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
Copy the code

The method is so short that we can guess what it does from its name:

  • Confirm the list capacity and try increasing the capacity by 1 to see if it is necessary
  • Add elements

Let’s see if this small capacity (+1) meets our requirements:

EnsureExplicitCapacity () is then called to determine the explicit capacity, and let’s see how it works:

So, how do you implement grow()

Go to the copyOf() method:

So far, we can see the basic implementation of add(E E) :

  • First check to see if the array is large enough
    • Enough: Add directly
    • If no, expand the capacity
      • Expand it by 1.5 times
      • If the capacity is still smaller than minCapacity after the first expansion, expand the capacity to minCapacity.

1.3.2 the add (int index, E element)

Steps:

  • Check the Angle of standard
  • Check space and expand capacity if necessary
  • Insert elements

Let’s look at the implementation of inserts:

We found that the add method of ArrayList related to capacity expansion is actually implemented by ArrayCopy ()

Arraycopy () is written in C/C++ and not implemented in Java:

Overall: ArrayCopy () is a fairly reliable and efficient method.

Reference R answer: www.zhihu.com/question/53…

1.4 the get method

  • Check the Angle of standard
  • Returns the element




   // Check the corner markers
   private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
	
	// Return the element
    E elementData(int index) {
        return (E) elementData[index];
    }
Copy the code

1.5 set method

Steps:

  • Check the Angle of standard
  • Alternative elements
  • Returns the old value

1.6 the remove method

Steps:

  • Check the Angle of standard
  • Remove elements
  • Count the number of moves you need to make and move
  • Set to NULL for Gc collection

1.7 Details

  • ArrayList is implemented based on dynamic arrays, which need to be copied when adding and deleting arrays.
  • The default initial capacity of an ArrayList is 10, which increases by half, or 1.5 times, each time it is expanded
  • Deleting an element does not reduce capacity; if you want to reduce capacity, call trimToSize()
  • It is not thread-safe. It can store null values.

References:

  • Blog.csdn.net/panweiwei19…
  • zhuanlan.zhihu.com/p/27878015

Vector and ArrayList

Vector is a jdk1.2 class, an older collection class.

Vector is also an array. The biggest difference between Vector and ArrayList is synchronization (thread-safe).

Vector is synchronous, as we can see from the method

In cases where asynchrony is required, ArrayList is used instead of Vector

If you want a ArrayList synchronization, can use the method of the Collections: List the List = Collections. SynchronizedList (new ArrayList (…). ); , you can achieve synchronization ~

There’s another difference:

  • ArrayList is 0.5 times larger when the underlying array is insufficient; Vector is 1 times larger. ,

Vector source code:

  • Blog.csdn.net/panweiwei19…
  • zhuanlan.zhihu.com/p/28241176

3. LinkedList parsing

If you are not familiar with LinkedList, you can take a look at my LinkedList.

Once you understand unidirectional lists, bidirectional lists are not difficult.

Structurally, we also see that LinkedList implements the Deque interface, so we can manipulate LinkedList like queues and stacks

There are only a few LinkedList variables, as we found when we were working with one-way lists: with headers, we can get all the other data. (The same goes for bidirectional lists.)

3.1 Construction method

LinkedList is constructed in two ways:

3.2 the add method

If you have done the linked list exercise, you are familiar with the following code ~

  • The add method actually adds elements to the end of the list

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

3.3 the remove method

This is actually the operation of the following diagram:

3.4 the get method

The get method is implemented in two pieces of code:

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
Copy the code

Let’s go in and see what the implementation looks like:

3.5 set method

The set method is similar to the GET method in that the index is used to determine whether to traverse from the beginning or from the end


    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

Copy the code

. There are many more methods for LinkedList than for ArrayList, but I won’t go into them here. Please refer to:

  • Blog.csdn.net/panweiwei19…
  • zhuanlan.zhihu.com/p/24730576
  • zhuanlan.zhihu.com/p/28373321

Four,

In fact, the collection source looks not very difficult, encounter problems can be turned over, should be able to understand ~

ArrayList, LinkedList and Vector are common knowledge points in interview questions. Let me make a brief summary:

ArrayList:

  • The underlying implementation is an array
  • The default initial capacity of an ArrayList is 10, which increases by half, or 1.5 times, each time it is expanded
  • The navite method is implemented by C/C++.

LinkedList:

  • The underlying implementation is bidirectional lists [bidirectional lists facilitate traversal]

Vector:

  • The bottom layer is arrays, which are now used sparingly, replaced by arrayLists, for two reasons:
    • Vector all methods are synchronous and have a performance penalty.
    • Vector starts with a length of 10 and grows at a 100% rate beyond length, consuming more memory than ArrayList.
    • Reference data: www.zhihu.com/question/31…

In summary: Query more ArrayList, add and delete more LinkedList.

The ArrayList is not absolute (in the case of large numbers, tested) :

  • If adding elements is always usedadd()If added to the end, ArrayList is faster
  • Always delete the element at the end of the ArrayList is also faster
  • As for deleting the middle position, ArrayList is still faster!

But generally speaking, use LinkedList to add or delete most of your LinkedList because it’s extreme

Open source project (6 K STAR) :Github.com/ZhongFuChen…

If you want to follow my updated articles and shared dry goods in real time, you can search Java3y on wechat.

The content of the PDF document is typed by hand. If you don’t understand anything, you can ask me directly (the official account has my contact information).