Solved

converting singly linked list to doubly linked list

Posted on 2003-11-03
7
693 Views
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());
        prev.setNext(newNode);
      } // end if
      numItems++;
    }
    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();
        prev.setNext(curr.getNext());
      } // end if
      numItems--;
    } // 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!   =^_^=
0
Comment
Question by:luna621
  • 2
  • 2
  • 2
  • +1
7 Comments
 
LVL 15

Expert Comment

by:dualsoul
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:
  Node.getNext()
  Node.getPrevious()

or do you use some standart implementation? i don't see it in API.
0
 
LVL 15

Expert Comment

by:jimmack
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.
0
 

Expert Comment

by:dmcreyno
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.
0
Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

 

Author Comment

by:luna621
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!

=^_^=
0
 

Author Comment

by:luna621
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 {
      System.exit(0);
      }

  } // 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));
                                         break;
                 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;
                                   break;
                 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!!  ^_^ '
0
 
LVL 15

Accepted Solution

by:
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.
0
 
LVL 15

Assisted Solution

by:dualsoul
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.


0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

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…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…

744 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now