Hi everyone, I am DHL. Public number: ByteCode, focus on sharing the latest technology original articles, involving Kotlin, Jetpack, algorithm animation, system source code, LeetCode/point Offer/multithreading/domestic and foreign large factory algorithm problems and so on.

The previous two articles focused on the disadvantages of the Java Stack, why it is not recommended to use it, and why ArrayDeque is not recommended to replace the Java Stack directly. For more, click the link below.

  • | algorithm animation diagrams are “abandoned” Java stack, why still use
  • Why not recommend ArrayDeque instead of Stack

ArrayDeque, a subclass of interface Deque, is faster as a Stack than Stack because the original Java Stack inherits from Vector, which locks each method. The subclass of Deque, ArrayDeque, has no lock overhead.

Interface Deque has another subclass LinkedList. LinkedList is a two-ended queue based on a two-way LinkedList implementation, and ArrayDeque may be faster than LinkedList when used as a queue.

This article will analyze why ArrayDeque is faster than LinkedList. Before we begin our analysis, we need to take a brief look at the characteristics of their data structures.

Interface Deque

The interface Deque is derived from Queue, i.e. Queue. In Java, queues have two forms, AbstractQueue and Deque. The effect of a one-way Queue is shown below.

Today, we will mainly introduce a Deque. A Deque is a linear data structure of a double-ended queue. It can be inserted and deleted at both ends, as shown below.

The subclasses of Deque are ArrayDeque and LinkedList respectively. ArrayDeque is based on the dual-ended queue implemented by array, while LinkedList is based on the dual-ended queue implemented by bidirectional LinkedList. Their inheritance relationship is shown in the figure below.

Interface Deque and Queue provides two sets of apis, there are two forms, an exception is thrown, respectively, and is not an exception is thrown, return a special value null or Boolean value (true | false).

Operation type An exception is thrown Return special value
insert addXXX(e) offerXXX(e)
remove removeXXX() pollXXX()
To find the element() peekXXX()

ArrayDeque

ArrayDeque is a two-ended queue based on (looping) arrays with an initial capacity of 16 (JDK 8), as shown below.

ArrayDeque has the following characteristics:

  • Because double-ended queues can only insert or delete elements at the head and tail, the time complexity isO(1), but elements need to be moved in batches during capacity expansion, and its time complexity isO(n)
  • During capacity expansion, the array length is doubled, i.en << 1
  • The array uses a contiguous memory address space, so when querying, the time complexity isO(1)
  • It is a non-thread-safe collection

LinkedList

LinkedList is a two-ended queue based on a two-way LinkedList implementation, and its structure is shown below.

LinkedList has the following characteristics:

  • LinkedListIs based on the structure of the bidirectional linked list to store elements, so there is no limit to the length, so there is no expansion mechanism
  • Since the memory address of the linked list is discontinuous, the elements can only be searched from the head or tail, and the query time is complexO(n), but the JDKLinkedListWe optimized it so that when we look for something, ifindex < (size / 2), fromheadLook behind, or fromtailLet’s go ahead, but when we calculate the time complexity, the constant term can be omitted, so the time complexityO(n)
