12 Replies - 6869 Views - Last Post: 30 June 2010 - 02:32 PM Rate Topic: -----

#1 Guest_sam jenks*


Reputation:

Doubly Linked List

Posted 29 June 2010 - 02:19 PM

Hi all,
For a homework assignment I am trying to create a doubly linked list ADT and for the most part I completed it, but there are two functions that don't seem to work. One is insertBeforeCurrent() (insert a new node before the current marker) and movePrev() (move current marker one step towards the first element in the list). The latter is most frustrating because it seems so simple, yet I can't get it to work. I have insertAfterCurrent() and moveNext() (the opposite of the functions mentioned above) working completely fine. Below is the code needed to get the functions to work. Hopefully you can help. Thanks

class List{

   private class Node{
      // Fields //
      int data;
      Node next;
      Node prev;
      // Constructor //
      Node(int data) { 
        this.data = data;
        next = null;
        prev = null;
      }
      // toString:  Overides Object's toString method.//
      public String toString() { 
        return String.valueOf(data); 
      }
   }

   // Fields //
   private Node front;
   private Node back;
   private Node current;
   private int length;

   // Constructor //
   List() { 
     front = back = null; 
     length = 0; 
   }

   void movePrev() {
     if (this.isEmpty() ) {
       throw new RuntimeException("List Error: movePrev() called on empty List");
     }
        current = current.prev;
   }
   void insertBeforeCurrent(int data){
     Node node = new Node(data);
     if( this.isEmpty() ) {
       throw new RuntimeException("List Error: insertBeforeCurrent() has no current marker on an empty list");
     }
     if ( this.offEnd() ) {
       throw new NullPointerException("List Error: insertBeforeCurrent() called with no element in current");
     }
     if ( current == front) {
       node.prev = null;
       front = node;
     }
     else {
       node.prev = current.prev;
       current.prev.next = node.prev;
     }
     node.next = current;
     current.prev = node;
     length++;
   }



NOTE: offEnd() and isEmpty() are both functions that are also included in my program, but not included in this post. offEnd() returns true if the current marker is undefined.

Edited by macosxnerd101: Welcome to DIC! :) Please remember to post your code using code tags, like so: :code:.

This post has been edited by macosxnerd101: 29 June 2010 - 02:25 PM


Is This A Good Question/Topic? 0

Replies To: Doubly Linked List

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,257
  • Joined: 27-December 08

Re: Doubly Linked List

Posted 29 June 2010 - 02:30 PM

I think current.prev.next should reference node, not node.prev which is still the same as current.prev.
     else {
       node.prev = current.prev;
       current.prev.next = node.prev;
     }
     node.next = current;
     current.prev = node;
     length++;
   }



As for moveNext(), it should be as easy as current = current.next;, with some basic validation.

You may also find my Linked List Tutorial helpful.
Was This Post Helpful? 0
  • +
  • -

#3 Guest_sam jenkins*


Reputation:

Re: Doubly Linked List

Posted 29 June 2010 - 03:10 PM

I switched insertBeforeCurrent() to this (see below) and it works if current is the first element in the list, but otherwise I keep getting a NullPointerException. InsertAfterCurrent() works fine with the reverse version of the code, so I really don't understand why the BeforeCurrent one is giving me an error. Please help, this is incredibly frustrating.
void insertBeforeCurrent(int data){
     Node node = new Node(data);
     node.prev = current.prev;
     node.next = current;
     if (current == front) {
       front = node;
     }
     else {
       current.prev.next = node;
     }
     current.prev = node;
 }



Edited by macosxnerd101: Please, :code:.

This post has been edited by macosxnerd101: 29 June 2010 - 03:48 PM

Was This Post Helpful? 0

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,257
  • Joined: 27-December 08

Re: Doubly Linked List

Posted 29 June 2010 - 03:53 PM

You never initialize current, and you leave head and tail as null. So when you go to reference variables from any of these Objects, you will get NullPointerExceptions b/c you have variables/pointers which don't reference Objects in memory.

My suggestion for this method is to check the following:
//some pseudo-code
function insertBeforeCurrent(data)
     if head is null
        set head to hold the data
        set current to reference head
        set back to reference head
     end if

     else
        create new node n to hold data
        set n.prev to reference current.prev
        set current.prev.next to reference n
        set n.next to reference current
     end else
end function


Was This Post Helpful? 0
  • +
  • -

#5 Guest_sam jenkins*


Reputation:

Re: Doubly Linked List

Posted 29 June 2010 - 04:39 PM

Thats basically what I have been doing. I've tried a couple different ways to do insertBeforeCurrent() and it all turns out the same way, it only works if current is the front of the list, otherwise it gives me an error. How should I got about initializing current? I think that is what my problem is here because the simple movePrev() method where the body is "current = current.prev" is still not working.
Was This Post Helpful? 0

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,257
  • Joined: 27-December 08

