


A question asked in almost all Java interviews: talk about the difference between ArrayList and LinkedList
Jul 26, 2023 pm 03:11 PMPreface
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
ArrayList
The 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
.
LinkedList
The 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!

Hot AI Tools

Undress AI Tool
Undress images for free

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

The settings.json file is located in the user-level or workspace-level path and is used to customize VSCode settings. 1. User-level path: Windows is C:\Users\\AppData\Roaming\Code\User\settings.json, macOS is /Users//Library/ApplicationSupport/Code/User/settings.json, Linux is /home//.config/Code/User/settings.json; 2. Workspace-level path: .vscode/settings in the project root directory

To correctly handle JDBC transactions, you must first turn off the automatic commit mode, then perform multiple operations, and finally commit or rollback according to the results; 1. Call conn.setAutoCommit(false) to start the transaction; 2. Execute multiple SQL operations, such as INSERT and UPDATE; 3. Call conn.commit() if all operations are successful, and call conn.rollback() if an exception occurs to ensure data consistency; at the same time, try-with-resources should be used to manage resources, properly handle exceptions and close connections to avoid connection leakage; in addition, it is recommended to use connection pools and set save points to achieve partial rollback, and keep transactions as short as possible to improve performance.

itertools.combinations is used to generate all non-repetitive combinations (order irrelevant) that selects a specified number of elements from the iterable object. Its usage includes: 1. Select 2 element combinations from the list, such as ('A','B'), ('A','C'), etc., to avoid repeated order; 2. Take 3 character combinations of strings, such as "abc" and "abd", which are suitable for subsequence generation; 3. Find the combinations where the sum of two numbers is equal to the target value, such as 1 5=6, simplify the double loop logic; the difference between combinations and arrangement lies in whether the order is important, combinations regard AB and BA as the same, while permutations are regarded as different;

DependencyInjection(DI)isadesignpatternwhereobjectsreceivedependenciesexternally,promotingloosecouplingandeasiertestingthroughconstructor,setter,orfieldinjection.2.SpringFrameworkusesannotationslike@Component,@Service,and@AutowiredwithJava-basedconfi

fixture is a function used to provide preset environment or data for tests. 1. Use the @pytest.fixture decorator to define fixture; 2. Inject fixture in parameter form in the test function; 3. Execute setup before yield, and then teardown; 4. Control scope through scope parameters, such as function, module, etc.; 5. Place the shared fixture in conftest.py to achieve cross-file sharing, thereby improving the maintainability and reusability of tests.

java.lang.OutOfMemoryError: Javaheapspace indicates insufficient heap memory, and needs to check the processing of large objects, memory leaks and heap settings, and locate and optimize the code through the heap dump analysis tool; 2. Metaspace errors are common in dynamic class generation or hot deployment due to excessive class metadata, and MaxMetaspaceSize should be restricted and class loading should be optimized; 3. Unabletocreatenewnativethread due to exhausting system thread resources, it is necessary to check the number of threads, use thread pools, and adjust the stack size; 4. GCoverheadlimitexceeded means that GC is frequent but has less recycling, and GC logs should be analyzed and optimized.

Use classes in the java.time package to replace the old Date and Calendar classes; 2. Get the current date and time through LocalDate, LocalDateTime and LocalTime; 3. Create a specific date and time using the of() method; 4. Use the plus/minus method to immutably increase and decrease the time; 5. Use ZonedDateTime and ZoneId to process the time zone; 6. Format and parse date strings through DateTimeFormatter; 7. Use Instant to be compatible with the old date types when necessary; date processing in modern Java should give priority to using java.timeAPI, which provides clear, immutable and linear

TheJVMenablesJava’s"writeonce,runanywhere"capabilitybyexecutingbytecodethroughfourmaincomponents:1.TheClassLoaderSubsystemloads,links,andinitializes.classfilesusingbootstrap,extension,andapplicationclassloaders,ensuringsecureandlazyclassloa
