The goals and methods for creating user-defined Linked Lists
are similiar to those described in
the Array Lists document.
We will create a LListAdapter class from which we
can derive our implementation classes.
We are interested in linked lists created both from singly-linked
(forward-going) node structures as well as doubly-linked
node structures. Towards this end two implementations
SingleLList and DoubleLList are created.
Description
Comparison of LinkedList/ArrayList
The linking structure of linked lists creates different
behavior from array lists, here are the key difference:
ArrayList
LinkedList
get/set random access
accessing an element (get/set) at an index is O(1)
accessing an element (get/set) at an index is O(n) because we must proceed through
a sequence of node pointers to get to the correct position.
add/remove at first and last positions
add at the last position is
O(1) in general; an additional
O(n) cost is incurred
when the array's capacity is increase;
if the capacity is maintained efficiently, the overall average cost is
still O(1)
remove at the last position is always
O(1)
add/remove at the first position is always
O(n)
because the entire array is shifted
add/remove at the first or last positions is
O(1)
(with doubly-linked lists)
add/remove at arbitrary position
add/remove at arbitrary position is
O(n) due to shifting
add/remove at arbitrary position is O(n)
due to sequencing through pointers
space usage
wasted space varies according to the number of
unused array positions; in order to keep
average add time efficient,
O(n) wasted space
must be created at capacity increases
the links are "wasted" by virtue of not holding data; thus
there is always
O(n)
wasted space
In general terms, an ArrayList
is a better choice when we're interested in
"random positional" access of elements whereas a
LinkedList is better suited for end-based access.
Member functions
The LinkedList implements the
Queue and Deque interfaces in addition
to the List interface. All
of these interface/implementation declarations are useful
in practical situations:
Deque<E> L = new LinkedList<E>();
Queue<E> L = new LinkedList<E>();
List<E> L = new LinkedList<E>();
The Queue and Deque interfaces
offer a bewildering array of choices of member functions described
in the
Java Data Structures (java.util)
document.
Here is a table of operation
descriptions focusing on the non-index operations.
Keep in mind that
first and last signify the leftmost and rightmost elements,
respectively.
E removeFirst(),
E remove(),
E pop(),
E poll(),
E pollFirst()
get last element
getLast(),
peekLast()
get first element
getFirst(),
element(),
peek(),
peekFirst()
The main difference between the "remove_" and "get_" operations
versus the "poll_" and "peek_" operations is that for the former ones,
an exception is thrown if the list is empty, whereas for the latter,
a null is returned.
Of course, we can also use the more obvious declaration:
LinkedList<E> L = new LinkedList<E>();
which would give us access to all the relevant operations, but in
practice one tends to focus on one
the Queue, Deque, or List interface operations
exclusively.
Demo Program
Create a NetBeans project LListDemo (with Main class).
Make the following the content of Main.java.
Try running both main1 and main2 which illustrate different
features of Linked Lists.
package llistdemo;
import java.util.*;
public class Main {
public static void main(String[] args) {
main1(args);
//main2(args);
}
public static void main1(String[] args) {
Deque<String> L = new LinkedList<String>();
for (String str : new String[]{"aaa", "bbb", "ccc", "ddd", "eee"}) {
System.out.println(L.add(str));
}
System.out.println(L);
System.out.println(L.size());
System.out.println(L.getFirst());
System.out.println(L.getLast());
System.out.println(L.removeFirst());
System.out.println(L);
L.addFirst("XXX");
L.addLast("YYY");
System.out.println(L);
}
public static void main2(String[] args) {
Deque<String> L = new LinkedList<String>();
for (String str : new String[]{"aaa", "bbb", "ccc", "ddd", "eee"}) {
L.add(str);
}
System.out.println(L);
System.out.println(L.size());
System.out.println(L.removeLast());
System.out.println(L);
System.out.println(L.size());
// The next operation goes "outside" the Deque interface.
// We can accomodate it by casting to the List interface.
((List<String>)L).add(3, "QQQ");
System.out.println(L);
// The following would be misinterpreted as
// L.remove(new Integer(2)) if L is a Deque as above
// L.remove(2);
// We can, however, cast L to the List interface to obtain
// the intended interpretation of "2" as the list position
((List<String>)L).remove(2);
System.out.println(L);
Iterator<String> desc = L.descendingIterator();
while (desc.hasNext()) {
System.out.println(desc.next());
}
}
}
LListAdapter
Our LListAdapter demonstrates all the functions
satisfied by LinkedList. The functions are all "unimplemented"
in the sense that their only code is to throw an
UnsupportedOperationException.
All of our user-defined versions will be extensions of LListAdapter.
As described in the
User defined Array Lists
document, the Serializable implementation is avoided.
In order to create this in NetBeans, create a new Java Class:
Class Name: LListAdapter
package: llist
Then insert the following content
( click to show )
Version 1: singly-linked list
Our first attempt at an implementation uses a singly-linked list.
Create a Java Class:
Class Name: SingleLList
package: llist
Then insert the following content
( click to show )
Testing
The main1 function (not main2)
can execute for
SingleLList in place of LinkedList.
Add the import statement to Main:
import llist.*;
Replace the definition of L in main1
and reset main to call main1
public static void main1(String[] args) {
//Deque<String> L = new LinkedList<String>();
Deque<String> L = new SingleLList<String>();
...
Description
SingleLList uses the inner class:
private class Node {
public E data;
public Node next;
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
}
The data members of SingleLList are:
private Node first = null;
private Node last = null;
private int size = 0;
The add functions
If we only had a first element to deal with, these would be
all we needed for the add functions:
a) first = new Node(elt, first); // add to first
b) last.next = new Node(elt, null); // add to last
last = last.next;
The one situation which does not fit is dealing with the empty list.
In (a) last is not correctly set;
in (b) the situation is even worse.
Therefore, to do adding requires a special private member function
to deal exactly the empty list situation:
private void handleFirstElement(E elt) {
first = new Node(elt, null);
last = first;
}
With this in place, our public
addFirst and addLast functions both use this style:
if (first == null) {
handleFirstElement(elt)
} else {
// do the "usual thing"
}
Singly-linked limitations
SingleLList purposefully avoids many operations.
The foremost of these
is removeLast, which the singly-linked list structure
is not equipped to
handle efficiently.
Removing the first element is easy because
there is nothing before it. At all other positions it is different, because
you would need to access the previous element in order to be able to
link it to the next element, thereby bypassing the deleted node.
Version 2: Doubly-linked list
Create a Java Class:
Class Name: DoubleLList
package: llist
Then insert the following content
( click to show )
Testing
Replace DoubleLList in place of LinkedList
in both main1 and main2 by
by replacing the definition of L:
//Deque<String> L = new LinkedList<String>();
Deque<String> L = new DoubleLList<String>();
...
Description
The doubly-linked used uses an inner class:
private class Node {
public E data;
public Node prev, next;
public Node(E data, Node prev, Node next) {
this.data = data;
this.prev = prev;
this.next = next;
}
}
Although it may seem like an overly complex approach, making the list
nodes doubly-linked with both next and prev
pointers,
gives us the ability to efficiently remove nodes which are being
pointed to. Additionally,
creating a doubly linked list makes the list effectively symmetrical
and thereby makes sense out of the
following required operations which would be tricky with singly-linked lists:
descendingIterator
removeLastOccurrence
Unfortunately, the double-linking makes it tricky to avoid coding errors.
The hard work in the following class is achieved by these private helper functions:
void handleFirstElement(E e)
void removeNode(Node n)
addElementBefore(Node n, E e)
Node nodeAtPosition(int index)