From: Introduction to Java Programming 9th edition The MyLinkedList class used i

Question

From: Introduction to Java Programming 9th edition

The MyLinkedList class used in Listing 26.6 is a one-way directional linked list that enables one-way traversal of the list. Modify the Node class to add the new field name previous to refer to the previous node in the list, as follows:

public class Node<E> {

E element;

Node<E> next;

Node<E> previous;

public Node(E e) {

element = e;

}

Implement a new class named MyTwoWayLinkedList that uses a doubly linked list to store elements. The MyLinkedList class in the text extends MyAbstractList. Define MyTwoWayLinkedList to extend the java.util.AbstractSequentialList class. You need to implement the methods listIterator() and listIterator(int index). Both return an instance of java.util.ListIterator<E>. The former sets the cursor to the head of the list and the latter to the element at the specified index.

Explanation / Answer

import java.util.*; public class DoubleLink { public static void main (String [] args) { LList list; Iterator sequence; list = new LList(); System.out.println("The list contains " + list.size1() + " items."); list.append(new Double (3.1415)); list.append(new Double (6.2830)); System.out.print("The list contains " + list.size2() + " items: "); /* Use the list's iterator to help print the list content */ sequence = list.anIterator(); while (sequence.hasNext()) { Double object = sequence.next(); System.out.print(object + " "); } System.out.println(); } } class LList { private Node head, // references the first node in the list tail; // references the last node in the list public LList() { head = null; // initially, the list is empty tail = null; } /* size1() -- To figure the # of items in the list, this method * uses the traditional 'travelling pointer' method to visit * each list node in turn. This is the way to do the job if * an iterator is not available. */ public int size1 () { int count = 0; Node ptr = head; while (ptr != null) { count++; ptr = ptr.getNext(); } return count; } /* size2() -- Does the same job as does size1(), but uses an * iterator. The big difference is that we don't need to * reference a Node object directly; the iterator encapsulates * those details, making knowledge of the list representation * unnecessary. */ public int size2 () { int count = 0; T tmp = null; Iterator sequence = anIterator(); while (sequence.hasNext()) { count++; tmp = sequence.next(); } return count; } /* append(T) -- attaches the given object (well, attaches * a Node object containing a copy of the given object reference) * to the end of the list. Note that append may be appending to * the end of a list, or may be placing the first node in the * list. */ public void append (T object) { Node newNode = new Node (object); newNode.setNext(null); newNode.setPrevious(tail); if (head == null) { // this new node will be the only node head = tail = newNode; } else { // just need to attach to old last node tail.setNext(newNode); tail = newNode; } } /* anIterator() -- creates and returns an Iterator for the list */ public Iterator anIterator() { return new LLIterator(); } /* The class LLIterator. This is an inner (nested) class, meaning * that it is declared within the declaration of another class. * The idea is that this iterator is specific to this particular * list class, and as such does not need to be visible to * any other class. LList supplies a method that creates * an iterator for whomever wants one, and the supplied iterator * has all necessary interface commands; nothing else is needed. */ private class LLIterator implements Iterator { Node position; // to keep track of the current position public LLIterator() { position = null; // initially, start 'before' the list } /* next() -- advance to the next object in the list and * return a reference to it. */ public T next() { if (!hasNext()) // if we try to run off the end of the list throw new NoSuchElementException(); if (position == null) { // if this is 1st time next() is called position = head; } else { position = position.getNext(); } return position.getData(); } /* hasNext() -- test to see if the list contains any more * items over which we might iterate (or, test to see if * next() would succeed if called). */ public boolean hasNext() { if (position == null) { // if we have not yet begun to iterate if (head != null) { // if the list isn't empty return true; } else { return false; } } else { if (position.getNext() != null) { return true; } else { return false; } } } /* remove() -- Story time: Java's Iterator interface must * be implemented with three methods: next(), hasNext(), * and remove(). remove() is optional, but the compiler * will complain if you don't define it. So, in this * context 'optional' means that you have to include it * as a method, but it doesn't have to do anything. Of * course, it would be nice to let the poor programmer * know that remove() isn't actually working, and so the * exception is thrown. */ public void remove() { throw new UnsupportedOperationException(); } } } /* The Node class. Not much to say: A LList is a group of * dynamically allocated nodes, each containing the data to be * stored (in this case, a Generic reference) and information * necessary to relate nodes to each other (references to preceding * and succeeding nodes). Nodes don't do anything other than * permit the outside world to look at their values and change * their values. Yes, we could have made the instance variables * public and done away with the getters and setters, but that's * bad form. */ class Node { private Node prev; private T data; private Node next; public Node () { prev = next = null; data = null; } public Node (T object) { data = object; prev = next = null; } /* The getters */ public Node getPrevious () { return prev; } public T getData () { return data; } public Node getNext () { return next; } /* The setters */ public void setPrevious (Node node) { prev = node; } public void setData (T object) { data = object; } public void setNext (Node node) { next = node; } }

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.