Is the LinkedList down? The author doesn’t use it himself

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

Recently, WHEN I saw some people talking about LinkedList authors who don’t even use LinkedList themselves, I looked it up on the Internet and found it.

Twitter.com/joshbloch/s…

Is God really not using his LinkedList anymore? I carefully scrubbed it, as shown in the picture below, the great god’s reply.

In fact, God is very fond of linked list data structure, in C language is very useful. And I like the implementation of ArrayDeque because ArrayDeque is probably faster than Stack when used as a Stack and faster than LinkedList when used as a queue.

But why not use LinkedList? LinkedList is a double-ended queue based on bidirectional linked lists. Linked lists and queues are very good data structures, but LinkedList has performance problems in Java, so it is rarely used in actual projects. Let’s first understand the characteristics of LinkedList.

LinkedList 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

LinkedList belongs to the chain queue, and the corresponding ArrayDeque is a two-ended queue based on array implementation. The characteristics of ArrayDeque and LinkedList data structure are shown as follows.

For more on the pros and cons of ArrayDeque and LinkedList, when they are used, and who is faster, head over to the diagram ArrayDeque is Faster than LinkedList.

Now that we understand the data structure characteristics, let’s analyze why LinkedList has performance problems from two aspects.

Performance issues with LinkedList

• 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

In the last article, ArrayDeque was illustrated that ArrayDeque was faster than LinkedList. The performance of ArrayDeque was better than LinkedList from both speed and memory, and the results were verified in combination with actual cases, as shown in the figure below.

In the previous article, I wrote four articles around linkedLists (stacks, queues, and so on), analyzing them from different perspectives.

• | algorithm animation diagrams are “abandoned” Java stack, why still use

  • The definition of the stack
  • The realization of the stack
    • Why not use the Java stack
      • The performance is low
      • The original data structure is broken
    • It’s not recommended anymore. Why is it still used
    • Why recommendedDequeInterface replacement stack
      • Faster efficiency than Java stacks
      • Block out irrelevant methods
    • Stack and ArrayDeque
    • Time complexity of the stack
  • The stack of actual combat

• Why not recommend ArrayDeque instead of Stack

  • Why not use the Java stack
  • JDK recommended useArrayDequeInstead ofStackIs that really reasonable?
  • Great God is not recommendedArrayDequeInstead ofStack
  • How to implement a true stack

• Diagram ArrayDeque is faster than LinkedList

  • ArrayDeque 和 LinkedListData structure characteristics?
  • whyArrayDeque 比 LinkedListFast?

• Follow the source data structure | circular queue

  • Basically, how do you design a loop queue
  • How does the JDK source code design queues?
  • Why is the queue size set to an integer power of 2?
  • How much faster is bitwise operation than non-bitwise operation?
  • What is the difference between ArrayDeque’s integer power of 2 calculation logic and HashMap?
  • How do I design a loop queue?

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

• Oracle recommends the details of using ReentrantLock
• Kotlin announced a blockbuster feature
• Google has announced the abandonment of the LiveData.observe method
• One detail to note when using Kotlin
• Follow the source data structure | circular queue
• Diagram ArrayDeque is faster than LinkedList
• 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