Node<E> Node (int index) {// size >> 1 equivalent to size / 2 if (index < (size >> 1)) {// form head to tail} else {// form tail to head } }Copy the code
  • Linked lists access each element through Pointers, so the insertion and deletion of elements only need to change the pointer pointing, so the insertion and deletion of time complexityO(1)
  • It is a non-thread-safe collection

Finally, the characteristics of ArrayDeque and LinkedList are summarized as follows:

Collection types The data structure Initialization and capacity expansion Insert/delete time complexity Query time Complexity Thread safe or not
ArrqyDeque Circular array Initialization: 16

Capacity expansion: 2 times		 0(n) O (1) no
LinkedList Two-way linked list There is no O (1) 0(n) no

Why is ArrayDeque faster than LinkedList

With data structure characteristics behind us, let’s look at two aspects of why ArrayDeque might be faster than LinkedList when used as a queue.

  • From the perspective of speed: ArrayDeque implements a double-ended queue based on an array, while LinkedList implements a double-ended queue based on a bidirectional LinkedList. Arrays use a continuous memory address space that is accessed by subindex, while linked lists are discontinuous memory address Spaces that are accessed by Pointers, so arrays are more efficient than linked lists in addressing.

  • From a memory point of view: Although there is no problem with LinkedList expansion, when an element is inserted, a Node object needs to be created. In other words, a new operation is performed every time. When a new operation is performed, the process is very slow and goes through two processes: class loading and object creation.

    • Class loading process

      • Determines whether the class has been initialized, and if not, the class loading process is performed
      • The loading process of a class: the loading, validation, preparation, parsing, initialization phases, and so on, are then executed<clinit>()Method, initialize static variables, execute static code blocks, and so on

    • Object creation process

      • If the class is already initialized, the object creation process is performed directly
      • Object creation process: create a block of heap memory, allocate an address to the open space, perform initialization, will execute<init>()Method to initialize a normal variable and call a normal code block

Next we | the algorithm animation diagrams are “abandoned” the Java stack, why still use article LeetCode algorithm: effective parentheses, to verify their speed of execution, and in the memory overhead, the code is as follows:

class Solution { public boolean isValid(String s) { // LinkedList VS ArrayDeque // Deque<Character> stack = new LinkedList<Character>(); Deque<Character> stack = new ArrayDeque<Character>(); // start traversing the string for (int I = 0; i < s.length(); i++) { char c = s.charAt(i); / / had left parenthesis, press the corresponding right parenthesis into the stack of the if (c = = '(') {stack. Push (')); } else if (c == '[') { stack.push(']'); } else if (c == '{') { stack.push('}'); } else {/ / right parenthesis, judge whether the current element and stack elements are equal, not equal to return early, the end of the cycle the if (stack. The isEmpty () | | stack. The poll ()! = c) { return false; }}} return stack.isempty (); }}Copy the code

As you can see, the core algorithms are all the same, accessed through the interface Deque, but the code to initialize the interface Deque is different.

<Character> stack = new LinkedList<Character>(); <Character> stack = new ArrayDeque<Character>();Copy the code

As you can see, ArrayDeque outperforms LinkedList both in terms of execution speed and memory overhead.


A “like” would be the biggest encouragement if it helps

More code, more articles

Welcome to the public account: ByteCode, continue to share the latest technology


Finally, recommend long-term update and maintenance projects:

  • Personal blog, will all articles classification, welcome to check hi-dhl.com

  • KtKit compact and practical, written in Kotlin language tool library, welcome to check KtKit

  • Androidx-jetpack-practice androidX-Jetpack-practice androidX-Jetpack-practice androidX-Jetpack-Practice androidX-Jetpack-Practice

  • LeetCode/multiple thread solution, language Java and Kotlin, including a variety of solutions, problem solving ideas, time complexity, spatial complexity analysis

    • Job interview with major companies at home and abroad
    • LeetCode: Read online

Must-read articles these days

  • Why not recommend ArrayDeque instead of Stack
  • | algorithm animation diagrams are “abandoned” Java stack, why still use
  • Kotlin code affecting Performance (1)
  • Jetpack Splashscreen parsing | power generation IT migrant workers get twice the result with half the effort
  • Kotlin’s Technique and Analysis (3)
  • Kotlin’s Technique and Principle Analysis that few people know (II)
  • Kotlin’s Technique and Principle Analysis that few people know (1)
  • Uncover the == and === in Kotlin
  • The Kotlin hermetic class evolved
  • The sealed class in Kotlin is superior to the tagged class
  • What is Kotlin Sealed? Why does Google use it all
  • Android 12 behavior changes that affect applications
  • AndroidStudio
  • Kotlin StateFlow search features practice DB + NetWork
  • The end of the Kotlin plugin and the rise of ViewBinding