The LinkedList and ArrayList represent some of the widely used data structures of the Java Collections Framework. You might have had a chance to already use both classes several times so far; however, if you have wondered on what makes them fundamentally different, then continue reading.
Although both the LinkedList and ArrayList classes implement the List interface, they differ on the following 3-key issues: 1) Data Storage, 2) Data Access, 3) Data Management.
DATA STORAGE: Linked-list versus Array
• LinkedList uses the design of a linked-list data structure (from where it get its name) to store data elements (i.e. objects). In this manner, each data element -- depending on the position of the list -- has a link to the previous and next element. This storage approach proves to be very efficient, as it uses only as much memory as it needs; no more, no less.
• ArrayList uses an Object array for storing the data elements. By default the array starts with a capacity of 10; unless otherwise specified at the time of instantiation. For example, if we want to instantiate an ArrayList of strings with an initial capacity of 1024 then we would use:
• ArrayList uses an Object array for storing the data elements. By default the array starts with a capacity of 10; unless otherwise specified at the time of instantiation. For example, if we want to instantiate an ArrayList of strings with an initial capacity of 1024 then we would use:
ArrayList<String> stringArrayList = new ArrayList<String>(1024);
Thus, by default the ArrayList can be more wasteful as far as the memory allocation goes.
DATA ACCESS: Sequential Access versus Random Access
• LinkedList due to the nature of its data storage, has a sequential access approach. Thus, if we want to retrieve an element at a specific index through the public E get(int index) method, we would have to iterate either from the beginning or the end, depending if the requested index is greater than or less than half the length of the list. It can easily be seen how this sequential access can become quite timely as we deal with longer and longer lists. As the public E get(int index)method uses the Node node(int index) method for data retrieval, we can see the implications of LinkedList's sequential access in the following code:
570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 | /**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
|
• ArrayList supports random access as it has an internal array for data storage. Thus, when we call the public E get(int index) method in an ArrayList instance, we get forwarded to the E elementData(int index) method which simply returns the element located at the specified position within the array, i.e.:
333 334 335 336 337 338 | // Positional Access Operations
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
|
Needless to say, ArrayList's random access approach is far more efficient, as it doesn't have to waste computing cycles on iteration.
DATA MANAGEMENT: Linking and Unlinking versus Array Copying
• LinkedList can very efficiently undergo any changes in its collection of data elements. For example, if we want to remove a specific data element from the LinkedList instance -- through the public boolean remove(Object o) method -- then we go ahead and link the neighbors (i.e. previous and next data elements) of the unwanted data element, and the Garbage Collector will take care of the rest. Thus, if we have a linked-list structure with three string data elements (with previous and next links), as follow:
["A"] <-> ["B"] <-> ["C"]
Then, when we request removal of the "B" string data element, "A" and "C" get linked together, and "B" is left alone, thus becoming eligible for Garbage Collection:
["A"].next = ["B"].next => ["A"].next = ["C"]
["C"].prev = ["B"].prev => ["C"].prev = ["A"]
The Java implementation behind this pseudo-code looks like the following:
213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 | /**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
|
Do note that the code displayed above is for the E unlink(Node x) method on which LinkedList's public boolean remove(Object o) method relies. In addition to the efficiency of the remove method, LinkedList is very flexible when it comes to enlarging or shrinking its collection of data elements. In a LinkedList instance whenever we need to add to the collection, a call is made to the void linkLast(E e) method, which simply appends the new data element to the end of the list, as seen below:
144 145 146 147 148 149 150 151 152 153 154 155 156 157 | /**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<E>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
|
• ArrayList due to the usage of its internal array it copies all of the elements to a new array every time there's a removal request, or when there's not enough room to add a new element. Thus, for every new addition or removal from our ArrayList collection a call is made to the public void ensureCapacity(int minCapacity) method, which carries out the necessary copying and shifting of the elements, as seen below:
171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 | /**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
|
Needless to say, you can imagine how much work these operations carry out, especially when dealing with very large arrays.
In conclusion, we can see that both the LinkedList and ArrayList have their positives and negatives; however, by having a good understanding of these issues you can make a better decision on what implementation should you use, based on the data size and usage requirements.
No comments:
Post a Comment