Linked Lists in Java Part 1

April 23rd, 2008
By: Cory Mathews

Recently I have been playing around with Java’s LinkedList class. This is a very usefull class that is included in java.util.LinkedList.

The LinkedList Class allows you to implement a linked list (what a surprise) with a simple class declaration. I am going to explain how to create and use the class, as well as a few tips I have picked up while playing around with the class.

In Part 1 I will cover:
Adding information
The basics of accessing it
Then removing it.

View Part 2 Here

First things first we need to include the class.

import java.util.LinkedList;
//or the lazy mans way
import java.util.*;

Now on to creating an instance of the class.

LinkedList myList = new LinkedList();
//or more specifically define its type.
LinkedList< String> myList = new LinkedList< String>();

Note: make sure to remove the space before String in both cases. WordPress would not display the < String> without the space.
Otherwise pretty simple, it’s just like any other class. I am going to call the list myList.

Adding to the List:
The first thing you would want to do is to add to the list. This can be done in 1 of 4 ways. The first and most basic is

myList.add("1");
//or
myList.add(varName);

This simply adds an item to the end of a list.
We can then expand on this and declare what spot in the array we want to add to. For example if I want to add it to the front (I will show a better way in a minute).

myList.add(0, "2");
//or
myList.add(0, varName);

The 0 just states that we want it as the first element. But you could substitue zero for any number within the list. Note that the destination spot must be within the size of the array. For instance right now after adding 1 and 2 from our two previous examples we have a list with size of 2. We could not insert into spot 4, an IndexOutOfBoundsException would be thrown and if not caught our program would crash.

The next two ways to add are pretty self documented. They are the addFirst() and addLast() functions. They can be used just like the add() method except the position to add to has already been set.

myList.addFirst("3");
myList.addLast("4");

There is also a function to add everything from a collection called .addAll() but I am not going to get into this because I do not have enough practice with collections to explain. You can find out more about using this method here.

Basics of Accessing Items

Getting the Size:
The first thing is a simple method to return the size of a list. The following would print the size of our list using the .size() method.

System.out.println(myList.size());

Getting the value of a specific spot.
using the .get() method we can get the value of any index in our list. If the index is not in the list a IndexOutOfBoundsException is thrown. Using this method does NOT remove the item from the list itself.

System.out.println(myList.get(0));
//or to store the value first
temp = myList.get(0);
System.out.println(temp);

This prints out the first item in our list. But does NOT remove it from the list.

I keep stressing that it does not remove it from the list because a couple tutorials I read when first learning the class, told me that it does remove the item. So I just want to make it clear to save you the trouble.

Just like with adding there is a getFirst() and getLast() that do exactly what they say.

Removing an Item:
So now we can add items and access items but we need to be able to get rid of the items. This is where the function .remove(), .removeFirst() and .removeLast() come into play. They work just like the add, and get functions. So we could remove our 4 items from our list using:

myList.removeLast();
myList.remove(0);
myList.removeFirst();
myList.removeFirst();

Of course the order here doesn’t matter I just wanted to show the 3 different ways to remove an item.

Here is a little useless example program using the LinkedList Class to see everything put together.

import java.util.*;public class LinkedListTest
{
public static void main(String[] args)
{
int pause;
String temp;
LinkedList myList = new LinkedList();
myList.add("1");
myList.add(0, "2");
myList.addFirst("3");
myList.addLast("4");
System.out.println("Size: "+myList.size());
System.out.println("Element 0: "+myList.get(0));
temp = myList.get(1);
System.out.println("Element 1: "+temp);
System.out.println("Size :"+myList.size());
System.out.println("First :"+myList.getFirst());
System.out.println("Last :"+myList.getLast());
System.out.println("Size yet again: "+myList.size());
myList.removeFirst();
System.out.println("Size yet again: "+myList.size());
myList.removeLast();
myList.remove(0);
myList.removeFirst();
System.out.println("Empty Size: "+myList.size());for(int x=0; x<100; x++) {
myList.add(""+x);
}
System.out.println("Loop Size :"+myList.size());
for(int x=100; x>0; x--) {
myList.removeLast();
}
System.out.println("Empty Size: "+myList.size());
}
}

View Part 2 Here