java program In this laboratory, you will create a (doubly) linked list implemen

Question

java program

In this laboratory, you will create a (doubly) linked list implementation of the interface OrderedStructure, which declares the following methods

. int size();

boolean add( Comparable obj );

Object get( int pos );

void remove( int pos ).

Implementations of this interface should be such that the elements are kept in increasing order. The order of the elements is defined by the implementation of the method compareTo( Object obj ) declared by the interface Comparable. The classes Integer and String both implement the interface Comparable, you can use these for the tests. Objects of any other classes that implement the interface Comparable can be stored in an OrderedList.

Implement the method size(), i.e. replace the throw statement by an iterative implementation that traverses the list and counts the number of elements. Add a test to the test class, simply to check that the method size works for the empty list. We will check the other cases when the method add has been completed.

Implement the method boolean add( Comparable obj ); adds an element in increasing order according to the class’ natural comparison method (i.e. uses the method compareTo ). Returns true if the element can be successfully added to this OrderedList, and false otherwise.

Add test cases for the method add. It will be difficult to thoroughly test the implementation, but at least the size of the list should change as new elements are added.

Implement Object get( int pos ). It returns the element at the specified position in this OrderedList; the first element has the index 0. This operation must not change the state of the OrderedList;

Add test cases for the methods add and get to the test class. You are now be in a better position for testing all three methods, add, get and size. In particular, you should be able to add elements, use a while loop to get all the elements of the list, one by one, using the method get. Make sure that all three methods are fully debugged before continuing.

Implement void remove( int pos ); Removes the element at the specified position in this OrderedList; the first element has the index 0.

Add test cases for the method remove to the test class. Make sure that the method remove (as well as all the other methods) is fully debugged before continuing.

Explanation / Answer

DoublyLL.java

import java.util.ListIterator;

import java.util.NoSuchElementException;

public class DoublyLL<box> implements Iterable<box> {

private int no;   

private Node first;

private StructNode last;

public DoublyLL() {

first = new StructNode();

last = new StructNode();

first.nxt = last;

last.earlier = first;

}

private class StructNode {

private box items;

private StructNode nxt;

private StructNode earlier;

}

public boolean isBlank()

{

return no == 0;

}

public int ssz()   

{

return no;

}

public void add(box items) {

StructNode last = last.earlier;

StructNode io = new StructNode();

io.items = items;

io.nxt = last;

io.earlier = last;

last.earlier = io;

last.nxt = io;

no++;

}

public liIterate<box> iterate() { return new DoublyLLIterate(); }

private class DoublyLLIterate implements liIterate<box> {

private StructNode curr = first.nxt;

private StructNode lstAccess = null;

private int indices = 0;

public boolean hsNxt() { return indices < no; }

public boolean hasEarlier() { return indices > 0; }

public int prevIn() { return indices - 1; }

public int nxtInd() { return indices; }

public box nxt() {

if (!hsNxt()) throw new NoSuchElementException();

lstAccess = curr;

box items = curr.items;

curr = curr.nxt;

indices++;

return items;

}

public box previous() {

if (!hasEarlier()) throw new NoSuchElementException();

curr = curr.earlier;

indices--;

lstAccess = curr;

return curr.items;

}

public void keep(box items) {

if (lstAccess == null) throw new IllegalStateException();

lstAccess.items = items;

}

  

public void rm() {

if (lstAccess == null) throw new IllegalStateException();

StructNode io = lstAccess.earlier;

StructNode ui = lstAccess.nxt;

io.nxt = ui;

ui.earlier = io;

no--;

if (curr == lstAccess)

curr = ui;

else

indices--;

lstAccess = null;

}

public void add(box items) {

StructNode io = curr.earlier;

StructNode ui = new StructNode();

StructNode qq = curr;

ui.items = items;

io.nxt = ui;

ui.nxt = qq;

qq.earlier = ui;

ui.earlier = io;

no++;

indices++;

lstAccess = null;

}

}

public String toString() {

StringBuilder sb = new StringBuilder();

for (box items : this)

sb.append(items + " ");

return sb.toString();

}

public static void main(String[] args) {

int no = Integer.parseInt(args[0]);

StdOut.println(no + " Random integers between 0 - 99");

DoublyLL<Integer> lss = new DoublyLL<Integer>();

for (int i = 0; i < no; i++)

lss.add(StdRandom.uniform(100));

StdOut.println(lss);

StdOut.println();

liIterate<Integer> iterate = lss.iterate();

StdOut.println("Add 1 to each element");

while (iterate.hsNxt()) {

int io = iterate.nxt();

iterate.keep(io + 1);

}

StdOut.println(lss);

StdOut.println();

StdOut.println("Multiply each element by 3");

while (iterate.hasEarlier()) {

int io = iterate.previous();

iterate.keep(io + io + io);

}

StdOut.println(lss);

StdOut.println();

StdOut.println("Remove elements which are multiple of 4");

while (iterate.hsNxt()) {

int io = iterate.nxt();

if (io % 4 == 0) iterate.rm();

}

StdOut.println(lss);

StdOut.println();

StdOut.println("Remove elements that are even");

while (iterate.hasEarlier()) {

int io = iterate.previous();

if (io % 2 == 0) iterate.rm();

}

StdOut.println(lss);

StdOut.println();

StdOut.println("Add elements");

while (iterate.hsNxt()) {

int io = iterate.nxt();

iterate.add(io + 1);

}

StdOut.println(lss);

StdOut.println();

  

StdOut.println("Add elements");

while (iterate.hasEarlier()) {

int io = iterate.previous();

iterate.add(io * 10);

iterate.previous();

}

StdOut.println(lss);

StdOut.println();

}

}

Please rate the answer if it helped....Thankyou

Hope it helps.....

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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