Java Collections Tutorial 2: LinkedList

A LinkedList is a lot like the ArrayList, which we covered in the last tutorial. It implements the same methods for adding, removing and iterating through its elements as an ArrayList.

So if we were to declare an LinkedList that holds objects of type String, then we would declare it like this:

LinkedList<String> names = new LinkedList<String>();

If we create an LinkedList to hold doubles, here is how we do it:

LinkedList<Double> prices = new LinkedList<Double>();

If we create an LinkedList to hold integers, here is how we do it:

LinkedList<Integer> numbers = new LinkedList<Integer>();

Notice that in all the above example, I use the wrapper types and not the primitive types. So instead of int, I use Integer. Instead of double, I use Double. Java will not allow you to use primitive types as parameters in generic classes. You always need to use the wrapper classes.

Adding Items to an LinkedList

When adding items to an LinkedList, we use the add() method. You can use the add() method in isolation or in a loop. It depends with what you want to add.

For example, if I want to add a couple of names to an LinkedList of type String, I would do the following:

LinkedList<String> names = new LinkedList<String>();

names.add(“Brian”);

names.add(“Veronicah”);

names.add(“Victor”);

If I want to add numbers from one to ten to an LinkedList holding integers, here is how I would do it using a for loop:

LinkedList<Integer> numbers = new LinkedList<Integer>();

for(int i  = 0; i <= 10; i++) {

            numbers.add(i);

}

Figure 1: Adding items to a LinkedList

Removing Items from an LinkedList

To remove items from an LinkedList, we use the remove() method. We pass the index of the item we want to remove as a parameter to the method. Remember that in LinkedList, just like in arrays, we always start counting the items at index zero. So if we want to remove the third item, we call remove(2).

So let’s say we have the array of numbers that we created above. Here is how we would remove the 4^th item, which is the number 5.

LinkedList<Integer> numbers = new LinkedList<Integer>();

for(int i  = 0; i <= 10; i++) {

            numbers.add(i);

}

numbers.remove(4); 

Figure 2: Removing items from a LinkedList

Iterating through an LinkedList

To iterate through an LinkedList, you can either use a for loop or a for each loop. So say we want to display all the values in the LinkedList above that contains integers. Here is how we would do it:

a) Using a for loop:

LinkedList<Integer> numbers = new LinkedList<Integer>();

for(int i  = 0; i <= 10; i++) {

            numbers.add(i);

}

numbers.remove(4);

for(int i  = 0; i < numbers.size(); i++) {

            System.out.println(numbers.get(i));

} 

Figure 3: Iterating through an ArrayList

b) Using a for each loop:

LinkedList<Integer> numbers = new LinkedList<Integer>();

for(int i  = 0; i =< 10; i++) {

            numbers.add(i);

}

numbers.remove(4);

for(Integer number: numbers) {

            System.out.println(number);

} 

Figure 4: Iterating through a LinkedList using a foreach loop

Notice that we use the get() method to access the value stored at a certain index.

The Difference Between LinkedList and ArrayList

Now that we are discussing the difference between LinkedList and ArrayList, I might as well discuss the similarity. LinkedList and ArrayList both implement the List interface. So it is common to find code written like this:

List<String> names = new ArrayList<String>();

List<String> numbers = new LinkedList<String>();

So long as you remember the last part of the code where you are using the new keyword, the part to the right of the equals sign can use List.

Now let’s look at the difference. ArrayList internally manages an array of objects. So if we were to imagine the internal working of an ArrayList, the objects would be arranged like this: [0][1][2][3][4][5]… So with in an ArrayList, locating items is very fast because what you need to know is the index of the object you are referring to. This means that when we add items to the end of an ArrayList, it’s very fast because Java will look for the last index and place the new item at the last index + 1 position. Removing items from the end or close to the end of an ArrayList is also fast because the item will be removed without any additional operations.

With a LinkedList, however, each object has a reference to the previous and the next element. So, if we were to look at the internal workings of a LinkedList, this is how items would be arranged:

[0]->[1]->[2]->[3]->[4]->[5]->[6]->[7]…

   <-   <-   <-   <-   <-   <-   <-

The real difference between ArrayLists and LinkedLists is when we are adding items at the beginning or the middle. With ArrayLists, Java has to copy all the items to a new ArrayList where each item after the index where the new item is added is moved up one index. When you delete an item at the beginning or middle of an ArrayList, Java has to create a new ArrayList onto which it copies the contents of the new list of objects, leaving out the removed one. Therefore, each object after the one that is removed has to move down one index. These operations take a long time, especially if you have so many items on the ArrayList.

On the other hand, when you add an object at the beginning or middle of a LinkedList, what Java does is just point the previous object to the new object and the new object to the object that is located after it. This is very fast. And this is why when you are adding or removing items towards the end or at the end of a list, use an ArrayList. However, if you are adding or removing items at the beginning or the middle of a list, use a LinkedList.

If you have any questions or comments about this tutorial or any other tutorial for that matter, please use the comments section below.

In the next tutorial, we will look at the HashMap.

Until then, take care.