Java’s LinkedList Data Structure by Example

Java’s Data Structure Illustrated

One way to get exposure to a specific data structure is to simply read the documentation. But it won’t sink in thoroughly until you create your own example. In this article, we’ll look at the LinkedList class. The phone directory seems to be the example of choice by most college professors to introduce this data structure. Within our phone directory program, we’ll want to be able to:

  1. add a new record,
  2. delete the current record,
  3. change the first name of the current record,
  4. change the last name of the current record,
  5. change the phone number of the current record,
  6. select the current record,
  7. show all records and
  8. quit the program.

The phone directory will store the first name, last name and the phone number. When inserting, we’re going to want to insert the new record into the correct order without creating or using a sorting algorithm. You may have duplicate names but not duplicate phone numbers. The phone directory should be sorted by last name, first name, phone number. When deleting a record, there will not be a current record that’s selected. To select the record after deletion, you must use the select the current record option. You will not be able to change the first name, last name or phone number unless the current record is selected.

Below is my phone directory program. To help follow the logic, start with the main() method. It instantiates the class in which it’s located and calls the start() method. If you look above the main() method, you’ll notice three instance variablesLinkedList<Person> personsScanner input, and int currentRecord. The persons variable is where you will store Person objects into when you create them (going to the bottom of the class you’ll notice a nested class called Person that has the firstName, lastName, and phoneNumber instance variables). The input variable is of type Scanner meaning that it awaits user input when we need it. And the currentRecord variable holds the current record.

When you call the start() method, a prompt is displayed and the user has the option to enter a value. If they don’t select from the available values, an error is displayed and the user is asked to enter one of the available values again. A common approach to using the phone directory may be as follows:

  1. The user selects to add a new record.
  • Prompted to enter the first name.
  • Prompted to enter the last name.
  • Prompted to enter the phone number.
  • Checks to make sure that the phone number is correct.
  • Checks to make sure that the phone number is not in the LinkedList already.
  • Creates a new Person object.
  • Calls the getIndexOfInsertion() method to figure out where to insert the newly created Person object in order.
  • Inserts the Person object into the persons LinkedList in the correct order.
  • Displays the current record.

2. The user selects to change the first name

  • Prompted to enter first name.
  • Gets the current record and stores it in a temp variable.
  • Deletes the current record from the LinkedList.
  • Modifies the first name in the Person object that’s stored in the temp variable.
  • Since the changing of the first name might alter the position in the phone directory, a call to getIndexOfInsertion() is made.
  • The updated Person is re-inserted into the persons LinkedList.
  • Current record is displayed.

3. The user selects to change the last name.

  • An almost identical approach is taken as with the changing of the first name.

4. The user selects to change the phone number.

  • A similar approach to changing the first and last name.
  • The only difference is that the program must check and verify that a) the number is correct and b) that the number doesn’t exist in the LinkedList.

5. The user might add a few more records to the phone directory.

6. The user selects to display all records.

  • A presentable list is displayed.
  • Extra attention is applied to make sure that all columns line up properly.
  • I didn’t include a way to resize the column titles, but you may if you choose to. You’ll just have to get the longest first name and last name and go from there.

7. The user selects to delete the current record.

  • The current Person object is removed from the persons LinkedList.

8. The user selects a new current record, adds a new record to the phone directory or exits the program.

Let’s get to it. Create the file and start writing some code. As I mentioned earlier, in my example below, start with the main() method and work from there. Read the preconditions and postconditions of each method. This will tell you the condition that the method expects before use and the type of result that you can expect.


Leave a Reply