Linked Lists

Since arrays must be made of a contiguous section of memory, large arrays become harder to allocate memory for them, especially as the application becomes more complex.

Therefore, developers will often look to using something like a linked list. A linked list incorporates a custom data type. One of the data types which makes it up will be a pointer to the next item in the list. 

If you know the first item in the list, you can then follow the chain to the next item, and the next, and the next. It makes it easy to traverse the list.

However it is not so easy to find an item in the middle of the list, especially if it is a large list. This is the case with many solutions, you have to know what you gain and lose with a given solution, so you can properly choose which method to work with.

Generally you will have two application level variables, top (sometimes called first) and current. If you build a linked list class, then these would be class level variables.

Both of these are pointers to elements on the list. At the beginning, they will hold the same value – the first item as you will start with the beginning of the list. Top might also be referred to as the head, or first, node.

To traverse the list, you will look to the next item inside the current list. This is done by looking at current.next and assigning it to the current item, like you might find below.

function nextItem() {
    current = current.next;
}

To start back at the beginning, you would have a function like:

function topOfList() {
    current = top;
}

Additionally, we will need methods for searching the linked list, as well as adding and removing items from the linked list.

Typically, with a traditional linked list, we can only append elements to the beginning or the end of the list, as this is the easiest process. (Adding to the beginning is the easiest.)

The Linked List Element

Of course, you need an element which you can link together. Typically this is a class which had two attributes, and several methods.

The Link List Element Attributes

The first attribute will be for data we are going to store. This could be a primitive data type, or an object reference. Many times, I will call this attribute, value, as it is the value which we are holding. The second attribute is a reference to the next element in the linked list. This is a reference/pointer and is used to track how all of the chains in the linked list connect together. No element knows about every link in the list, but each one knows about the next element, and with this we can traverse a list.

The Link List Element Methods

There are several methods, including constructors.

When developing a linked list, it is import to think about how you will be creating the elements. For example, you can assume you have a value being passed to your constructor, but will you know about the next element as well? If you might, then you might want to overload the constructor.

See the example of constructors below for a Java Class below.

    public LinkedListElement(int value) {
        this.value = value;
        this.next = null;
    }
    public LinkedListElement(int value, LinkedListElement next) {
        this.value = value;
        this.next = next;
    }

Next you will need to be able to view (get) the value of the element, and the next element. Additionally, you will need to be able to set the next element as well, in case an element is added, or removed from the Linked List.

    public int getValue() {
        return this.value;
    }

    public LinkedListElement getNextElement() {
        return this.next;
    }

    public void setNextElement(LinkedListElement lle) {
        this.next = lle;
    }

You can see that the linked list element is fairly simple, and easy to code, regardless of the language.

The Order of the Linked Elements

One question that always comes up is how do you choose what order your list is in? This depends upon the need of your program. In many cases, we just use the order that they were added.

On the other hand we can choose to sort by any value that is available for us to use. For example, a directory listing of employees might choose to sort the list by name, or department and then name. Each time someone is added to the list, you run through the list until you know where they should be. An insertion sort could then be used.

Consider the following pseudo code where you want to insert movies into a list based upon which is the highest grossing movie. Assume there is a class called movie, and it has the fields of title and boxOffice, with appropriate getters and setters.

Movie current = readMovie();
Movie top = current;

while(toBeInserted = readMovie()) {
    while(current.getNextMovie().getBoxOffice() > toBeInserted.getBoxOffice()) {
        current = current.getNextMovie();
    }
    toBeInserted.setNextMovie(current.getNextMovie());
    current.setNextMovie(toBeInserted);

    current = top;
}

As you read through this code, you can see some basics of what is occurring. First we read a set of data about a movie and get an object returned to us. At this point we don’t care if it was stored in a SQL database, a flat file, or anything else. That’s outside the scope of the example, instead, we just look at the fact that we have this data – and that is an important distinction when working with multi-tiered applications like this example appears to be in.

Next we loop through our list of movies. As long as the current next movie box office receipts is higher than the new movie’s amount we continue to move down the list to the next item. We use this method to traverse the list until we get to where we need to insert our item.

Once we identify the new movie’s position, the new movie’s nextMovie is set to the current movie’s nextMovie, and then the current movie’s nextMovie points to the new movie we are adding to the list. This essentially splices the new one into our list. We then start back at the beginning of our list.

This process might look something like:

while(currentMovie.boxOfficeReciepts > newMovie.boxOfficeReciepts) {
    currentMovie = currentMovie.nextMovie
    newMovie.nextMovie = currentMovie.nextMovie
    currentMovie.nextMovie = newMovie
}

While we would need to add a little error checking into this process, the pseudo code lets you get a good feel for how an insert would work.

Of course, if you don’t care about the order, other than the order it was entered, adding items is even easier. You just need to make your current.nextMovie always equal the newly inserted, and then make your current pointer point to the newly inserted movie. This is much faster for inserting, but slower to search for items later on.

Linked Lists was originally found on Access 2 Learn