Enjoy the view first

ArrayList, ArrayList, ArrayList, ArrayList, ArrayList, ArrayList, ArrayList, ArrayList

List and Set interface inherit from Collection interface (Map interface and Collection interface are not related)

Because brother Wet want to give you posted some source code to analyze, so an article certainly liver not over, this is the main liver linkedList, the rest of the Map and Set below continue liver ~

No matter in work or interview, collection is the most common. I don’t believe you haven’t been asked about collection in school recruitment. I don’t believe you can’t use collection in work, just don’t believe it.

To understand

Collection and Map are two highly abstract interfaces:

  • Collection abstracts the Collection and contains the basic operations and attributes of the Collection. Collection mainly contains the List and Set branches.

  • A List is an ordered List that allows the storage of repeated elements. The main implementation classes of a List are LinkedList, ArrayList, Vector, and Stack.

  • A Set is a collection of non-repeating elements, and the main implementation classes of a Set are HastSet and TreeSet (which rely on hash implementations, described below).

A collection is a container used to store multiple objects in Java. We know that container arrays are immutable in length and can only store elements of the same type. They can store primitive types or reference types. Collections are variable in length, can store elements of different types (but we don’t usually do that), and can only store reference types (primitive types become wrapper classes).

Fail-fast and Fail-safe mechanisms for collections:

  • Fail – fast quick failure mechanism, A thread A when using iterators iterate through the set, another thread B to modify the collection can lead to A rapid failure at this moment, throw ConcurrentModificationException. Collection classes in java.util fail fast.

  • Fail-safe A fail-safe mechanism that replicates a set and traverses the copied set instead of the original set. Container classes under the java.util.concurrent package are securely failed, and collection classes under this package are recommended for concurrent environments.

Fail-fast **** Fast failure is achieved by using a modCount variable during the traversal. Before each traversal, the modCount variable is checked to see if it is the same as the expected value. If so, the traversal is terminated by throwing an exception.

LinkedList

The source part of the first declaration, there is my CSDN website watermark, personal original, no plagiarism, we are free to watch ~~

LinkedList defined:

  public class LinkedList<E> extends AbstractSequentialList<E> 
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}
Copy the code

LinkedList introduction:

  • LinkedList is a bidirectional LinkedList implementation of the List interface and allows all elements, including null. The Deque is a two-way queue, which means that the LinkedList is also an implementation of a two-way queue. We can manipulate the LinkedList like queues and stacks.

  • A bidirectional list is an instance of a Node that contains member variables: prev, Next, and item. Where, prev is the last node of this node, next is the next node of this node, and item is the value contained in this node, so the insertion speed is fast (the time complexity is O(1), but the time complexity of determining the position before insertion also becomes O(n)), and only the pointer of the front and back nodes need to be moved.

  • LinkedList is ordered and can contain repeating elements, not thread-safe.

  • The LinkedList’s chained storage structure is more efficient than the contiguous storage of arrays, and the query is relatively slow because the next pointer needs to be traversed from the head node or tail node for each query.

LinkedList source code:

Let’s start with the attribute ~

Constructor (understand)

      /**       * Constructs an empty list.       */   
   public LinkedList() {      }   
   public LinkedList(Collection<? extends E> c) {  
      this();     
   addAll(c); 
     }
Copy the code

Inner class nodes are the actual nodes where the actual elements are stored

Add function: adds the specified element to the end of the list.

**linkLast()**

Here is an example illustration and schematic:

  List<Integer> lists = new LinkedList<Integer>();  lists.add(5);  lists.add(6);
Copy the code

Note: As shown in the figure above, after the addition of element 5 and elements, the pre pointer of 5 is null (representing first), then the next pointer points to 6 (representing last), and then the next pointer at the end is also null. When performing the process of adding elements, the last node is first saved as final and then a new node is created. The pre pointer points to the last node, and then the last pointer points to the new node to re-assign the last node.

AddAll () : Adds a Collection, as shown in the figure below. AddAll has two overloaded functions, but both are converted to addAll(int, Collection
) this, so let’s examine this function;

Addendum: Step 2 involves a node() function that finds the element by index and returns it. Index < (size >> 1) is used to determine whether the index belongs to the first half of the LinkedList or the second half of the LinkedList.

The get() function: uses the node function above to locate the node.

Summary: the underlying data structure of LinkedList is based on a two-way circular LinkedList, and there is no data stored in the header. Add, delete, and modify operations in LinkedList are all performed by manipulating Pointers of nodes, so it is easier to insert and delete operations and more efficient. An ArrayList is less efficient because many array elements need to be moved around.

Key issues:

In addAll(), why pass a collection into an array and then iterate over the array, adding elements to the array instead of iterating over the collection directly?

The above screenshot is the official explanation. The purpose of toArray is to ensure that the Collection passed in will not be referenced anywhere, and that the Collection will not have any chance to be modified (i.e. the contents of the Collection will change during the addAll process), so as to ensure the security of data.

Analyze the LinkedListtraverseWay?

Iterators and list iterators

Iterator iterator=list.iterator();  //ListIterator<Student> iterator=list.listIterator();  while(iterator.hasNext()){     System.out.println(iterator.next());   }
Copy the code

2, fast random (there will be serious efficiency problems, see the following analysis, strongly not recommended to use!!)

for(int i=0; i<list.size(); i++){ System.out.println(list.get(i)); }Copy the code

3. Use enhanced for traversal

for(String str:list){        System.out.println(str);      }
Copy the code

