ArrayList Vs LinkedList in Java
ArrayList and LinkedList are the Collection classes , and both of them implements the List interface. LinkedList implements it with a doubly-linked list while ArrayList implements it with a dynamically re-sizing array.
- Search Operation
- Manipulation
- Behaviour
- Memory Overhead
Search Operation
Search Operation in ArrayList is pretty fast when compared to the LinkedList search operation. ArrayList Method get[int index] gives the performance of O[1] while LinkedList performance is O[n]. This is because ArrayList allows random access to the elements in the list as it operates on an index-based data structure while LinkedList does not allow random access as it does not have indexes to access elements directly, it has to traverse the list to retrieve or access an element from the list.
Manipulation
Manipulation with ArrayList is slow because it internally uses array. If We need to insert or delete element in ArrayList, it may take O[n], as it internally uses array and we may have to shift elements in case of insertion or deletion. On the other hand manipulation with LinkedList is faster than ArrayList because it uses doubly linked list so no bit shifting is required in memory. If We need to insert or delete element in LinkedList, it will take O[1], as it internally uses doubly.
An ArrayList is a simpler data structure than a LinkedList . An ArrayList has a single array of pointers in contiguous memory locations. It only has to be recreated if the array is expanded beyond its allocated size. But, LinkedList consists of a chain of nodes; each node is separated allocated and has front and back pointers to other nodes. So, unless you need to insert in the middle, splice, delete in the middle etc. an ArrayList will usually be faster. It needs less memory allocations, has much better locality of reference [which is important for processor caching] etc.
Behaviour
ArraylList behaves as List as it implements list. LinkedList behaves as List a well as the Queue as it implements List and Queue both.
Memory Overhead
ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbour nodes hence the memory consumption is high in LinkedList comparatively.
ArrayList Implementation
Output
LinkedList Implementation
Output
- Java Interview Questions-Core Faq - 1
- Java Interview Questions-Core Faq - 2
- Java Interview Questions-Core Faq - 3
- Important features of Java
- Difference between Java and JavaScript?
- What is the difference between JDK and JRE?
- What gives Java its 'write once and run anywhere' nature?
- What is JVM and is it platform independent?
- What is Just-In-Time [JIT] compiler?
- What is the garbage collector in Java?
- What is NullPointerException in Java
- Difference between Stack and Heap memory in Java
- How to set the maximum memory usage for JVM?
- What is numeric promotion?
- Why do we need Generic Types in Java?
- What does it mean to be static in Java?
- What are final variables in Java?
- How Do Annotations Work in Java?
- How do I use the ternary operator in Java?
- What is instanceof keyword in Java?
- How ClassLoader Works in Java?
- What are fail-safe and fail-fast Iterators in Java
- What are method references?
- "Cannot Find Symbol" compile error
- Difference between system.gc[] and runtime.gc[]
- How to convert TimeStamp to Date in Java?
- Does garbage collection guarantee that a program will not run out of memory?
- How setting an Object to null help Garbage Collection?
- How do objects become eligible for garbage collection?
- How to calculate date difference in Java
- Difference between Path and Classpath
- Is Java "pass-by-reference" or "pass-by-value"?
- Difference between static and nonstatic methods java
- Why Java does not support pointers?
- What is package in Java?
- What are wrapper classes?
- What is singleton class in Java?
- Difference between Java Local Variable, Instance Variable and a Class Variable?
- Can a top level class be private or protected in java
- Are Polymorphism , Overloading and Overriding similar concepts?
- How to Use Locks in Java
- Why Multiple Inheritance is Not Supported in Java
- Why Java is not a pure Object Oriented language?
- Why can't a Java class be declared as static?
- Difference between Abstract class and Interface in Java
- Why do I need to override the equals and hashCode methods in Java?
- Why does Java not support operator overloading?
- Whats meant by anonymous class in Java?
- Static Vs Dynamic class loading in Java
- Why am I getting a NoClassDefFoundError in Java?
- How to generate random integers within a specific range in Java
- What's the meaning of System.out.println in Java?
- What is the purpose of Runtime and System class?
- What is finally block in Java?
- What is difference between final, finally and finalize?
- What is try-with-resources in java?
- What is a stacktrace?
- What is the meaning of immutable in terms of String?
- What are different ways to create a string object in Java?
- Difference between String and StringBuffer/StringBuilder in Java
- What is the difference between creating String as new[] and literal?
- How do I convert String to Date object in Java?
- How do I create a Java string from the contents of a file?
- What actually causes a StackOverflow error in Java?
- Why is char[] preferred over String for storage of password in Java
- What is I/O Filter and how do I use it in Java?
- Serialization and Deserialization in Java
- Understanding transient variables in Java
- What is Externalizable in Java?
- What is the purpose of serialization/deserialization in Java?
- What is the Difference between byte stream and Character streams
- How to append text to an existing file in Java
- Read/convert an InputStream to a String in Java
- What is the difference between Reader and InputStream in Java
- Introduction to Java threads
- What is synchronization Java?
- Static synchronization Vs non static synchronization in Java
- Java Thread Deadlock Tutorial
- What is Daemon thread in Java
- Difference between implements Runnable and extends Thread in Java
- What is the volatile keyword in Java
- What are the basic interfaces of Java Collections Framework
- What are the differences between ArrayList and Vector in Java
- What is the difference between List and Set in Java
- Difference between HashSet and HashMap in Java
- Difference between HashMap and Hashtable in Java?
- How does the hashCode[] method of java works?
- Difference between capacity[] and size[] of Vector in Java
- What is a Java ClassNotFoundException?
- How to fix java.lang.UnsupportedClassVersionError