Re: Doubly Linked List

Posted 29 June 2010 - 09:30 PM

That maybe what you want to do and have tried to do, but it isn't exactly what you're doing. As I said before, when you instantiate your List, you have null head, back, and current Nodes. This is all well and good, so long as you understand that this means you have an empty list and compensate for this accordingly. Your methods have all assumed current isn't null, and you obviously have seen the results of such. My pseudo-code should be fairly straight-forward to implement, and I cover similar concepts in my Linked List Tutorial, though my methods are designed to show implementations of the major List interface methods.

current = current.prev;


If current is null, you cannot reference current.prev, as there is no Object for the variable current to reference in memory. Remember, your variables are juts pointers. It is the Objects in memory that allow you to do work and reference variables. If your pointer doesn't reference an Object in memory, then it can't do these things.
Was This Post Helpful? 0
  • +
  • -

#7 Guest_sam jenkins*


Reputation:

Re: Doubly Linked List

Posted 29 June 2010 - 10:58 PM

What I don't understand is that current is defined in exactly the same way in insertBeforeCurrent() as it is in insertAfterCurrent(), yet insertBefore doesn't work. Same goes for the way current is defined in moveNext() and movePrev(). Do you have any other ideas what it could possibly be that is giving me these errors?
Was This Post Helpful? 0

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,257
  • Joined: 27-December 08

Re: Doubly Linked List

Posted 30 June 2010 - 07:18 AM

Without seeing your insertAfterCurrent() method, I can't make any judgements. If you want me to, I'd be happy to take a look. However, I have already explained why you are getting your errors in insertBeforeCurrent() and my suggestions still stand. Not to come across the wrong way, but whether or not you want to implement my suggestions is up to you.
Was This Post Helpful? 0
  • +
  • -

#9 Guest_sam jenkins*


Reputation:

Re: Doubly Linked List

Posted 30 June 2010 - 12:19 PM

Heres what I have for my insertAfter();
void insertAfterCurrent(int data){
Node node = new Node(data);
node.prev = current;
node.next = current.next;
if (current == back) {
back = node;
}
else {
current.next.prev = node;
}
current.next = node;
}
Here's what I came up with from your pseudocode, but I was still getting an error.

Node node = new Node(data);
if (front == null) {
front = node;
current = front;
back = front;
}
else {
node.prev = current.prev;
current.prev.next = node;
node.next = current;
}
It works if the list is empty, but once I try to add a second element it gives me a null pointer again.
}
Was This Post Helpful? 0

#10 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,257
  • Joined: 27-December 08

Re: Doubly Linked List

Posted 30 June 2010 - 02:14 PM

Before I take a look at your code, please re-post it using code tags as I have asked twice before. It makes it a lot easier for me to read your code. :)
Was This Post Helpful? 0
  • +
  • -

#11 Guest_sam jenkins*


Reputation:

Re: Doubly Linked List

Posted 30 June 2010 - 02:19 PM

void insertAfterCurrent(int data){
Node node = new Node(data);
node.prev = current;
node.next = current.next;
if (current == back) {
back = node;
}
else {
current.next.prev = node;
}
current.next = node;
}

This post has been edited by macosxnerd101: 30 June 2010 - 02:22 PM
Reason for edit:: Removed [indent] tag. BBCode is not parsed within code tags.

Was This Post Helpful? 0

#12 Guest_sam jenkins*


Reputation:

Re: Doubly Linked List

Posted 30 June 2010 - 02:23 PM

 void insertAfterCurrent(int data){
     Node node = new Node(data);
     node.prev = current;
     node.next = current.next;
     if (back == null) {
       back = node;
       current = back;
     }
     else {
       current.next.prev = node;
   }
     current.next = node;
   }
   }


void insertBeforeCurrent(int data){
     Node node = new Node(data);
     node.prev = current;
     node.next = current.next;
     if (front == null) {
       front = node;
       current = front;
     }
     else {
       current.prev.next = node;
     }
     current.prev = node;
   }

Was This Post Helpful? 0

#13 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,257
  • Joined: 27-December 08

Re: Doubly Linked List

Posted 30 June 2010 - 02:32 PM

You are getting a NullPointerException here probably b/c current.prev == null. That was a mistake in my pseudo-code. I forgot about this, but I hope it at least helped get you on the right track. :)
current.prev.next = node;



The reason before insertAfterCurrent() works, but insertBeforeCurrent() does not is b/c you check to see if there will be a next Node for current in after(), but you do not do the same for current.prev in before().

This post has been edited by macosxnerd101: 30 June 2010 - 02:32 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1