ArrayList vs. LinkedList vs. Vector
Landing a job in software engineering role is much easier than people think. But in some cases, the majority of my folks with many years experience in this expertise failed its candidacy. “What’s a problem?” The question is pumping up in my head.
I’ve been enjoying my time as Software Engineering role even better love what I’m doing with my code for the last 6 years. During that time I’ve had amazing experiences interviewing many Software Engineering candidates. In every interview process, I do not only expect the candidates to be well grounded in topics like good software design principles, scalable code architecture, and testing but also their knowledge in basic of data structure and algorithm in Software Engineering. I was so sad when many candidates didn’t understand the basic.
Besides being quick learner who can learn new frameworks, tools or even programming languages within a short amount of time, having a solid understanding of data structure is one of key knowledge that you should have if you want to pursue a career as software engineer.
Data structure is a particular way of storing and organising information in a computer so that it can be retrieved and used most productively. Different kinds of data structures are meant for different kinds of applications, and some are highly specialised to specific tasks. — Wikipedia
Why data structure becomes one of the important knowledge to have? The data structure and algorithm provide a set of techniques for handling the data efficiently. If the candidates do not know about data structure and algorithm, they may not be able to write efficient code to handle the data. Knowing how data structure store their data, how they perform and when to use with pre-defined set of techniques will improve the time needed to resolve the problem. One of the questions that candidates often fail to answer is
Which one better, ArrayList, LinkedList or Vector?
List
Before answering the question, its good to know what List is. List is one of an abstract data type (ADT) which stores its elements in a sequence and allows us to add, remove and access its elements by using index. Array is one of the data structures that implements the ADT List. In Array, we can add, delete, and get element by using index. ArrayList, LinkedList and Vector are another example of data structures that implement ADT List. While Array has static size once it declared, ArrayList, LinkedList and Vector have a dynamic size (resizable). If an Array is declared with length 7, then it will have a length of 7 until the end of its scope. While ArrayList, LinkedList and Vector can store data as much as possible, where the limit is total of available memory.
In the Java Collection Framework, the ADT List is implemented as an Interface called List, and ArrayList, LinkedList & Vector are the concrete class that implements the List interface. Since these concrete classes implements the same interface, these classes must have the same functionality because for all non-abstract classes that implements an interface, is required to implements all abstract methods that is declared in the interface.
How Data Stored
The fundamental difference of the three data structures above is the way they store their data which causes different performance for different operations. In Java (and also used in Kotlin), ArrayList and Vector uses an Array to store its elements, while LinkedList stores its elements in a doubly-linked-list.
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. — Wikipedia
In LinkedList, the first node can know the second node. The second node can know the first and third nodes. The third node can know the second and fourth nodes. And so on, a Node can know the previous Node and the next Node. Especially for the first Node in LinkedList, there will be no previous node and also the last node in LinkedList there will be no next Node.
Here is the code snippet how ArrayList store their elements in Array.
/**
* The array buffer into which the elements of the ArrayList are
* stored. The capacity of the ArrayList is the length of this
* array buffer. Any empty ArrayList with elementData ==
* DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to
* DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested
// class accessAnd here is how Vector store their elements also in Array.
/**
* The array buffer into which the components of the vector are
* stored. The capacity of the vector is the length of this array
* buffer, and is at least large enough to contain all the vector's
* elements.
*
* <p>Any array elements following the last element in the Vector
* are null.
*
* @serial
*/
protected Object[] elementData;In the above code snippet, we can see that both ArrayList and Vector stores its elements in a variable named elementDatawith Object[] as its type. Why Object[]? Object is a super-class of all classes in Java. By defining elementData as Object[], then elementData could store various types of elements, it could be String, Integer, Double, Float or custom class like Pair, TextView and so forth.
Why ArrayList and Vector using an Array to store its data? As mentioned earlier, although ArrayList and Vector uses arrays to store its data, ArrayList and Vector has the ability to have dynamic sizes (resizable). When the array used in ArrayList and Vector is full, those can “grow” to enlarge its capacity. ArrayList and Vector increase its capacity by creating a new Array with size bigger than the previous size, then copies all the elements from the old Array to the new Array by using command Arrays.copyOf. Here is a code snippet of the program on ArrayList to enlarge its capacity (source: ArrayList.java).
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}And here is how Vector enlarge its capacity (source: Vector.java)
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}Vector implementation is almost identical to ArrayList, and the only difference is all operations in Vector are synchronized that makes any method that touches the Vector’s contents is thread safe.
So which one better, ArrayList, LinkedList or Vector? To answer this question lets compare the performance for common operations inside ArrayList and LinkedList. Since the ArrayList and Vector implementation is almost identical, their performance also would be nearly the same.
From the table above, we can see that there are no silver bullet for all operations. ArrayList is superior to LinkedList at random access (get). ArrayList better than LinkedList because ArrayList stores its elements in an Array while LinkedList stores its elements within the linked Node. For example, to get the 5th element, ArrayList and Vector can directly get its element by using index since ArrayList and Vector essentially is an array, while LinkedList must be iterate to find out fifth element, because in LinkedList, we can only know the first and last element only.
For insertFirst and deleteFirst, LinkedList is superior to ArrayList. ArrayList requires great effort to add an element at the beginning (first index) or delete the first element because ArrayList must shift the following elements after addition or deletion. While LinkedList only need to replace/set its pointers. As for other functions, both ArrayList and LinkedList have relatively the same performance.
So which one better, ArrayList, LinkedList or Vector? Depend on your needs. If you use random access (get) more often, then ArrayList and Vector is a good choice. Choose Vector if you need a thread-safe collection. But if you frequently make additions or deletions on the first position (index), LinkedList is a better choice.
There is another ADT that commonly used while developing application like Set, Map and PriorityQueue. To know how they store their data, how they work and when to use, keep stay tune on my Medium.
