Java Collections – LinkedList Example – Developers Corner

A LinkedList is implemented as a double linked list enabling the traversing in the forward as well as the backward direction. The performance on the get() and remove() is very good as it only needs to readjust the pointers to the previous and next nodes. However, it suffers worst performance than Vector and ArrayList in the get() methods as it does not have direct way of getting at a specific element index.

Big-O Notation

The LinkedList implementation provides O(1) for add() and remove() operations and log(n) for get() operations.

Creating a LinkedList

This was the old-way prior to Generics.

LinkedList  HallOfFameMembers = new LinkedList();

Collection HallOfFameMembers = new LinkedList();

Generics

If you look closely, you will notice that I am using Generics to limit the type to String. Generics add stability to your code, by having the computer detect type incompatibilities during compile-time. These runtime bugs would be more difficult to debug if left unchecked.

Collection<String> HallOfFameMembers = new LinkedList<String>();

Adding elements

Adding elements to the LinkedList is done by using the add(Object obj) method.

// Add elements to our LinkedList
HallOfFameMembers.add("Babe Ruth");
HallOfFameMembers.add("Ty Cobb");
HallOfFameMembers.add("Lou Gehrig");
HallOfFameMembers.add("Ted Williams");
HallOfFameMembers.add("Hank Aaron");
HallOfFameMembers.add("Yogi Berra");
HallOfFameMembers.add("Willie Mays");

Removing elements

Removing elements is just a matter of calling the remove(Object obj) method.

HallOfFameMembers.remove("Yogi Berra");
HallOfFameMembers.remove("Ted Williams");

Size of Collection

Returning the number of elements in a LinkedList is as easy as calling the size() method.

HallOfFameMembers.size();

Iterating through the Collection (Using foreach)

Java 1.5 and above provides a foreach loop, which makes it much easier to iterate over the entire collection. This is my preferred way of doing it.

// Loop through the collection of LinkedList
for (String player : HallOfFameMembers) {
   count++;
   System.out.format("[%d]: %sn", count, player);
}

Iterating through the Collection (Using iterator)

// Loop through the collection of HallOfFameMembers
int count = 0;
Iterator<String> iter = (Iterator<String>) HallOfFameMembers.iterator();
while (iter.hasNext()) {
   count++;
   String player = iter.next();
   System.out.format("[%d]: %sn", count, player);
}

Full Program Listing

package com.avaldes.tutorials;

import java.util.Collection;
import java.util.LinkedList;

public class LinkedListExample {
    
  public static void main(String[] args) {
    Collection<String> HallOfFameMembers = new LinkedList<String>();

    // Check to see if the LinkedList is empty
    System.out.println("Is LinkedList Empty: "+HallOfFameMembers.isEmpty());
        
    System.out.println("Adding 10 elements...");
    // Add elements to our LinkedList
    HallOfFameMembers.add("Babe Ruth");
    HallOfFameMembers.add("Ty Cobb");
    HallOfFameMembers.add("Lou Gehrig");
    HallOfFameMembers.add("Ted Williams");
    HallOfFameMembers.add("Hank Aaron");
    HallOfFameMembers.add("Yogi Berra");
    HallOfFameMembers.add("Willie Mays");
    HallOfFameMembers.add("Jim Palmer");
    HallOfFameMembers.add("Tom Seaver");
    HallOfFameMembers.add("Nolan Ryan");
    
    // Add null values -- Allowed
    System.out.println("Adding null element...");
    HallOfFameMembers.add(null);
    
    // Check if Willie Mays is in my List
    System.out.println("Checking if Willie Mays is in HallOfFameMembers" 
                              + HallOfFameMembers.contains("Willie Mays"));
    System.out.println("Checking if Amaury Valdes is in HallOfFameMembers" 
                              + HallOfFameMembers.contains("Amaury Valdes"));
    
    // Adding duplicate records
    HallOfFameMembers.add("Lou Gehrig");
    HallOfFameMembers.add("Babe Ruth");
    HallOfFameMembers.add("Yogi Berra");
    
    // Display the number of elements in LinkedList
    System.out.println("Size of LinkedList: " 
                               + HallOfFameMembers.size());

    // Check to see if the LinkedList is empty
    System.out.println("Is LinkedList Empty: " 
                               + HallOfFameMembers.isEmpty() + "n");

    // Display the LinkedList object
    System.out.println(HallOfFameMembers);

    // Remove the null entry in HallOfFameMembers
    HallOfFameMembers.remove(null);
    
    // Display the LinkedList object
    System.out.println(HallOfFameMembers);
    
    // Display the LinkedList using foreach loop
    System.out.println("Displaying the full List of 
                                  Baseball HallOfFameMembers");
    int count = 0;
    for (String player : HallOfFameMembers) {
      count++;
      System.out.format("[%d]: %sn", count, player);
    }
  } 
}

Output

Is LinkedList Empty: true
Adding 10 elements...
Adding null element...

Checking if Willie Mays is in HallOfFameMembers... true
Checking if Amaury Valdes is in HallOfFameMembers... false

Size of LinkedList: 14
Is LinkedList Empty: false

[Babe Ruth, Ty Cobb, Lou Gehrig, Ted Williams, Hank Aaron, Yogi Berra, Willie Mays, 
Jim Palmer, Tom Seaver, Nolan Ryan, null, Lou Gehrig, Babe Ruth, Yogi Berra]
[Babe Ruth, Ty Cobb, Lou Gehrig, Ted Williams, Hank Aaron, Yogi Berra, Willie Mays, 
Jim Palmer, Tom Seaver, Nolan Ryan, Lou Gehrig, Babe Ruth, Yogi Berra]

Displaying the full List of Baseball HallOfFameMembers...
[1]: Babe Ruth
[2]: Ty Cobb
[3]: Lou Gehrig
[4]: Ted Williams
[5]: Hank Aaron
[6]: Yogi Berra
[7]: Willie Mays
[8]: Jim Palmer
[9]: Tom Seaver
[10]: Nolan Ryan
[11]: Lou Gehrig
[12]: Babe Ruth
[13]: Yogi Berra