PollFirst pollLast removeFirst removeLast pollFirst removeLast pollFirst removeLast pollFirst removeLast pollFirst removeLast pollFirst removeLast pollFirst removeLast pollFirst removeLast

while(list.pollFirst() ! = null)//while(list.pollLast() ! = null)//while(list.removeFirst() ! = null)//while(list.removeLast() ! = null) { }Copy the code

Parsing traversal: The list function removeFist or removeLast traversal is efficient, but removes the original data after traversal. There are many problems with the fast random (size traversal loop) traversal method of list. Why? Watch:

If less test data of time may find it’s not a problem, but we will find the data as the amount of data to increase significantly the card phenomenon, we have analyzed in front of the get () method, and its internal node () method (used to locate the position of the element), will decide if the current element is in the first half or the second half of the list and decide which side from the traversal, Then, when fetching data, no matter where the target element is, it will traverse from the head node or tail node to the target node and then remove the data.

If there are 10 elements in the list that need to be traversed, the number of queries for each element is (1,2,3,4,5,5,4,3,2,1) and the total number of queries is 30, and the time complexity approaches O(n^2) as n approaches infinity. When the number of targets n is larger, the time complexity increases faster, resulting in program false death.

Therefore, it is highly recommended that you do not use size loops to iterate over data, and that you use traversers or foreach for efficiency.

How does LinkedList provide the ability to retrieve data by location, and is it really very inefficient to query?

LinkedList is actually implemented through a two-way LinkedList. Since it is a bidirectional list, sequential access is very efficient, while random access is less efficient. The greatest benefit of LinkedList is that the insertion and deletion time complexity of both header and tail and known nodes is O (1).

However, in the case of locating first and then operating, the time complexity becomes O (n), because locating the LinkedList requires either the beginning node or the end node to loop. Of course, the need to keep prev and next Pointers for each node is often mocked as a waste of space.

How is it used as a stack, queue, or double-endian queue?

As shown in the figure above, the Deque interface is implemented and LinkedList can be used as a queue or double-endian queue because it is implemented. (The specific implementation method does not say, according to the queue and stack structure to achieve, I believe that smart people will certainly ~)

What if LinkedList is not thread-safe?

Why are threads unsafe? Thread safety is caused by multiple threads writing to or reading from the same resource at the same time.

Solution ~

1, the Collections. SynchronizedList (new LinkedList ()); See the analysis in ArrayList above, which also appears: iterators returned by iterator() and listIterator() are fail-fast and require manual synchronization;

Change to ConcurrentLinkedQueue or LinkedBlockingQueue, which supports adding elements to atomic operations. LinkedBlockingQueue uses a lock mechanism. ConcurrentLinkedQueue uses CAS (optimistic lock), but LBQ also uses CAS for the underlying lock acquisition.

Methods such as put of LinkedBlockingQueue are operations to add element atoms using ReentrantLock. Let’s look at the add and offer() methods, which use CAS to implement lock-free atomic operations:

ConcurrentLinkedQueue is definitely the fastest in terms of insert element performance. In practice, especially on multi-CPU servers, the difference between locked and unlocked elements can be seen. ConcurrentLinkedQueue is much faster than LinkedBlockingQueue.

Analyze where ArrayList and LinkedList are applicable

1. ArrayList is superior to LinkedList if the application has more random access to the data;

2. LinkedList is superior to ArrayList if the application has more inserts or deletions and less data reads;

3. ArrayList insertion and deletion are not necessarily slower than LinkedList insertion. If insertion is near the end of List, ArrayList only needs to move less data, while LinkedList needs to search all the way to the end of List, which takes more time. ArrayList is faster than LinkedList.

** Summary: ** In fact, the usage scenario should be analyzed in detail, according to the characteristics of ArrayList and LinkedList to analyze which one needs to be applied.

Vector

The Vector definition:

public class Vector<E> extends AbstractList<E>   implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
Copy the code

The Vector profile:

  • Vector inherits AbstractList and implements List, so it is a queue that supports adding, deleting, modifying, traversing, etc.

  • Vector is thread-safe and can also be considered a thread-safe ArrayList because many of its internal functions are ArrayList functions with the Synchronized keyword, but this makes Vector less efficient.

  • In a Vector, we can get an element object quickly by its ordinal number. This is called fast random access.

Vector core functions:

Much of the source code inside Vector is similar to that of ArrayList. If you are interested, you can study it yourself

Key issues:

The bottom layer is arrays, which are now rarely used, replaced by arrayLists.

  • All Vector methods are synchronized, which is never required and incurs a performance penalty.

  • Vector starts with a length of 10 and grows at a rate of **100%** over length, consuming more memory than ArrayList.

Stack

Stack definition:

 class Stack<E> extends Vector<E> {}
Copy the code

The Stack profile:

  • A Stack is a Stack, inherited from a Vector. Its features are: FILO, First In Last Out.

  • Since Vector is implemented as an array, this means that Stack is implemented as an array, not a list.

  • The Stack class is a Stack, but actually this class is not used much, but it implements a Stack structure that is often used, which we will explain in detail in the data structure section.

Flocculant on

The more you know, the more you don’t know.

Suggestion: This is LinkedList, one of the common collection classes. The Java base collection is the darling of interviews and the most commonly used tool class in our work. Many students may be a variety of sets and the underlying principle to do meng force, in fact, we use a few times, look at the source code several times, found, but so ~

If you think it is good, you can give attention to the captain, and you are also welcome to recommend it to your friends. Forwarding and liking can give Shi Brother more encouragement