Hi! All the latest lessons have been devoted to ArrayList. This data structure is very convenient and useful. It can handle plenty of tasks. But Java has lots of other data structures.
Why? Above all, because the range of tasks is enormous, and the most efficient data structures are different for different tasks.
Today we'll meet a new structure: LinkedList, a doubly-linked list.
Let's see how it's organized, why it's called doubly-linked, how it differs from ArrayList.
The elements in a LinkedList are actually links in a single chain. In addition to data, each element stores references to the previous and next elements. These references let you move from one element to another.
This is how you create one:
public class Main {
public static void main(java.lang.String[] args) {
String str1 = new String("Hello World!");
String str2 = new String("My name is Earl");
String str3 = new String("I love Java");
String str4 = new String("I live in Canada");
LinkedList<String> earlBio = new LinkedList<>();
earlBio.add(str1);
earlBio.add(str2);
earlBio.add(str3);
earlBio.add(str4);
System.out.println(earlBio);
}
}
Output:
[Hello World! My name is Earl, I love Java, I live in Canada]
Here's what our list looks like:
Let's see how to add a new element. This is done using the add() method.
earlBio.add(str2);
At the point in the code, our list consists of one element: the String str1.
Let's see what happens next in the picture:
As a result, str2 and str1 become linked via the next and previous links stored in this nodes of the list:
Now you should understand the main idea of a doubly-linked list. This chain of links is precisely what makes LinkedList elements a single list. Unlike ArrayList, LinkedList doesn't have an array or anything array-like inside.
Any (well, most) work with ArrayList boils down to working with the internal array.
Any work with LinkedList boils down to changing links.
This can be seen very clearly by adding an element to the middle of the list:
public class Main {
public static void main(java.lang.String[] args) {
String str1 = new String("Hello World!");
String str2 = new String("My name is Earl");
String str3 = new String("I love Java");
String str4 = new String("I live in Canada");
LinkedList<String> earlBio = new LinkedList<>();
earlBio.add(str1);
earlBio.add(str3);
earlBio.add(1, str2);
System.out.println(earlBio);
}
}
As you can see, the overloaded add() method lets you specify a specific index for a new item. In this case, we want to add String str2 between str1 and str3.
This is what will happen internally:
After changing the internal links, str2 has been successfully added to the list:
Now all 3 elements are connected. You can move via the next link from the first element on the chain to the last and back again.
So, we're fairly comfortable with insertion, but what about removing elements?
The principle is exactly the same. We just update the links in the two elements "to the left and the right" of the element being removed:
public class Main {
public static void main(java.lang.String[] args) {
String str1 = new String("Hello World!");
String str2 = new String("My name is Earl");
String str3 = new String("I love Java");
String str4 = new String("I live in Canada");
LinkedList<String> earlBio = new LinkedList<>();
earlBio.add(str1);
earlBio.add(str3);
earlBio.add(1, str2);
earlBio.remove(1);
System.out.println(earlBio);
}
}
Here's what happens if we delete the item with index 1 (it's in the middle of the list):
After updating the links, we get the desired result:
Unlike the removal operation in ArrayList, here there is no need to shift array elements or do anything of the kind. We just update the links for str1 and str3. They now point to each other, and str2 has "dropped out" of the chain of links and is no longer part of the list.
Overview of methods
LinkedList has a lot of methods in common with ArrayList.
For example, both classes have methods such as add(), remove(), indexOf(), clear(), contains() (indicates whether an item is in the list), set() (replaces an existing element), and size().
Although many of them work differently internally (as we found with add() and remove()), the end result is the same.
However, LinkedList does have separate methods for working with the beginning and end of the list, which ArrayList does not have:
addFirst(),addLast(): These methods for adding an element to the beginning/end of the list
public class Car {
String model;
public Car(String model) {
this.model = model;
}
public static void main(String[] args) {
LinkedList<Car> cars = new LinkedList<>();
Car ferrari = new Car("Ferrari 360 Spider");
Car bugatti = new Car("Bugatti Veyron");
Car lambo = new Car("Lamborghini Diablo");
Car ford = new Car("Ford Modneo");
Car fiat = new Car("Fiat Ducato");
cars.add(ferrari);
cars.add(bugatti);
cars.add(lambo);
System.out.println(cars);
cars.addFirst(ford);
cars.addLast(fiat);
System.out.println(cars);
}
@Override
public String toString() {
return "Car{" +
"model='" + model + '\'' +
'}';
}
}
Output:
[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
[Car{model='Ford Modneo'}, Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}]
We end up with "Ford" at the top of the list, and "Fiat" at the end.
peekFirst(),peekLast(): The methods return the first/last element in the list. They returnnullif the list is empty.
public static void main(String[] args) {
LinkedList<Car> cars = new LinkedList<>();
Car ferrari = new Car("Ferrari 360 Spider");
Car bugatti = new Car("Bugatti Veyron");
Car lambo = new Car("Lamborghini Diablo");
cars.add(ferrari);
cars.add(bugatti);
cars.add(lambo);
System.out.println(cars.peekFirst());
System.out.println(cars.peekLast());
}
Output:
Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
pollFirst(),pollLast(): These methods return the first/last element in the list and remove it from the list. They return null if the list is empty
public static void main(String[] args) {
LinkedList<Car> cars = new LinkedList<>();
Car ferrari = new Car("Ferrari 360 Spider");
Car bugatti = new Car("Bugatti Veyron");
Car lambo = new Car("Lamborghini Diablo");
cars.add(ferrari);
cars.add(bugatti);
cars.add(lambo);
System.out.println(cars.pollFirst());
System.out.println(cars.pollLast());
System.out.println ("What's on the list?");
System.out.println(cars);
}
Output:
Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What's left on the list?
[Car{model='Bugatti Veyron'}]
toArray(): This method returns an array containing the list items
public static void main(String[] args) {
LinkedList<Car> cars = new LinkedList<>();
Car ferrari = new Car("Ferrari 360 Spider");
Car bugatti = new Car("Bugatti Veyron");
Car lambo = new Car("Lamborghini Diablo");
cars.add(ferrari);
cars.add(bugatti);
cars.add(lambo);
Car[] carsArray = cars.toArray(new Car[3]);
System.out.println(Arrays.toString(carsArray));
}
Output:
[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
Now we know how LinkedList works and how its organization differs from ArrayList. What are the benefits of using LinkedList?
Above all, we benefit when working in the middle of the list. Insertion and removal operations in the middle of a LinkedList are much simpler than in an ArrayList. We simply update the links of neighboring elements, and the unwanted element "drops out" of the chain of links.
But in an ArrayList, we must
- check whether there is enough space (when inserting)
- if not, then we create a new array and copy the data there (when inserting)
- we remove/insert the element, and move all the other elements to the right/left (depending on the type of operation). And the complexity of this process depends heavily on the size of the list. It's one thing to copy/move 10 elements, and quite another to do the same with a million elements.
In other words, if your program insertion/removal operations in the middle of the list are most common in your program, LinkedList should be faster than ArrayList.
In theory
public class Main {
public static void main(String[] args) {
List<Integer> list = new LinkedList<>();
for (int i = 0; i < 5_000_000; i++) {
list.add(new Integer(i));
}
long start = System.currentTimeMillis();
for (int i = 0; i < 100; i++) {
list.add(2_000_000, new Integer(Integer.MAX_VALUE));
}
System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
}
}
Output:
Time taken by LinkedList (in milliseconds) = 1873
public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 5_000_000; i++) {
list.add(new Integer(i));
}
long start = System.currentTimeMillis();
for (int i = 0; i < 100; i++) {
list.add(2_000_000, new Integer(Integer.MAX_VALUE));
}
System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
}
}
Output:
Time taken by ArrayList (in milliseconds) = 181
That was unexpected!
We performed an operation where LinkedList should be much more efficient: inserting 100 items in the middle of a list.
And our list is huge: 5,000,000 elements. ArrayList had to shift a couple of million items with every insertion!
How did it win?
First, the time required for ArrayList to access elements is fixed (constant). When you write
list.add(2_000_000, new Integer(Integer.MAX_VALUE));
then ArrayList [2_000_000] is a specific memory address (after all, the list has an internal array).
But, a LinkedList does not have an array. It will search for element number 2_000_000 along the chain of links. For LinkedList, this is not a memory address, but a link that still needs to be reached:
fistElement.next.next.next.next.next.next.…………
As a result, during each insertion (removal) in the middle of the list, ArrayList already knows the exact memory address to access, but LinkedList still needs to "get there".
Second, there is the structure of the ArrayList itself. A special internal function (System.arrayCopy()) expands the internal array, and copies and shifts all the elements. It is very fast because it is optimized for this specific work.
But when you don't have to "get to" a particular index, LinkedList is the winner. Suppose we insert at the very beginning of the list.
Let's try inserting a million elements there:
public class Main {
public static void main(String[] args) {
getTimeMsOfInsert(new ArrayList());
getTimeMsOfInsert(new LinkedList());
}
public static long getTimeMsOfInsert(List list) {
// Write your code here
Date currentTime = new Date();
insert1000000(list);
Date newTime = new Date();
long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
System.out.println("The result in milliseconds: " + msDelay);
return msDelay;
}
public static void insert1000000(List list) {
for (int i = 0; i < 1000000; i++) {
list.add(0, new Object());
}
}
}
Output:
The result in milliseconds: 43448
The result in milliseconds: 107
Now we get an entirely different result!
ArrayList spent more than 43 seconds inserting a million items at the front of the list took, while LinkedList managed to do it in 0.1 seconds!
LinkedList benefited here because it did not have to run through the chain of links to the middle of the list every time. It immediately finds the needed index at the beginning of the list, so the different algorithm is already an advantage. :)
In fact, the "ArrayList versus LinkedList" discussion is very widespread, and we won't dive deep into it at the current level.
The main thing that you need to remember is this:
- Not all of the theoretical advantages any particular collection always work in reality (we saw this with the example involving the middle of the list)
- Don't adopt an extreme position when it comes to choosing a collection ("ArrayList is always faster. Use it and you can't go wrong. Nobody has been using LinkedList for a long time").
Although even LinkedList author, Joshua Bloch, says this is the case. :)
Still, this perspective is far from 100% correct, and we've convinced ourselves of this. In our previous example, LinkedList was 400 (!) times faster. Another thing is that there really are a few situations where LinkedList is the best choice. But they do exist, and at the right moment LinkedList can reward you handsomely. Don't forget what we said at the beginning of the lesson: the most efficient data structures are different for different tasks.
It's impossible to be 100% sure which data structure will be best until you know all the conditions of your task.
You'll know more about these collections later, which will make the choice easier. But the simplest and most effective option is always the same: try both on the actual data used in your program. Then you will be able to see for yourself how both types of lists perform and you definitely won't go wrong.
Was published on CodeGym blog .