Java basic collection article -List

preface

In fact, this basic article was originally written for a long time, the content is a bit redundant, because I always want to explain every source code clean, but I believe that you have the ability to read it. Comprehensive consideration or for most of the simple source code are CV, a small part of the source code to explain.

Java collections are often used for job interviews, test reading, and work. Leaving Iterable aside, starting at the Collection level, the entire Java Collection is divided into Collection and Map categories.

Under the Collection interface, there are three interfaces: List, Queue, and Set. For List, this article describes four commonly used classes: Vector, Stack, ArrayList, and LinkedList.

A List simply accesses an ordered collection, has an index value, and the elements can be repeated.

ArrayList

Structure and constructors

Looking at the source code, you can see that the underlying ArrayList uses elementData to store data.

For the constructor of an ArrayList, it’s all about constructing elementData

1. ArrayList(int initialCapacity)

   

   If you have an initial size, create a new array. 0 is an empty array, to be initialized when the first add; Less than 0 simply throws an exception

2. ArrayList()

   

   The empty constructor constructs an empty array

3. ArrayList(Collection<? extends E> c)

   

   If the type of the collection passed in is ArrayList, the assignment can be done directly; otherwise, the assignment can be done by Array.CopyOf.

The processing of the data, must be inseparable from the addition, deletion and change check, so in this article mainly tells the story of several very common methods, as for other individual methods, you can see the source partners themselves.

Add elements

So when we insert an element we need to do a check on the capacity ensureCapityInternal (size + 1)

Calculate the capacity calculateCapacity(elementData, minCapacity)

Call EnsureExplicitCapacity (int mincapCity) when the volume is calculated

/ grow(minCapacity); / grow(minCapacity); / grow(minCapacity); / grow(minCapacity)

There are many boundary judgments, including HugeCapacity (minCapacity) which is actually a boundary judgment

The important point is that we can see that the capacity of the expanded array is 1.5 times of the old capacity, and the whole expansion is to use Arrays.CopyOf (ElementData, NewCapacity) for data migration.

In addition to the add method, there are many other methods that begin with add

Add (int index, Integer element)

Everything else is the same, but the code for data migration is different because you need to insert elements at a particular location. The remaining two method code is not posted, or even their own implementation can be, the core is data migration.

delete

For deleting, there are two overloaded methods, one for deleting a subscript element and another for deleting a specific element.

First get the value of the element to delete the subscript; If the subscript is not the last one, then the same data migration can be used; If the subscript is the last one, then simply set the last element to null, which also facilitates Garbage collection.

For deleting a particular element

You can find operations such as the decision to discard an object, and the core function is fastRemove(Index).

Not unrelated to the code that removes a particular index, but identical.

We need to make a pit here, so when we save the wrapper type, and when we delete it, we pass in the base type, and we call the delete subscript function; To call a function that removes an element, you need to cast it.

Modify the

The query

Find the subscript of a particular element

This is nothing to say, is to traverse one by one, find the elements you want, in order to be more efficient, you can even consider modifying the source code, using binary search, but the amount of data used ArrayList access is generally not very large, the efficiency is not obvious.

If you look for the last index of an element, you just go backwards.

You get some subscript element

LinkedList

Structure and constructors

It’s worth noting that LinkedList implements both the List interface and the Deque, and this article only discusses the part that implements the List interface.

LinkedList is a bidirectional LinkedList made up of multiple nodes

public LinkedList() {
}

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

Two constructors, but the latter also takes an empty constructor and calls the addAll method to add the element.

The construction of Node nodes is also something to learn

increase

The addition is to get the last element, and then maintain the node relationship.

As mentioned earlier, in other cases there are two important functions linkBefore and node, the latter of which is reserved for query analysis.

Find the node, and then maintain the same node relationship.

There’s another way to add another set, and there are two ways.

Simply inserted at the end of the situation is not said, mainly said the following winning the number of the situation

delete

The code to delete an object is as follows

The code to delete a subscript is as follows. It will be the same. You have to find the object based on the subscript, and then call the code above to delete the object

So now the important thing is to get to the UNLINK method

Modify the

It’s very simple, just find the node and replace the item.

The query

Query node

Remember, we said that node is a node that gets a certain index, so let’s see what that is.

Maybe if you give your friends, the first impression is to start from the beginning, and then look back. If the index is less than half, start from first, otherwise start from last and go forward.

Query the subscript

(index = 0); (index = 0); (index = 0);

If you want the last index, you just go backwards and forwards, and then the variable you maintain is index = size, decrement by one each time

Vector

Vector, which also uses arrays to store data, is a thread-safe version of ArrayList, and all implementations are similar

As you can see, the synchronized keyword is added to the method body for thread-safety. Another difference is the implementation of capacity expansion.

You can see that instead of the ArrayList growing 1.5 times, the Vector is growing 2 times.

Stack

If you look at the source code, Stack inherits from Vector, so it also uses arrays to store elements, and all operations are based on arrays.

All the methods on the stack are here, but it’s basically the same. Take a look at the source code for push()

Will be calling addElement (item)

So we go back to the implementation of arrays, which we talked about in the analysis of ArrayList, we didn’t even have to do any analysis, we just had a simple array to store the data.

conclusion

A List stores a non-unique (multiple elements can refer to the same object), ordered array of objects, divided into ArrayList, LinkedList, Vector, and Stack.

ArrayList is the use of array to achieve, suitable for RandomAccess and traversal (you look at the source code found that ArrayList implementation RandomAccess interface, but this interface is an empty implementation, it is estimated to be just a mark) but not suitable for adding and removing, is thread unsafe.

LinkedList stores data in a bidirectional LinkedList structure. In general, LinkedList can be used as a queue, a bidirectional queue and a stack. Because of the structure of the linked list, it is more suitable for adding and deleting, and the efficiency of random access and traversal is relatively low.