The use of Data Structures in Java
by Steve Ochani http://www.steveo.us
v 1.1 March 5th, 2008.
v 1.0 July 7th, 2006.
Purpose: To show the use, through code examples, of Data Structures such as stacks, queues, linked lists and hash tables that come with the Java Development Kit (JDK) as parts of the java.util package and to show that there isn't a need to "re-invent" the wheel once you know how it works.
Intended audience: This document is intended for people who have taken at least the first Computer Science course offered at most colleges and universities. It will be more appreciated by people who have taken the second CS course and/or a data structures course also.
Why it was written: Students are shown in CS1, CS2 and CS3 how to build data structures such as queues and linked lists manually but they are rarely shown that they exist in modern programming languages such as Java. In my opinion it is like showing students how to do calculus manually all by hand and never shown any shortcuts or/and how to use the calculator.
Once a student understands what these data structures are there is no reason to re-invent the wheel. Often times programmers will need to use these data structures as part of their work in the "real world" and it would be just plain foolish to re-invent the wheel and create your own data structure when one already exists in the language. Re-creating the wheel also introduces opportunity for errors in the code.
Structure of this document: There are four sections of this document: ArrayLists, Stacks, LinkedLists and HashTables. All of the sections are mainly sample source code that shows the use of the data structure. Each section also has the URL of the javadoc page from SUN that has the details about the data structure in that section.
You can click any of the links below to jump to that section within this Document.
ArrayLists
So let's begin. The first data structure that most people are taught is an Array. The classic problems with arrays are that they have a definite size that cannot be changed. Another problem is that they are not as safe as some of the other data structures.
The ArrayList solves a lot of those problems and adds many features that are not part of a classic array. The following is example code that I encourage you to look over and compile/run yourself to see the results. Majority of the code is self explained with the use of System.out.println so pay attention to the print outs.
// http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html
import java.util.*;
public class TestArray
{
public static void main(String[] args)
{
System.out.println("Demo program for java.util.ArrayList");
System.out.println();
// arraylist is FIFO (First In First Out)
// ArrayList myList = new ArrayList();
// above code will still work in Java 1.5/1.6 but will
// give warnings
ArrayList<String> myList = new ArrayList<String>();
// add initial items
System.out.println("Adding items to the list");
myList.add("item1");
myList.add("item2");
myList.add("item3");
myList.add("item4");
System.out.println();
System.out.println("There are " + myList.size() + " items in the list.");
System.out.println();
System.out.println("Here is the list, output method 1");
// output list
for (Iterator<String> iter = myList.iterator(); iter.hasNext();)
{
System.out.println(iter.next());
}
System.out.println();
System.out.println("Here is the list, output method 2");
for (int i = 0; i < myList.size(); i++)
{
System.out.println(myList.get(i));
}
System.out.println();
System.out.println();
System.out.println("Here is the list, output method 3, using toString()");
// remember that you do not have to explicitly call the toString()
// method since java is "smart" enough to know when to call it
// automatically
System.out.println(myList); // calls toString() of ArrayList
System.out.println();
System.out.println();
System.out.println("Removing 2nd Item");
// remove 2nd item
// the remove method takes in a 0 based index
int indexOfItemToRemove = 1;
String removedItem = (String)myList.remove(indexOfItemToRemove);
System.out.println();
System.out.println("Removed : " + removedItem);
System.out.println();
System.out.println("Here is the list after removal of an item");
for (Iterator<String> iter = myList.iterator(); iter.hasNext();)
{
System.out.println(iter.next());
}
System.out.println();
System.out.println("Adding (inserting) item back to it's position");
myList.add(indexOfItemToRemove, removedItem);
System.out.println();
System.out.println("Here is the list after additon of item");
for (Iterator<String> iter = myList.iterator(); iter.hasNext();)
{
System.out.println(iter.next());
}
System.out.println();
System.out.println("Adding several more items");
// adding several more items in an unsorted manner
myList.add("item9");
myList.add("item7");
myList.add("item8");
myList.add("item6");
System.out.println();
System.out.println("Here is the list after additon of several items, unsorted");
for (Iterator<String> iter = myList.iterator(); iter.hasNext();)
{
System.out.println(iter.next());
}
System.out.println();
System.out.println("Sorting items");
Collections.sort(myList);
System.out.println();
System.out.println("Here is the list after sorting");
for (Iterator<String> iter = myList.iterator(); iter.hasNext();)
{
System.out.println(iter.next());
}
// searching on item that doesn't exist
String searchItem = "Hello";
System.out.println();
System.out.println("Searching for " + searchItem);
boolean searchResult = myList.contains(searchItem);
if(searchResult == true)
System.out.println("Item found at position " + myList.indexOf(searchItem));
else
System.out.println("Item NOT found");
// searching on item that does exist
searchItem = "item8";
System.out.println();
System.out.println("Searching for " + searchItem);
searchResult = myList.contains(searchItem);
if(searchResult == true)
System.out.println("Item found at position " + myList.indexOf(searchItem));
else
System.out.println("Item NOT found");
System.out.println();
}
}
Output for above program
In my above example you can see how easy it is to sort the list of Strings in the ArrayList by simply calling
Collections.sort(myList);If you were working with your own objects remember to implement the Comparable interface and declare and properly code the compareTo method in your class. Without the compareTo method the sorting will not work.
Stacks
Now we move on to Stacks. Stacks are very similar to ArrayLists.
Stacks traditionally are LIFO (Last In First Out) meaning that the last item you push on to the Stack is the first one that comes off, however, in the java.util.Stack data structure you can pull items out that are not on the top. If you're going to do that then you might was well use the ArrayList data structure.
Again, I feel it's always best to explain through source code examples, so here it is:
// http://java.sun.com/j2se/1.5.0/docs/api/java/util/Stack.html
import java.util.*;
public class StackTest
{
public static void main(String[] args)
{
System.out.println("Demo program for java.util.Stack");
System.out.println();
Stack<String> myStack = new Stack<String>();
// add initial items
System.out.println("Pushing items on to the stack");
myStack.push("item1");
myStack.push("item2");
myStack.push("item3");
myStack.push("item4");
System.out.println();
System.out.println("There are " + myStack.size() + " items in the stack.");
System.out.println();
System.out.println("Here is the stack, output method 1");
// output stack
for (Iterator<String> iter = myStack.iterator(); iter.hasNext();)
{
System.out.println(iter.next());
}
System.out.println();
System.out.println("Here is the stack, output method 2");
for (int i = 0; i < myStack.size(); i++)
{
System.out.println(myStack.get(i));
}
System.out.println();
System.out.println();
System.out.println("Here is the stack, output method 2 but printed backwards");
System.out.println("to show the traditional stack output");
for (int i = myStack.size() - 1; i >=0 ; i--)
{
System.out.println(myStack.get(i));
}
System.out.println();
System.out.println();
System.out.println("Here is the stack, output method 3, using toString()");
System.out.println(myStack);
System.out.println();
System.out.println("Top of the stack is : " + myStack.peek());
System.out.println();
System.out.println("Popping all the items from the stack");
// pop all items and print them
for (Iterator<String> iter = myStack.iterator(); iter.hasNext();)
{
System.out.println(myStack.pop());
}
System.out.println();
System.out.println("Now there are " + myStack.size() + " items in the stack.");
// add items again
System.out.println();
System.out.println("Pushing items on to the stack");
myStack.push("item2");
myStack.push("item1");
myStack.push("item4");
myStack.push("item7");
myStack.push("item6");
myStack.push("item5");
myStack.push("item9");
System.out.println();
System.out.println("Here is the stack after addition of new items, unsorted");
System.out.println(myStack);
System.out.println();
System.out.println("Sorting items");
Collections.sort(myStack);
System.out.println();
System.out.println("Here is the stack after sorting");
System.out.println(myStack);
// searching on item that doesn't exist
String searchItem = "Hello";
System.out.println();
System.out.println("Searching for " + searchItem);
boolean searchResult = myStack.contains(searchItem);
if(searchResult == true)
System.out.println("Item found at position " + myStack.indexOf(searchItem));
else
System.out.println("Item NOT found");
// searching on item that does exist
searchItem = "item6";
System.out.println();
System.out.println("Searching for " + searchItem);
searchResult = myStack.contains(searchItem);
if(searchResult == true)
System.out.println("Item found at position " + myStack.indexOf(searchItem));
else
System.out.println("Item NOT found");
System.out.println();
System.out.println("Searching with alternate method which returns");
System.out.println("1 based position from top of stack");
// alternate way of searching using the search method
// search method returns 1 based position from top of stack
// -1 if it's not in the stack
int position = myStack.search(searchItem);
if(position != -1)
System.out.println("Item found at position " + position);
else
System.out.println("Item NOT found");
}
}
Output for above program
As you can see in the above code it is very easy to access items that are not on the top with the get method. The traditional pop method still works the way you expect: it pops the top item off the stack each time you call it. The search method also works in a traditional top down manner, it gives a 1 based position from the top of the stack.
Linked Lists
Moving on to one of the most important yet usually most painful/pain to implement Data Structures, Linked Lists. Using the Linked List data structure is just as easy to use as is the ArrayList data structure. Again, check the code for yourself:
// http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html
import java.util.*;
public class LinkedListTest
{
public static void main(String[] args)
{
System.out.println("Demo program for java.util.LinkedList");
System.out.println();
LinkedList<String> linkList = new LinkedList<String>();
// add initial items
System.out.println("Adding items to the list");
linkList.add("item1");
linkList.add("item2");
linkList.add("item3");
linkList.add("item4");
System.out.println();
System.out.println("There are " + linkList.size() + " items in the list.");
System.out.println();
System.out.println("Here is the list, output method 1");
// output list
for (Iterator<String> iter = linkList.iterator(); iter.hasNext();)
{
System.out.println(iter.next());
}
System.out.println();
System.out.println("Here is the list, output method 2");
for (int i = 0; i < linkList.size(); i++)
{
System.out.println(linkList.get(i));
}
System.out.println();
System.out.println();
System.out.println("Here is the list, output method 3, using toString()");
System.out.println(linkList);
System.out.println();
int indexOfItemToRemove = 1;
// remove 2nd item
String removedItem = linkList.remove(indexOfItemToRemove);
System.out.println();
System.out.println("removed : " + removedItem);
System.out.println();
System.out.println("Here is the list after removal of an item");
for (Iterator<String> iter = linkList.iterator(); iter.hasNext();)
{
System.out.println(iter.next());
}
System.out.println();
System.out.println("Adding (inserting) item back to it's position");
linkList.add(indexOfItemToRemove, removedItem);
System.out.println();
System.out.println("Here is the list after additon of item");
for (Iterator<String> iter = linkList.iterator(); iter.hasNext();)
{
System.out.println(iter.next());
}
System.out.println();
System.out.println("Adding several more items");
// adding some more items in an unsorted manner
linkList.add("item9");
linkList.add("item6");
System.out.println();
System.out.println("Here is the list after addition of several items, unsorted");
for (Iterator<String> iter = linkList.iterator(); iter.hasNext();)
{
System.out.println(iter.next());
}
System.out.println();
System.out.println("Sorting items");
Collections.sort(linkList);
System.out.println();
System.out.println("Here is the list after sorting");
for (Iterator<String> iter = linkList.iterator(); iter.hasNext();)
{
System.out.println(iter.next());
}
// searching on item that doesn't exist
String searchItem = "Hello";
System.out.println();
System.out.println("Searching for " + searchItem);
boolean searchResult = linkList.contains(searchItem);
if(searchResult == true)
System.out.println("Item found at position " + linkList.indexOf(searchItem));
else
System.out.println("Item NOT found");
// searching on item that does exist
searchItem = "item8";
System.out.println();
System.out.println("Searching for " + searchItem);
searchResult = linkList.contains(searchItem);
if(searchResult == true)
System.out.println("Item found at position " + linkList.indexOf(searchItem));
else
System.out.println("Item NOT found");
System.out.println();
System.out.println();
System.out.println("The LinkedList is almost identical to the ArrayList");
System.out.println("However it has some additional methods such as");
System.out.println("addFirst method - which adds an item to the beginning of the list");
System.out.println();
System.out.println("Adding items using addfirst method");
linkList.addFirst("item5");
linkList.addFirst("item7");
System.out.println();
System.out.println("Here is the list after adding items to the beginning");
System.out.println(linkList);
}
}
Output for above program
By default when adding items in the linked list by using the add method the items are added at the end of the list. As the above code shows there are two ways of adding nodes in other places:
use the addFirst method which adds the item to the beginning of the list
use the overloaded add method which takes the position as the first parameter.
HashTables
Last but not least is the HashTable. HashTables, like the previous data structures are pretty straightforward to use as shown by the code below.
// http://java.sun.com/j2se/1.5.0/docs/api/java/util/Hashtable.html
import java.util.*;
public class HashTableTest
{
public static void main(String[] args)
{
System.out.println("Demo program for java.util.Hashtable");
System.out.println();
Hashtable<Integer, String> items = new Hashtable<Integer, String>();
System.out.println("Adding items to hashtable");
// Integer objects are the keys, Strings are the values
items.put(new Integer(1), "item1");
items.put(new Integer(2), "item2");
items.put(new Integer(3), "item3");
System.out.println();
System.out.println("There are " + items.size() + " items in the hashtable");
// output hashtable
System.out.println();
System.out.println("Printing the items two diff. ways");
for (Enumeration<String> e = items.elements(); e.hasMoreElements() ;)
{
System.out.println(e.nextElement());
}
// output list using toString of Hashtable
System.out.println();
System.out.println(items);
System.out.println();
System.out.println("Printing item with key of 2");
// retrieving item with key
String s = items.get(new Integer(2));
if (s != null)
System.out.println("2 = " + s);
else
System.out.println("Item does not exist in hashtable");
// test if hashtable contains certain key
boolean found = false;
System.out.println();
System.out.println("Searching for key 10");
found = items.containsKey(new Integer(10));
if (found == true)
System.out.println("Hashtable contains the key");
else
System.out.println("Hashtable does not contain the key");
System.out.println();
System.out.println("Searching for value item3");
found = items.containsValue("item3");
if (found == true)
System.out.println("Hashtable contains the value");
else
System.out.println("Hashtable does not contain the value");
System.out.println();
System.out.println("Removing item with key of 3");
// remove method takes key and returns the value that it removed
System.out.println("Removed item: " + items.remove(new Integer(3)));
System.out.println();
System.out.println("There are " + items.size() + " items in the hashtable now");
// output hashtable
System.out.println();
System.out.println(items);
}
}
Output for above program
Keep in mind that if you add another item with a key that already exists in the table then that new value will overwrite the previous value. So if I put the following line at the end of the program:
items.put(new Integer(2), "item20");
this will overwrite "item2"
I hope you have found the document useful.
-Steve O.
EOF