Java for Humans {Data Structures: LinkedLists}

Lincoln W Daniel
Jan 18, 2016 · 6 min read
View Table of Contents | Download Supporting Code | Subscribe to ModernNerd Youtube Channel for Coding Videos | By Lincoln W Daniel

Our phone book from the Arrays chapter could only hold a fixed number of our friends’ contact information because it was made with an array. We bounded our phone book by implementing it as an array because it makes sense: your phone only has a limited amount of storage space, so we can only store a limited amount of contacts. Arrays are best when you know how many elements you will be collecting, but there are other situations where it doesn’t make sense to bound the capacity of our collection. For those situations, dynamically expanding lists are best.

Why Lists are Important & Useful

Unlike arrays, lists in Java can expand without bounds. You may use a list to accumulate and collect things you don’t know the bounds of, such as the people you meet in your life time, the places you’ve been, the skills you learn, the movies you want to watch. If you’ve ever heard of a “Bucket List”, it is the best application of a list: toss everything you want to do into the bucket and mark them as done as you accomplish them.

The Java List class is an interface from which we can implement any kind of list subclass we’d like. Java provides us two popular implementations of the List interface — LinkedList and ArrayList — but we will focus on the LinkedList in this chapter because you already know much of how an ArrayList works; an ArrayList is simply an array with convenient instance methods and a dynamically expanding capacity. It also works very similarly to a LinkedList, so you’ll be able to learn it by analogy later.

LinkedLists

A LinkedList is a special type of data structure that allows us to link elements together in a line without bounds. Elements of a LinkedList are referred to as nodes and each node has a pointer field pointing to its left neighbor and another pointing to its right neighbor.

A node has a minimum of three instance fields: its two pointers which are int values, and its data field which holds the actual data. The datatype of a LinkedList, or any data structure for that matter, is the datatype of its elements and all elements must be of the same type.

There are only six functions you need to know to get started working with the LinkedList class. LinkedLists have a size() instance method that returns the number of nodes in the list. You can add elements to a LinkedList by passing the object as an argument to the list’s add() instance method. If you want to check if an object is already in the list before you try to add it again, you can call the contains() instance method and provide it the object to check as an argument.

When you want to access an element of a list, you must provide its position in the list as an argument to the list’s get() instance method. A reference to the object stored in the node at that position in the list will be returned. If you want to remove an element from the list, simply pass its position as an argument to the list’s remove() instance method. Finally, you can remove all elements from the list by calling the clear() method.

When we initialize our LinkedList, we must specify the type of data that can be stored in our LinkedList. To do that, we place the type’s class name between a set of opening and closing arrows <>. Let’s see how we can use a LinkedList instance to make our bucket list of things we want to do this year:

public class Thing {
...

@Override
public String toString() {
if(done) { return name + " is done.";}
else { return name + " is not done";}
}
}
LinkedList<Thing> bucketList = new LinkedList<Thing>();

Our Thing class has only two instance fields: a String name and a boolean done. We can get the name of a Thing instance by calling the getName() instance method and we can mark a Thing as done by calling the markDone() instance method. We can check if a Thing is done by calling its isDone() instance method. Finally, our Thing class overrides the toString() instance method of its implicit superclass, Object. Let’s add some things to do to our bucket list:

bucketList.add(new Thing("Bungee Jump"));
Thing learnJava = new Thing("Learn Java");
bucketList.add(learnJava);
bucketList.add(new Thing("Build an Android Application"));
bucketList.add(new Thing("Travel to the Bermuda Triangle"));

We want to go bungee jumping, learn Java, build an Android application, and travel to the Bermuda Triangle. We are currently learning Java, so we can’t mark it as done just yet. Say we complete bungee jumping, we can mark the “Bungee Jump” Thing as done by calling the get() method on our bucketList object to get it and call its own markDone() instance method on it. Because “Bungee Jump” is the first element in the list, its position is zero (0):

Thing bungeeJump = bucketList.get(0);
bungeeJump.markDone();

To get the first or last element of the list, we could also call its getFirst() or getLast() instance methods respectively. Let’s traverse our bucket list and print out everything we have to do:

for(int position = 0; position < bucketList.size(); position++){
Thing thingToDo = bucketList.get(position);
System.out.println("Thing at position " + position
+ ": " +thingToDo);
}
/*Prints:
Thing at position 0: Bungee Jump is done.
Thing at position 1: Learn Java is not done
Thing at position 2: Build an Android Application is not done
Thing at position 3: Travel to the Bermuda Triangle is not done
*/

From that code snippet, we can see that we are looping over, traversing our bucket list by using the increasing position value to retrieve elements from the list by their position in the list. The first element, “Bungee Jump”, is rightfully the only Thing in the list that is “done”. We’ve traveled to the Bermuda Triangle, so we’ll mark that as done, too. At the end of each day, we should remove everything that we have done from our list:

bucketList.getLast().markDone();
for(int position = 0; position < bucketList.size(); position++){
Thing thingToDo = bucketList.get(position);
if(thingToDo.isDone()) {
bucketList.remove(thingToDo);
}
}
System.out.println("Things left to do: " + bucketList.size());
//prints "Things left to do: 2"

Now we only have two things left in our bucket list. Let’s imagine we have read all the way through Java for Humans and developed an Android application. That would mean we can mark those two things as done on our list. Given that we only have those two things left, instead of removing them one at a time, we can simply empty our entire bucket list by clearing our LinkedList:

bucketList.clear();
System.out.println("Things left to do: " + bucketList.size());
//prints "Things left to do: 0"

Now our bucket list is empty. However, we lied about having learned Java, so let’s add that back to our bucket list and make sure it was successfully added by checking if the list contains it:

System.out.println(bucketList.contains(learnJava));
//prints "false"
bucketList.add(learnJava);
System.out.println(bucketList.contains(learnJava));
//prints "true"
System.out.println(bucketList.contains(new Thing("Learn Java")));
//prints "false"

The contains method only returns true if the provided object is a reference to an object in the list. Although the two Thing instances with a name value of “Learn Java” appear to be the same, they are not because they don’t reference one another. This is something you should do some more research on because its beyond the scope of this book.

One final method you should be aware of is the isEmpty() instance method which returns true if the list has no elements in it. That’s it. We have used all of the essential instance methods of a LinkedList and those methods are all in other implementations of the List interface. Try to expand your bucket list here by adding more Java concepts you want to learn to the list.


ModernNerd Code

Learn to Code Life. Subscribe to Video Tutorials on Youtube

Lincoln W Daniel

Written by

My passion is in developing software to enable people to accomplish their goals more efficiently. Author @JavaForHumans.com. Creator of @Smedian.com

ModernNerd Code

Learn to Code Life. Subscribe to Video Tutorials on Youtube

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade