Linked List

The LinkedList class provides a list implementation that is based on linked nodes. Because links must be traversed, access to the list's elements is slow. However, because only node references need to be changed, insertions and deletions of elements are fast.

WHAT IS A NODE?

A node is a fixed sequence of value and link memory locations. Unlike an array, where each slot stores a single value of the same primitive type or reference supertype, a node can store multiple values of different types. It can also store links (references to other nodes).

Consider the following simple Node class:

class Node {

// value field String name; // link field Node next;

Node describes simple nodes where each node consists of a single name value field and a single next link field. Notice that next is of the same type as the class in which it is declared. This arrangement lets a node instance store a reference to another node instance (which is the next node) in this field. The resulting nodes are linked together.

The following code fragment creates a couple of Node objects and links the second Node object to the first Node object. This fragment also demonstrates how to traverse this linked list by following each Node object's next field. Node traversal stops when the traversal code discovers that next contains the null reference, which signifies the end of the list.

Node first = new Node(); first.name = "First node"; Node last = new Node(); last.name = "Last node"; last.next = null; first.next = last; Node temp = first;

System.out.println(temp.name); temp = temp.next;

The code first builds a linked list of two Nodes, and then assigns first to local variable temp in order to traverse the list without losing the reference to the first node that is stored in first. While temp is not null, the loop outputs the name field. It also navigates to the next Node object in the list via the temp = temp.next; statement.

If you convert this code into an application and run the application, you will discover the following output:

First node Last node

LinkedList supplies two constructors:

■ LinkedList() creates an empty linked list.

■ LinkedList(Collection<? extends E> collection) creates a linked list containing collection's elements in the order in which they are returned by the collection's iterator.

Listing 8-6 demonstrates a linked list.

Listing 8-6. A demonstration of a list of linked nodes import java.util.LinkedList; import java.util.List; import java.util.ListIterator;

public class LinkedListDemo {

public static void main(String[] args) {

List<String> ls = new LinkedList<String>();

String[] weekDays = {"Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"}; for (String weekDay: weekDays)

ls.add(weekDay); dump("ls:", ls); ls.add(1, "Sunday"); ls.add(3, "Monday"); ls.add(5, "Tuesday"); ls.add(7, "Wednesday"); ls.add(9, "Thursday"); ls.add(11, "Friday"); ls.add(13, "Saturday"); dump("ls:", ls);

ListIterator<String> li = ls.listIterator(ls.size()); while (li.hasPrevious())

System.out.print(li.previous() + " "); System.out.println();

static void dump(String title, List<String> ls) {

System.out.print(title + " "); for (String s: ls)

System.out.print(s + " "); System.out.println();

This application demonstrates that each successive add() method call must increase its index by 2 to account for the previously added element when adding longer weekday names to the list. It also shows you how to output a list in reverse order: return a list iterator with its cursor initialized past the end of the list and repeatedly call previous().

When you run this application, it generates the following output:

ls: Sun Mon Tue Wed Thu Fri Sat ls: Sun Sunday Mon Monday Tue Tuesday Wed Wednesday Thu Thursday Fri Friday Sat Saturday Saturday Sat Friday Fri Thursday Thu Wednesday Wed Tuesday Tue Monday Mon Sunday Sun

A set is a collection that contains no duplicate elements. In other words, a set contains no pair of elements el and e2 such that el.equals(e2) returns true. Furthermore, a set can contain at most one null element. Sets are described by the Set interface, whose generic type is Set<E>.

Set extends Collection and redeclares its inherited methods, for convenience and also to add stipulations to the contracts for add(), equals(), and hashCode(), to address how they behave in a set context. Also, Set's documentation states that all constructors of implementation classes must create sets that contain no duplicate elements.

Set does not introduce new methods.

Was this article helpful?

0 0

Post a comment