converting singly linked list to doubly linked list

Posted on 2003-11-03
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.
Online Training Solution

Drastically shorten your training time with WalkMe's advanced online training solution that Guides your trainees to action. Forget about retraining and skyrocket knowledge retention rates.


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 250 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 250 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

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Java had always been an easily readable and understandable language.  Some relatively recent changes in the language seem to be changing this pretty fast, and anyone that had not seen any Java code for the last 5 years will possibly have issues unde…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
The viewer will learn how to implement Singleton Design Pattern in Java.

724 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