converting singly linked list to doubly linked list

Posted on 2003-11-03
Medium Priority
Last Modified: 2008-03-17
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!   =^_^=
Question by:luna621
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
  • 2
  • +1
LVL 15

Expert Comment

ID: 9676951
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.
LVL 15

Expert Comment

ID: 9678060
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.

Expert Comment

ID: 9678327
Download the source for the JDK and look at java.util.LinkedList. It is a fine example of a double-linked list implementation.
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.


Author Comment

ID: 9684099
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!


Author Comment

ID: 9684122
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!!  ^_^ '
LVL 15

Accepted Solution

jimmack earned 1000 total points
ID: 9685088
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.
LVL 15

Assisted Solution

dualsoul earned 1000 total points
ID: 9685211
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.


Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

INTRODUCTION Working with files is a moderately common task in Java.  For most projects hard coding the file names, using parameters in configuration files, or using command-line arguments is sufficient.   However, when your application has vi…
Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
This video teaches viewers about errors in exception handling.
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
Suggested Courses
Course of the Month13 days, 9 hours left to enroll

801 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question