converting singly linked list to doubly linked list

Dear Java Gurus,

How would I convert a singly linked list to a doubly linked list?  Here is my referenced-based linked list code:


public class ListReferenceBased implements ListInterface {
  // reference to linked list of items
  private Node head;
  private int numItems; // number of items in list

  public ListReferenceBased() {
    numItems = 0;
    head = null;
  }  // end default constructor

  public boolean isEmpty() {
    return numItems == 0;
  }  // end isEmpty

  public int size() {
    return numItems;
  }  // end size

  private Node find(int index) {
  // --------------------------------------------------
  // Locates a specified node in a linked list.
  // Precondition: index is the number of the desired
  // node. Assumes that 1 <= index <= numItems+1
  // Postcondition: Returns a reference to the desired
  // node.
  // --------------------------------------------------
    Node curr = head;
    for (int skip = 1; skip < index; skip++) {
      curr = curr.getNext();
    } // end for
    return curr;
  } // end find

  public Object get(int index)
                throws ListIndexOutOfBoundsException {
    if (index >= 1 && index <= numItems) {
      // get reference to node, then data in node
      Node curr = find(index);
      Object dataItem = curr.getItem();
      return dataItem;
    else {
      throw new ListIndexOutOfBoundsException(
                     "List index out of bounds exception on get");
    } // end if
  } // end get

  public void add(int index, Object item)
                  throws ListIndexOutOfBoundsException {
    if (index >= 1 && index <= numItems+1) {
      if (index == 1) {
        // insert the new node containing item at
        // beginning of list
        Node newNode = new Node(item, head);
        head = newNode;
      else {
        Node prev = find(index-1);
        // insert the new node containing item after
        // the node that prev references
        Node newNode = new Node(item, prev.getNext());
      } // end if
    else {
      throw new ListIndexOutOfBoundsException(
                    "List index out of bounds exception on add");
    } // end if
  }  // end add

  public void remove(int index)
                   throws ListIndexOutOfBoundsException {
    if (index >= 1 && index <= numItems) {
      if (index == 1) {
        // delete the first node from the list
        head = head.getNext();
      else {
        Node prev = find(index-1);
        // delete the node after the node that prev
        // references, save reference to node
        Node curr = prev.getNext();
      } // end if
    } // end if
    else {
      throw new ListIndexOutOfBoundsException(
                   "List index out of bounds exception on remove");
    } // end if
  }   // end remove

  public void removeAll() {
    // setting head to null causes list to be
    // unreachable and thus marked for garbage
    // collection
    head = null;
    numItems = 0;
  } // end removeAll
} // end ListReferenceBased


Thank you!   =^_^=
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

hm...i don't see your Node implementation...just make it double linked:
  store in it  previous and next reference to nodes, attached to it.
so you will have 2 methods:

or do you use some standart implementation? i don't see it in API.
Add a previous attribute to your Node (as dualsoul suggests).

Update the Node constructor to take the previous link as another parameter.

Update the add() and remove() methods to handle the concept of the previous link (these are the only two methods you need to update).

Remember that when you are adding or deleting Nodes, you need to modify the "next" for the Node that comes before the addition/deletion and the "previous" for the Node that comes after the addition/deletion.
Download the source for the JDK and look at java.util.LinkedList. It is a fine example of a double-linked list implementation.
Cloud Class® Course: Microsoft Office 2010

This course will introduce you to the interfaces and features of Microsoft Office 2010 Word, Excel, PowerPoint, Outlook, and Access. You will learn about the features that are shared between all products in the Office suite, as well as the new features that are product specific.

luna621Author Commented:
Oh!  Sorry!  I forgot my Node class!

Here it is:

public class Node {
  private Object item;
  private Node next;

  public Node(Object newItem) {
    item = newItem;
    next = null;
  } // end constructor

  public Node(Object newItem, Node nextNode) {
    item = newItem;
    next = nextNode;
  } // end constructor

  public void setItem(Object newItem) {
    item = newItem;
  } // end setItem

  public Object getItem() {
    return item;
  } // end getItem

  public void setNext(Node nextNode) {
    next = nextNode;
  } // end setNext

  public Node getNext() {
    return next;
  } // end getNext

} // end class Node


What do I set my next to?  Do I need to change anything in my ListReferenceBased class?  Thanks!

luna621Author Commented:
I also have another question... so I increased the points :)

I can't seem to get this stack implementation to work.  In my main method, I would like the user to be able to state their own delimiter.  They will type in the opening, and a closing delimiter.  I read it in as a String, but is there a way to convert it to a char?  And if there is, how would I use it in the switch statement?

Here's part of my code:
// some more code up here in main method...
// .
// .
// .

System.out.println("Did you want to add a different type of delimiter such as < or >? (y/n)");
      String answer = br.readLine();
      answer = answer.trim();

          if (answer.equals("y")) {
                System.out.print("Please enter your choice of opening delimiter: ");
                String yourOpening = br.readLine();

                System.out.print("Please enter your choice of closing delimiter: ");
            String yourClosing = br.readLine();
      } // end if
      else {

  } // end main method


  // private helper method
  // checks whether its string argument s has balanced parentheses

  private static boolean checkParens(String s) {
     int n = s.length();
     char c1, c2;
     StackListBased myStack = new StackListBased();

     for (int i=0; i<n; i++) {
         switch (c1= s.charAt(i)) {
                 case '(':
                 case '[':
                 case '{':  // how do I make yourOpening into a char?
                 case 'yourOpening':      myStack.push(new Character(c1));
                 case ')':
                 case ']':
                 case '}':  // how do I make youClosing into a char?
                 case 'yourClosing':      if (myStack.isEmpty())  // parentheses not matched
                                            return false;
                                         c2=((Character) myStack.pop()).charValue();

                             if (!matched( c1, c2 )) return false;
                                   if ((c1 == ')') && (c2 != '(')) return false;
                                   else if ((c1 == ']') && (c2 != '[')) return false;
                                   else if ((c1 == '}') && (c2 != '{')) return false;
                 default:    return false;   // not one of the listed parentheses
               } // end switch
 } // end for

     if (!myStack.isEmpty()) return false;   // unmatched parentheses
           return true;
  } // end checkParens()


Sorry for so many questions!!  ^_^ '
See the previous comments regarding the linked list.

You already seem to be converting to characters successfully, using s.charAt(i);

However, if I understand what you seem to be trying to do in the code, you don't need a switch in this way.

You could step through the string 1 character at a time (as you currently do), set a boolean flag (eg. insideDelim = true) when you find the starting delimiter, "stack" each subsequent character until you reach the closing delimiter.

Alternatively, you could simply grab the substring between delimiters using String.indexOf(char) to get the location of the open delimiter and indexOf(char, int) for the closing delimiter.  This will help to ensure that the String contains the delimiters you want, in the right order.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
1) about Node:
   - add reference to previous Node:
public class Node {
  private Object item;
  private Node next;
  private Node prev;
  Node getPrevious();
   - update methods in your ListReferenceBased class to change value of previous node.

2) concerning delimters, as jimjack said:
"You could step through the string 1 character at a time (as you currently do), set a boolean flag (eg. insideDelim = true) when you find the starting delimiter, "stack" each subsequent character until you reach the closing delimiter."
   that's will be good.
   But you can try to use StringTokenizer class from SDK, may it'll be more clear, and you safe your time, not to code the same, if it suite you.

It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.