Question

Objective: Manipulate the Linked List Pointer.

1. Write a java subclass to extend LList.java. Provide a reverse list method in the subclass to reverse the order of the linked list.
2. Print the original linked list and the reverse ordered linked list at the end of program.
3. You can use the gamescore.txt to test the reverse method.

_____________________________________________________________________________________________________________________________________________________

/** Source code example for "A Practical Introduction to Data

    Structures and Algorithm Analysis, 3rd Edition (Java)"

    by Clifford A. Shaffer

    Copyright 2008-2011 by Clifford A. Shaffer

*/

/** List ADT */

public interface List {

  /** Remove all contents from the list, so it is once again

      empty. Client is responsible for reclaiming storage

      used by the list elements. */

  public void clear();

  /** Insert an element at the current location. The client

      must ensure that the list's capacity is not exceeded.   

      @param item The element to be inserted. */

  public void insert(E item);

  /** Append an element at the end of the list. The client

      must ensure that the list's capacity is not exceeded.   

      @param item The element to be appended. */

  public void append(E item);

  /** Remove and return the current element.

      @return The element that was removed. */

  public E remove();

  /** Set the current position to the start of the list */

  public void moveToStart();

  /** Set the current position to the end of the list */

  public void moveToEnd();

  /** Move the current position one step left. No change

      if already at beginning. */

  public void prev();

  /** Move the current position one step right. No change

      if already at end. */

  public void next();

  /** @return The number of elements in the list. */

  public int length();

  /** @return The position of the current element. */

  public int currPos();

  /** Set current position.

      @param pos The position to make current. */

  public void moveToPos(int pos);

  /** @return The current element. */

  public E getValue();

}

/** Source code example for "A Practical Introduction to Data

    Structures and Algorithm Analysis, 3rd Edition (Java)"

    by Clifford A. Shaffer

    Copyright 2008-2011 by Clifford A. Shaffer

*/

// Doubly linked list implementation

class LList implements List {

protected DLink head;        // Pointer to list header

protected DLink tail;        // Pointer to last element in list

protected DLink curr;      // Pointer ahead of current element

int cnt;          // Size of list

//Constructors

LList(int size) { this(); }  // Ignore size

LList() {

  curr = head = new DLink(null, null); // Create header node

  tail = new DLink(head, null);

  head.setNext(tail);

  cnt = 0;

}

public void clear() {         // Remove all elements from list

  head.setNext(null);         // Drop access to rest of links

  curr = head = new DLink(null, null); // Create header node

  tail = new DLink(head, null);

  head.setNext(tail);

  cnt = 0;

}

public void moveToStart()  // Set curr at list start

{ curr = head; }

public void moveToEnd()  // Set curr at list end

{ curr = tail.prev(); }

/** Insert "it" at current position */

public void insert(E it) {

  curr.setNext(new DLink(it, curr, curr.next()));  

  curr.next().next().setPrev(curr.next());

  cnt++;

}

/** Append "it" to list */

public void append(E it) {

  tail.setPrev(new DLink(it, tail.prev(), tail));

  tail.prev().prev().setNext(tail.prev());

  cnt++;

}

/** Remove and return current element */

public E remove() {

  if (curr.next() == tail) return null; // Nothing to remove

  E it = curr.next().element();      // Remember value

  curr.next().next().setPrev(curr);

  curr.setNext(curr.next().next());  // Remove from list

  cnt--;           // Decrement the count

  return it;                         // Return value removed

}

/** Move curr one step left; no change if at front */

public void prev() {

  if (curr != head)   // Can't back up from list head

    curr = curr.prev();

}

// Move curr one step right; no change if at end

public void next()

  { if (curr != tail.prev()) curr = curr.next(); }

public int length() { return cnt; }

// Return the position of the current element

public int currPos() {

  DLink temp = head;

  int i;

  for (i=0; curr != temp; i++)

    temp = temp.next();

  return i;

}

// Move down list to "pos" position

public void moveToPos(int pos) {

  assert (pos>=0) && (pos<=cnt) : "Position out of range";

  curr = head;

  for(int i=0; i

}

public E getValue() {   // Return current element

  if (curr.next() == tail) return null;

  return curr.next().element();

}

// Extra stuff not printed in the book.

  /**

   * Generate a human-readable representation of this list's contents

   * that looks something like this: < 1 2 3 | 4 5 6 >.  The vertical

   * bar represents the current location of the fence.  This method

   * uses toString() on the individual elements.

   * @return The string representation of this list

   */

  public String toString()

  {

    // Save the current position of the list

    int oldPos = currPos();

    int length = length();

    StringBuffer out = new StringBuffer((length() + 1) * 4);

    moveToStart();

    out.append("< ");

    for (int i = 0; i < oldPos; i++) {

      out.append(getValue());

      out.append(" ");

      next();

    }

    out.append("| ");

    for (int i = oldPos; i < length; i++) {

      out.append(getValue());

      out.append(" ");

      next();

    }

    out.append(">");

    moveToPos(oldPos); // Reset the fence to its original position

    return out.toString();

  }

}

/** Source code example for "A Practical Introduction to Data

    Structures and Algorithm Analysis, 3rd Edition (Java)"

    by Clifford A. Shaffer

    Copyright 2008-2011 by Clifford A. Shaffer

*/

/** Doubly linked list node */

class DLink {

  private E element;         // Value for this node

  private DLink next;     // Pointer to next node in list

  private DLink prev;     // Pointer to previous node

  /** Constructors */

  DLink(E it, DLink p, DLink n)

  { element = it;  prev = p; next = n; }

  DLink(DLink p, DLink n) { prev = p; next = n; }

  /** Get and set methods for the data members */

  DLink next() { return next; }

  DLink setNext(DLink nextval)

    { return next = nextval; }

  DLink prev() { return prev; }

  DLink setPrev(DLink prevval)

    { return prev = prevval; }

  E element() { return element; }

  E setElement(E it) { return element = it; }

}

public class GameEntry {

protected String name;

protected int score;

public GameEntry(String n, int s) {

   name = n;

   score = s;

}

public String getName() {return name;}

public int getScore() {return score;}

public String toString() {

return "("+name+","+score+")";

}

}

//gamescore.txt

Mike,1105
Rob,750
Paul,720
Anna,660
Rose,590
Jack,510

Answer 1

        public void reverse() {
                if(cnt == 0) {
                        return;
                }
                DLink prev = null;
                DLink start = head;
                while(start != null) {
                        DLink next = start.next;
                        start.next = prev;
                        start.prev = next;
                        prev = start;
                        start = next;
                }
                tail = head;
                head = prev; 
        }
        

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.