# Java Notes: Simple Linked Lists

This shows three programs.

- A simple singly-linked list. This shows the basics.
- A doubly-linked list. This is almost as simple as the singly-linked list, but makes some operations easier.
- Use of the java.util.LinkedList class, which is easy to use because it hides the details.

## Simple singly-linked list done "by hand"

The following program is an example of a very simple implementation of a singly-linked list. You should become very comfortable with this. Altho you should always prefer the predefined `java.util.LinkedList` class when working with linked lists, understanding linking objects is essential to building other structures for which there is no predefined library class.

      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
    // Purpose: Demonstrates a really simple singly-linked list.
    //          Main builds list of words, prints it using two styles.
    // Author : Fred Swartz, 21 Feb 2006, placed in the public domain.

    import java.util.Scanner;

    public class SimpleSinglyLinkedList {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);

            Elem front = null;    // First element of list.
            Elem back  = null;    // Last element of list.

            //... Read a list of words.
            while (in.hasNext()) {
                String word = in.next();

                Elem e = new Elem();     // Create a new list element.
                e.data = word;           // Set the data field.

                //... Two cases must be handled differently
                if (front == null) {
                    //... When the list is empty, we have to set the front pointer.
                    front = e;            // Back element will be set below.
                } else {
                    //... When we already have elements, we need to link to it.
                    back.next = e;       // Link last elem to new element.
                }
                back = e;                // Update back to link to new element.
            }

            //... While loop to print list in forward order.
            System.out.println("*** Print words in order of entry");
            Elem curr = front;
            while (curr != null) {
                System.out.println(curr.data);
                curr = curr.next;
            }

            System.out.println("*** Print words in order of entry");
            for (Elem e = front; e != null; e = e.next) {
                System.out.println(e.data);
            }

            //... Printing list in backward order is an interesting exercise.
            //    But too much for here.
        }
    }

    ////////////////////////////////////////////////////////////////////////// Elem
    // Simple class to hold data are sometimes defined with public fields.
    // This practice isn't good, but was done here for simplicity.
    class Elem {
        public Elem next;    // Link to next element in the list.
        public String data;  // Reference to the data.
    }

## A simple doubly-linked list

This makes only minor changes so that elements are linked in both forward and backward directions.

      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
    // Purpose: Shows a simple doubly-linked list.  Very few changes
    //          from singly-linked, but allows backwards traversal and
    //          easier insertion and deletion.
    //          Main builds list of words, prints it forward and backward.
    // Author : Fred Swartz, 21 Feb 2006, placed in the public domain.

    package linkedlistexamples;

    import java.util.Scanner;

    public class SimpleDoublyLinkedList {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);

            Elem2 front = null;    // First element of list.
            Elem2 back  = null;    // Last element of list.

            //... Read a list of words.
            while (in.hasNext()) {
                String word = in.next();

                Elem2 e = new Elem2();     // Create a new list element.
                e.data = word;           // Set the data field.

                //... Two cases must be handled differently
                if (front == null) {
                    //... When the list is empty, we have to set the front pointer.
                    front = e;            // Back element will be set below.
                } else {
                    //... When we already have elements, we need to link to it.
                    back.next = e;       // Link last elem to new element.
                }
                e.prev = back;
                back = e;                // Update back to link to new element.
            }

            System.out.println("*** Print words in order of entry");
            for (Elem2 e = front; e != null; e = e.next) {
                System.out.println(e.data);
            }

            System.out.println("*** Print words in reverse order of entry");
            for (Elem2 e = back; e != null; e = e.prev) {
                System.out.println(e.data);
            }
        }
    }

    ////////////////////////////////////////////////////////////////////////// Elem2
    // Simple classes to hold data are sometimes defined with public fields.
    // This practice isn't good, but was done here for simplicity.
    class Elem2 {
        public Elem2 next;   // Link to next element in the list.
        public Elem2 prev;   // Link to the previous element.
        public String data;  // Reference to the data.
    }

## Same program using java.util.LinkedList class

This program does the same thing as above using java.util.LinkedList, which hides the linking infrastructure and extra class. It is a doubly-linked list so moving in both directions is possible.

      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
    // Purpose: Contrast library LinkedList with the manual solutions.
    //          The link management infrastructure is completely hidden.
    // Author : Fred Swartz, 21 Feb 2006, placed in the public domain.

    package linkedlistexamples;

    import java.util.*;

    public class LibraryLinkedList {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);

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

            //... Read and build list of words.
            while (in.hasNext()) {
                String word = in.next();
                lst.add(word);
            }

            //... Enhanced for loop to print list forward.
            //    Could also use an Iterator (forward only) or
            //    ListIterator (forward or backward).
            System.out.println("*** Print words in order of entry");
            for (String s : lst) {
                System.out.println(s);
            }

            //... Use ListIterator go to backward.  Start at end.
            System.out.println("*** Print words in reverse order of entry");
            for (ListIterator<String> lit = lst.listIterator(lst.size()); lit.hasPrevious();) {
                System.out.println(lit.previous());
            }
        }
    }