16.5 Benefits of LinkedLists

Why use LinkedList?When to use ArrayLists?:

Why use LinkedList?

Manipulation: Moving elements around and changing elements in LinkedLists takes less time because, as you saw by the implementation, you can simply change node references. ArrayLists internally use arrays, so manipulating elements in ArrayLists requires traversing an array and physically shifting memory bits around, which takes more time.

Adding to front or back: It’s easier to end to the front or end of a LinkedList because you simply change the head or tail node. Adding to the beginning of an ArrayList requires transferring all the data down one position, which takes more time.

When to use ArrayLists?:

Storing: It’s more efficient to store elements in an ArrayList if you’re not going to change elements around too much.

Accessing: It takes less time to access an element in an ArrayList because it internally uses arrays, so elements can be accessed immediately. To access an element in a LinkedList, you have to traverse down the entire list one by one until you reach the node you want

Let’s demonstrate these differences by actually measuring the time it takes to complete an operation: adding elements to a list.

Here is our test code:


long a, b;

LinkedList<Integer> list1 = new LinkedList<Integers>();
a = System.nanoTime();
for(int i=0; i<10000; i++)
	list1.add(1);
b = System.nanoTime();
System.out.println("Linked: " + (b-a) + " ns");

ArrayList<Integer> list2 = new ArrayList<Integer>();
a = System.nanoTime();
for(int i=0; i<10000; i++)
	list2.add(1);
b = System.nanoTime();
System.out.println("ArrayList: " + (b-a) + " ns");

System.nanoTime() is a method which returns the current time of the system in nanoseconds. We record the time and store it in a, complete our operation, and then record the time again to store it in b. (a and b are longs because the current time in nanoseconds is too large to fit in an integer.)

We add a large number of elements (10,000) because the efficiency differences usually only show up when dealing with large amounts of data. We just add the element “1” repeatedly for simplicity.

Here is the output:


Linked: 10251960 ns
ArrayList: 18086990 ns

Clearly, the LinkedList takes much less time to add a large number of elements than the ArrayList does. Also, note that these numbers will be different every time you run the code because your computer will probably be doing other tasks (with other apps running in the background, like connecting to Google, keeping track of time, etc.), but the LinkedList will always take less time in general.

Previous Section

4️⃣

16.4 Do it Yourself! - CirclyLinkedList

Next Section

6️⃣

16.6 Practice

⚖️

Copyright © 2021 Code 4 Tomorrow. All rights reserved. The code in this course is licensed under the MIT License. If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.