Linked Lists

[chili5]

Linked Lists in Java

The java.util package provides a linked list class. A linked list is a structure where you have a bunch of nodes that contain pointers to the next item in the list. When you take a data structures class you use a Node class to implement this structure.

A node class might look like this:

class Node {
	int data;
	Node next;
}

Then the only way to iterate is with an 0(n) scan of the list. However, these structures provide 0(1) access to add and remove any items from any point in the list.

Adding an item is as simple as this:

Node new = new Node();
Node temp;

temp = old.next;
old.next = new;
new.next = temp;

In theory a linked list would have a pointer to the previous and first items. Meaning we wouldn't have to keep track of the position we are inserting the new item at and the node before the location of the new item. However, this tutorial is not about implementing linked structures.

You should know that the linked list is not a direct-access container.

The Java class

The nice thing about the java linked list class is it is a direct-access container. I know I just said that these structures aren't. The Java ones are.

The constructor for this class is:

public LinkedList() {
        header.next = header.previous = header;
    }

This shows that each node simply references another node. I don't quite know how it provides direct access with this structure. The reality is to provide direct-access items must reside in adjacent memory blocks. Which in these types of structures, is not always the case. The header original points to itself indicating that the list is done. You will either have a node that reference itself as the next node or a null value indicating the end of the list.

Okay I was wrong, it doesn't provide direct access. Each node is given an index but to find it the class must do an iterative scan. Thus you get an 0(n) scan to find the item. The use of a get method appears to provide direct-access but it does not.

The code is this:

private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> e = header;
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }

Basically if the index is less than the size than we keep moving forward until we have found the item with that index. This is the return value, otherwise we move backwards until we have found the item with that index.

Creating a new Linked List

The Linked List is a generic class so it can hold any type of data you want. Note, it can only hold objects. It cannot hold primitives like you can in C++.

Example of creating a new linked list:

LinkedList<String> out = new LinkedList<String>();

Returning the first item in the list. Since the linked list maintains a reference to the first item in the list, all you have to do is call getFirst() which returns a reference to the first item in the list. This methods throws a NoSuchElementException of the list is empty.

Node start = list.getFirst();

Getting the Last Item in the List

Similary, the list contains a reference to the last node. Giving you 0(1) access to the end of the list. All you have to do is call getLast. The getFirst and getLast give you fast access to elements making this structure perfect for implementing a stack and a queue. However, there are two methods that are even better for implementing queues and stacks.

Node last = list.getLast();

That simply returns the last item (well a reference to it). It doesn't remove it from the structure, which disqualifies it for using in implementing queues and stacks.

These two methods leave the item in the structure.

Removing the last item

You simply call the removeLast method which returns the last item from the structure and removes it.

Example:

Node last = list.removeLast();

Removing the first item in the list.

Node start = list.removeFirst();

This method, removes the first item from the list. It also returns a reference to the item.

Since these methods remove the first and last items. It makes them perfect for using in implementing stacks and vectors. Which brings up the question, why did the Java developers use a vector? You can get 0(1) access for adding items to the front and the end, and removing items from the front and the end. So you don't need access to items in the middle, so why even use a vector?

addFirst and addLast methods

Since we have a reference to the first and last items, it is quick and fast to add items to the last item. These methods are called addFirst and addLast respectively.

To add a new item to the list, I do this:

Node newNode = new Node();
list.addFirst(newNode);

This method assumes, that I have a list that is holding Node objects.

Similarly, to add an item at the end of the list I simply write:

Node newNode = new Node();
list.addLast(newNode);

Number of elements

The class maintains a counter of how many items are in the list. So to find out how many items are in the list, you simply call list.size().

Example:

System.out.println(list.size());

Removing items

To remove an item, you simply pass the item you want to remove to the remove method. The method then looks for the item and removes it once it finds it. It will return true if it found the item, and removed it. Otherwise, it will return false. The method has to find it because there is no direct-access.

if (list.remove(5)) {
	System.out.println("Five was removed.");
} else {
	System.out.println("Not found.");
}

Get method

You can access items using an index and get the get method. This method searches for the item with that index. The indices are assigned in the order that you added the items. Alternatively, you can specify an index to use.

Add Method

You can use the add method to add items to the structure. You can either pass in the index you want to use, along with the element or just pass the element you want to add.

Examples:

list.add(5); // chooses it's own index
list.add(3,2);

There are other methods, push, pop and others that let you treat this like a stack and queue. It also contains methods contains, indexOf and others.

Final thoughts?

At several parts of this tutorial, I have said things and then immediately said something that contradicts what I just said. Why? As I was writing this I was learning about the structure of these structures by reading the code by the java developers. I learn a lot about different structures this way. Instead of removing the false information, I decided to make a node about the learning process and show how I've learned lots by looking at the implementation of the linked list.

For instance, I saw a get method so I assumed direct-access with some incredible trick but looking at the method proved my assumption false. Nothing wrong with making assumptions, and finding out that you were wrong. Not very many people probably learn about a structure by looking at the JDK source code.

I like this structure best. It is great when you don't require direct-access. You can even use it for cases where direct-access would be nice, if you need fast insertion and deletion.

[Jordan]

Nice tutorial, full of information. +rep

[WingedPanther]

The advantage of a linked list appears when you have large data structures in each node. You don't have to shuffle all the other nodes around, just a few links.