search
HomeJavaJavaInterview questionsA question asked in almost all Java interviews: talk about the difference between ArrayList and LinkedList

Preface

Hello everyone, I am your old friend Qing Ge. I know you miss me, so I am here again Really?

The data structure of Java is the focus of the interview. I believe that students who have participated in Java interviews will have some experience. When interviewers ask such questions, they often want to check whether you have studied the underlying structures of commonly used data types in Java, rather than simply staying at the level of "knowing how to use". So how do we answer this question well during the interview and satisfy the interviewer?

In this issue, I will analyze the principles of Java high-frequency test points ArrayList and LinkedList, hoping to help you.

Introduction to ArrayList and LinkedList

ArrayListThe bottom layer is an array of type Object. The initial The capacity is 10 and supports dynamic expansion. The expanded capacity is 1.5 times the current capacity. Its maximum capacity is Integer.MAX_VALUE - 8 (but it can still be expanded to Integer.MAX_VALUE). For the vacated 8 bits, the current explanation is It isavoiding some machine memory overflows and reducing the chance of errors.

LinkedListThe bottom layer is a two-way linked list with an initial capacity of 0. To expand the capacity, you only need to create a new node and point the pointer to it.

In order to simplify it into verbally expressable language and facilitate students to explain to the interviewer during the interview, I will not post the source code auxiliary instructions here. Interested students can check the source code themselves. Internal structures and methods to deepen your understanding of this area.

Difference

Query

  • ArrayList random access is very efficient because the elements are stored in order. You can know the location of the queried data in the memory through the subscript index. The addressing is fast and the time complexity is O(1);
  • LinkedList query efficiency is low. When querying the specified data, it needs to traverse the linked list one by one, and the time complexity is O(n).

Insertion

  • ArrayList inserts at the end more efficiently, with a time complexity of O(1), but in Insertion efficiency at other positions is relatively low, requiring a large amount of data movement, and the time complexity is O(n);
  • LinkedList is more efficient at inserting elements at the head and tail, and the time complexity is complex The degree is O(1), but to insert an element at a specified position in the middle, you need to traverse to find the position of the element first, and then insert it. The time complexity is O(n).

Delete

  • Removing elements from ArrayList requires a large amount of data movement except for the end node. Time complexity O(n);
  • LinkedList is relatively efficient in deleting elements. It only needs to change the pointing of the pointer, but deleting elements requires traversing to query the location of the data, and the time complexity is O (n).

Memory space

  • ArrayList is implemented based on arrays. The capacity is fixed after each expansion, so there will be Reserve a part of the space;
  • LinkedList is based on a doubly linked list, so in addition to saving data, each node also needs to save the pointers of the previous and next nodes, which will consume some space.

Expansion mechanism

  • Every time ArrayList is expanded, the elements of the original array need to be copied to the new array;
  • LinkedList is a linked list and there is no expansion.

Same points

Thread safety

ArrayList and LinkedList are both thread-unsafe and can easily cause dirty reading problems in multi-threaded environments. You can use the Collections.synchronizedList() method to ensure thread safety

Storage Features

The stored elements are all ordered and can be repeated. New elements are stored at the end of the List.

The above is the detailed content of A question asked in almost all Java interviews: talk about the difference between ArrayList and LinkedList. For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:Java学习指南. If there is any infringement, please contact admin@php.cn delete
带你搞懂Java结构化数据处理开源库SPL带你搞懂Java结构化数据处理开源库SPLMay 24, 2022 pm 01:34 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于结构化数据处理开源库SPL的相关问题,下面就一起来看一下java下理想的结构化数据处理类库,希望对大家有帮助。

Java集合框架之PriorityQueue优先级队列Java集合框架之PriorityQueue优先级队列Jun 09, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

完全掌握Java锁(图文解析)完全掌握Java锁(图文解析)Jun 14, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于java锁的相关问题,包括了独占锁、悲观锁、乐观锁、共享锁等等内容,下面一起来看一下,希望对大家有帮助。

一起聊聊Java多线程之线程安全问题一起聊聊Java多线程之线程安全问题Apr 21, 2022 pm 06:17 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于多线程的相关问题,包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容,希望对大家有帮助。

详细解析Java的this和super关键字详细解析Java的this和super关键字Apr 30, 2022 am 09:00 AM

本篇文章给大家带来了关于Java的相关知识,其中主要介绍了关于关键字中this和super的相关问题,以及他们的一些区别,下面一起来看一下,希望对大家有帮助。

Java基础归纳之枚举Java基础归纳之枚举May 26, 2022 am 11:50 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于枚举的相关问题,包括了枚举的基本操作、集合类对枚举的支持等等内容,下面一起来看一下,希望对大家有帮助。

java中封装是什么java中封装是什么May 16, 2019 pm 06:08 PM

封装是一种信息隐藏技术,是指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法;封装可以被认为是一个保护屏障,防止指定类的代码和数据被外部类定义的代码随机访问。封装可以通过关键字private,protected和public实现。

归纳整理JAVA装饰器模式(实例详解)归纳整理JAVA装饰器模式(实例详解)May 05, 2022 pm 06:48 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于设计模式的相关问题,主要将装饰器模式的相关内容,指在不改变现有对象结构的情况下,动态地给该对象增加一些职责的模式,希望对大家有帮助。

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft