Linked Lists

Java Notes: Simple Linked Lists

http://leepoint.net/notes-java/data/collections/lists/simple-linked-list.html

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 lst = new LinkedList(); //... 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 lit = lst.listIterator(lst.size()); lit.hasPrevious();) { System.out.println(lit.previous()); } } }

Copyleft 2006 Fred Swartz MIT License