Java Article 21 - Java Collections - LinkedList

Another kind of container object useful for holding an ordered collection of objects is the LinkedList. The LinkedList is a close relative of ArrayList which we covered in our previous article. Both classes implement the List interface (among others) and by convention share the word List in the latter part of their name.

LinkedLists don't use arrays like ArrayLists. In a LinkedList each element has a pointer to the element before it and to the element following it. Because of this LinkedLists and ArrayLists will perform differently from processing time and memory usage standpoints.

I am not going to get into all the differences in performance here except to say a LinkedList can add elements very quickly to its beginning or middle, and there is no capacity to manage. Ultimately performance really depends on what you are doing with your collection. When performance is a concern you are best off testing each side by side and seeing which is better for your particular application.

Often LinkedLists are selected for use because of the methods in this class. LinkedList has most of the common methods ArrayList has (add(), get(), set(), remove(), size(), etc) plus a number of new methods that can be very convenient:

addFirst(object) & addLast(object): adds the object to the beginning or end of the LinkedList.

peek(): This just returns the first element of the LinkedList.

poll(): This returns and removes the first element of the LinkedList. Also this will return null if the LinkedListis empty.

offer(): Attempts to add an object to the end of the LinkedList, and returns a Boolean based on weather it was added or not.

removeFirst() and removeLast(): Returns or removes the last element.

Here is a quick program showing LinkedList in action:

import java.util.LinkedList;

public class LinkedListExample 
{

	static LinkedList <String> myLinkedList = 
		new LinkedList <String> ();
		
	public static void main(String[] argv)
	{
		
		demonstrateAddFirstAndLast();
		demonstratePeek();
		demonstratePoll();
		demonstrateOffer();
		demonstrateRemoveFirstAndLast();
		demonstratePollWithEmptyList();
	}

	private static void demonstrateAddFirstAndLast() 
	{
		
		System.out.print("Here we add some elements to the" +
			" beginning of our LinkedList with addFist():");
		
		myLinkedList.addFirst("Object A");
		displayCollection();
		myLinkedList.addFirst("Object B");
		displayCollection();
		myLinkedList.addFirst("Object C");
		displayCollection();
		myLinkedList.addFirst("Object D");
		displayCollection();
		
		System.out.print("\nHere we add Object E to the" +
		" end of our LinkedList with addLast():");
		myLinkedList.addLast("Object E");
		displayCollection();
		
		
	}
	
	private static void demonstratePoll() 
	{
		System.out.println("\nHere we see how poll() works:");
		System.out.println("The first element in the list is: " 
				+ myLinkedList.poll());
		System.out.print("poll() also removes the element:"); 
		displayCollection();
		
	}
	
	private static void demonstratePeek() 
	{
		System.out.println("\nHere we see how peek() works:");
		System.out.println("The first item in the list is: " 
				+ myLinkedList.peek());
		
	}

	private static void demonstrateOffer() 
	{
		System.out.println("\nHere we see how offer() works:");
		//offer() will return true if the object was added
		System.out.println("ObjectFromOffer was sucessfully " 
				+ "added to the end: " 
				+ myLinkedList.offer("ObjectFromOffer"));
		displayCollection();
	}
	
	private static void demonstrateRemoveFirstAndLast() 
	{
		System.out.print("\nFinally, we will remove the " +
				"first element with removeFirst():");
		myLinkedList.removeFirst();
		displayCollection();
		System.out.print("\n...and removeLast(): ");
		myLinkedList.removeLast();
		displayCollection();
		
	}
	
	private static void displayCollection() 
	{
		//String whatWeAreDoingNow
		System.out.println("\nCollection Contents:");
					
		for (String stings : myLinkedList)
		{
			
			System.out.println(stings);
		}
	}
	
	private static void demonstratePollWithEmptyList() 
	{
		
		myLinkedList.clear();
		
		System.out.println("\nHere we clear the list to show" +
				" how poll() works with an empty list:");
		System.out.println("The first element in the list is: " 
				+ myLinkedList.poll());
		
		//With this, you can also do:
		if (myLinkedList.poll() == null)
		{
			System.out.print("Empty");
			//do something if its empty
		}
		
		if (myLinkedList.poll() != null)
		{
			System.out.print("not Empty");
			//do something if its not empty
		}
	}
}