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
  • 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.
Networking for the Cloud Era

Join Microsoft and Riverbed for a discussion and demonstration of enhancements to SteelConnect:
-One-click orchestration and cloud connectivity in Azure environments
-Tight integration of SD-WAN and WAN optimization capabilities
-Scalability and resiliency equal to a data center


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: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

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

Suggested Solutions

Title # Comments Views Activity
login jsp example 24 65
java example issue 3 23
swing controls 2 16
collection output issue 9 36
For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.
This video teaches viewers about errors in exception handling.

839 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