Linked Lists

Up until now, we have been working with data structures which are backed by simple arrays of objects or generics. While this allows us to implement some interesting structures, it is somewhat limited. To eliminate some of the limitations of this type of structure, we need to change the way we look at data storage. We need data nodes.

Node:

A linked list is a data structure comprised by a series of Nodes. A Node is a simple object composed of a variable to store the data and a link to the next Node. Below is a visual and Java representation of a Node:

public class Node<E> {

    private E data;

    private Node<E> next;

    public Node(E data) {

        this.data = data;

    public Node getNext() {

        return next;

    public void setNext(Node<E> next) {

        this.next = next;

    public Node getData() {

        return data;

Nodes are created with data passed to the constructor. The data is typically only set once, during construction, but sometimes adding a setData(E data) method is useful.

Linked List [Java 8 LinkedList]

Linked lists can follow the same interface as a regular list. We will be using the ISimpleList<E> interface presented in the Lists lesson. The major difference is that now we won't be backing our list with an array, we will instead be backing it with Node objects.

The Linked List class itself must have a root Node representing the first item in the list. Other than that there are no other necessary instance variables. There are, however, a few useful ones:

tail - The last item in the linked list.
size - The size of the linked list.

Some notes about HOW to implement a Linked List:

In order to do any work at a particular index, you must first traverse the list to the desired position. This can be done via code that looks similar to this:

Node<E> val = root;

for (int i = 0; i < index; ++i) {

    if (val.getNext() != null) {

        val = val.getNext();

The last element in the list must have it's next value set to null in order to terminate the list.
The size of the array must be counted every time unless you store the value in an integer and keep it updated whenever any values are added or removed.
In order to remove an item in the linked list, you must:
1. Traverse to the Node BEFORE the appropriate index (n-1). Call this Node A.
2. Find the Node that occurs AFTER the appropriate index (n+1). Call this Node B.
3. Set the next value of A to B. Visual below:

Replace commands can work similarly to remove commands, except you can either replace the existing data in the Node, or create a new Node and set the next variable equal to the new data.

LINKS:

public interface ISimpleList<E> {

/**

     * Appeds an element e to the end of the list. Returns

     * success status.

     * @param e - the element to be added to the end

     * @return boolean - true if and only if the add was

     *        successful.

*/

    boolean add(E e);

/**

     * Inserts an element, e, into the list without losing

     * or reordering existing data.

     * @param i - the index to insert the element.

     * @param e - the element being inserted.

     * @return boolean - true if and only if the add was

     *        successful.

*/

    boolean insert(int i, E e);

/**

     * Replaces the element at index i with new element e.

     * Returns the old element.

     * @param i - the index of the element being replaced.

     * @param e - the element being placed into the list.

     * @return E - The previous element from the index

*/

    E replace(int i, E e);

/**

     * Removes the element at index i and returns it.

     * @param i - the index of the element being removed.

     * @return E - the item that was removed.

*/

    E remove(int i);

/**

     * Returns the element at index i

     * @param i - the index of the element

     * @return E - the item at the specified index.

*/

    E get(int index);

/**

     * Removes all elements from the list

*/

    void clear();

/**

     * Returns the number of elements currently in the list.

     * @return int - the number of elements in the list

*/

    int size();

/**

     * Returns true if and only if the list has more than

     * zero elements.

     * @return boolean - true if and only if there are no

     *         elements in the list.

*/

    boolean isEmpty();

/**

     * Returns a new SimpleList which contains the elements

     * starting at startIndex inclusive and ending at

     * endIndex exclusive.

     * @param startIndex - the beginning index of the

     *        new sublist, inclusive.

     * @param endIndex - the index at which to stop. The

     *        element at this index is not included in the

     *        returned sublist.

     * @return ISimpleList<E> - A new list object containing

     *        the specified elements.

*/

    ISimpleList<E> subList(int startIndex, int endIndex);

Report abuse