Home CPSC 340

Contents ▼

Motivation Linked Lists Simple Example Traversing the List A Linked List Class Adding Nodes

Linked Lists

Motivation

So far we have seen the array data structure. Arrays are good for many tasks, but there are several array operations which are inefficient:

• Inserting into the beginning or middle.
• Removing an item from the beginning or middle.
• Adding to a full array.
• Expanding or shrinking the array.

Linked lists store a sequence of data, just like an array, but in a manner which makes the above operations more efficient.

Linked Lists

A linked list is a fundamental data structure. The basic idea is that the list is composed of "nodes". Each node node contains one data element and the link to the next node in the list.

Unlike arrays, the elements in a linked list are not stored in order in memory. In order to loop through the linked list, we must follow the links in each node to find the location of the next item in the list. In Java, the links are references. So each node in the list contains a reference to the next node.

The first node in the linked list is called the "head". The location of the head must be stored so that we can find the rest of the list. The last element of the list is the one that doesn't contain a valid link to another node. In Java, we accomplish this by setting the reference in the last node to null.

Simple Example

We will start by making a class called "Node" which stores two things: a piece of data, and a reference to the next node:

class Node {
    public int data;
    public Node next;
}

We can create then make a linked list by creating a number of these Node objects, and linking them together with the references. This example demonstrates creating a simple linked list in this manner:

public class LinkedList1 {
    public static void main(String args[]) {
        // make 5 nodes for the list
        Node a = new Node();
        Node b = new Node();
        Node c = new Node();
        Node d = new Node();
        Node e = new Node();

        // set up the data
        a.data = 10;
        b.data = 20;
        c.data = 30;
        d.data = 40;
        e.data = 50;

        // set up the links
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = null;
    }
}

This program generates the following list:

Traversing the List

In order to loop through the list, we start with the first node, the head, and follow the links until we hit one with null for the next reference. That marks the end of the linked list.

The following code will print the list we made in the previous example:

public static void print(Node head) {
    Node current = head;
    while (current != null) {
        System.out.println(current.data);
        current = current.next;
    }
}

A Linked List Class

In the examples above, we created a fixed number of nodes and linked them together. Instead of making the nodes "manually" in main like this, we will begin writing a linked list class to manage making all the nodes.

We'll begin by making a generic class called LinkedList. Inside this class, we will put the Node class. In Java you can nest classes like this. This makes sense because the only purpose for Node is to help the LinkedList class:

class LinkedList<Type> {
    // a Node of the list
    private class Node {
        public Type data;
        public Node next;
    }

Notice the data stored in each Node uses our type variable, which allows us to make any kind of LinkedList we want.

The only data the LinkedList class needs to store itself is the head node. All we do in the constructor is set the head to null. Just like our DynamicList, the LinkedList will start empty until we add to it:

    // the head of the list is first node
    private Node head;

    // the list starts empty
    public LinkedList() {
        head = null;
    } 

Now we can include the print method we wrote earlier as a method of LinkedList:

    // print the list from start to finsih
    public void print() {
        Node current = head;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }

Adding Nodes

The only other thing we absolutely need for our simple linked list class is a way to add new data. We will add a method to the class which takes a piece of data and adds it.

It is actually easier and faster to add data to the beginning of the list than to the end. That's because the beginning of the list is the only element we can actually reference directly.

Adding to the start of the list consists of 4 steps:

1. Create a new Node object.
2. Store the data we're adding into this node.
3. Point the new node's next link to the current head.
4. Set the new node to be the head of the list.

Note that the order of these steps is important. If we re-arrange steps 3 and 4, we would have lost the existing part of the list!

The code for this appears below:

    // add an item to the list
    public void add(Type item) {
        Node newNode = new Node();
        newNode.data = item;
        newNode.next = head;
        head = newNode;
    }

The complete program also tests out the add and print methods. Why does it print backwards?

Next class we will add some more capabilities to this LinkedList class:

• Adding to the end of the list
• Removing from the list

Copyright © 2024 Ian Finlayson | Licensed under a Creative Commons BY-NC-SA 4.0 License.