Java Notes: Simple Linked Lists
Why learn to implement linked lists
Teaches basic skills. Every programmer is expected to understand how to build a linked list "by hand" (without using the library classes). This skill is especially important for C/C++ programmers who need to be very good at manipulating pointers and dynamic memory allocation/deallocation, and there's no better programming exercise than linked lists to get those skills. References and memory management in Java are vastly easier than C/C++, but the ability to use references fluently is necessary, and implementing linked lists is a very good exercise.
Linking in general. Even though you might use linked lists infrequently in your programs, you will definitely be linking objects together in various ways, and writing linked list code is a good way to become comfortable with this time of composition.
Advanced features of Java are necessary to write the equivalent of the Java LinkedList class, and there is a lot to be learned from that exercise (generics, iterators, inner classes, interfaces, ...). These notes don't show an implementation of a proper LinkedList class.
Why writing linked lists is a waste of time
Other than benefits of becoming comfortable with references and memory allocation, and perhaps the advanced features if you write a complete LinkedList equivalent, there are lots of reasons NOT to do this.
Linked lists are rarely useful! The surprising thing is that linked lists are rarely the right data structure to use. The theory is that insertions and deletions in the middle of a list are faster with a linked list are faster than an array based solution (eg, java.util.ArrayList or java.util.ArrayDeque). Benchmarks don't support that for most cases, probably because of the advantage of locality of reference in cache memory.
Use the libary classes. You will almost always be better off using the Java libary (or other public library) classes than writing your own in terms of time, defects, performance, ....
This shows three programs.
Despite reasons you might not want to implement linked lists by hand, here are two programs that illustrate how to write singly and double linked lists, and one program that shoulse how to use the library class.
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());
}
}
}
|