Static Doubly Linked Lists....

[Justin Fox]

ok here is the assignment description...

This program is basically the same program as 3L, but the implementation will be static rather than dynamic. In this case, all the linked lists will be taken from a single array of nodes defined as static member data.
Dll.StaticCls.cpp should be of considerable use. Your static member data
array should allocate 60 nodes. Convert your existing functions to deal with the nodes in the array. Add methods deleteNode and newNode that mirror delete and new. You should initially place all the nodes in the array in the "freelist", which may be linked how ever you please.


ok, now in this, so i would have a static member data array like the following...

    
private static Node[] theNodes = new Node[60];

all i really want to know is, all im doing is allocating memory in an array, for my nodes, instead of letting the OS do it for me right?

so everytime i call newNode, it just takes the first node reference at
theNodes[freelist] and assign that spot in the array to what ever node I
create, then freelist = theNodes[freelist].next;

where freelist points to the first node reference in the "theNodes" array;

but even though im creating my nodes in the array in order? can I still
modify next and prev to what ever node I want, or do i need to create the node and insert it in order into the "theNodes" array?

thanks,
justin

[marc weber]

Originally posted by Justin Fox:
...all i really want to know is, all im doing is allocating memory in an array, for my nodes, instead of letting the OS do it for me right?

Yes, new Node[60] creates an array object containing 60 Node references -- all initialized to null at this stage. In contrast to something that can be dynamically resized like a List, this array's size is now set and won't be changing. (Note: I think you mean the VM instead of the OS.)

Originally posted by Justin Fox:
...can I still modify next and prev to what ever node I want, or do i need to create the node and insert it in order into the "theNodes" array?

The array is just a place to store references to Node instances. The "next" and "prev" instance variables in a Node have nothing to do with that Node's position in the array. For example, the Node at index 3 might have a "next" value of 11 and a "prev" value of 49. The key here is that you can randomly access array elements, so jumping from 49 to 3 to 11 should be no problem.
[ July 15, 2006: Message edited by: marc weber ]

[Justin Fox]

thanks dude!

[Justin Fox]

ok in the following program, i need to initially link the nodes in the array theNodes[], but how do i go about doing that when you cant do it outside a constructor, and a non-static method can't call a static method..

code:

    
import java.util.Scanner;
import java.io.*;
 
 
public class StaticDDLL
{
private static final double NULL_DOUBLE = -99.0;
private static final int NULL_INDEX = -1;
private static final int NULL_VALUE = -99;
 
private class Node
{
 
private int EmpNum;
private double EmpHrs;
 
private int nextNum, prevNum;
private int nextHrs, prevHrs;
 
public Node()
{
EmpNum = NULL_VALUE;
EmpHrs = NULL_DOUBLE;
 
nextNum = nextHrs = prevNum = prevHrs = NULL_INDEX;
}
 
}
 
private static Node[] theNodes = new Node[60];
 
private static int freeNodes= 60;
private static int freelist = 0;
private static int NumofNodes = 60;
 
public static int getFreeNodes() {return freeNodes;}
 
 
private static void deleteNode(int old)
{
 
theNodes[old].nextNum = freelist;
theNodes[old].EmpNum = NULL_VALUE;
theNodes[old].prevNum = NULL_INDEX;
 


freelist = old;
freeNodes ++;

}
 
 
 
 
private static int newNode()
{
 
if(freelist == NULL_INDEX)
return NULL_INDEX;
 
else
{
 int avail = freelist;
freelist = theNodes[freelist].nextNum;
 freeNodes --;
return avail;
}

}
 
private int head = NULL_INDEX;
private int curr = NULL_INDEX;
 
public StaticDDLL()
{
 
 
 
makeEmpty();

 
}
 
public void makeEmpty()
{
 
if(head == NULL_INDEX)
{
head = newNode(); System.out.print(head);
 
if(head == NULL_INDEX)
displayMessageAndExit("out of freespace");
 

else
{
theNodes[head].EmpNum = NULL_VALUE;
theNodes[head].EmpHrs = NULL_DOUBLE;
 
theNodes[head].nextNum = head;
theNodes[head].prevNum = head;
 
theNodes[head].nextHrs = head;
theNodes[head].prevHrs = head;
 
curr = head;
}
    }
else if ( isNotEmpty())
{
toHeadNode();
 
while(toNextNode())
{
deleteCurrentNode();
}
}
else
;
}
 
 
public boolean isNotEmpty()
{
if(head == NULL_INDEX)
displayMessageAndExit("is not empty");

return theNodes[head].nextNum != head;
}
 
 
public void deleteCurrentNode()
{
      int deadNode = curr;
 
curr = theNodes[curr].prevNum;
 
theNodes[theNodes[deadNode].nextNum].prevNum = theNodes[deadNode].prevNum;
theNodes[theNodes[deadNode].prevNum].nextNum = theNodes[deadNode].nextNum;
 
theNodes[theNodes[deadNode].nextHrs].prevHrs = theNodes[deadNode].prevHrs;
theNodes[theNodes[deadNode].prevHrs].nextHrs = theNodes[deadNode].nextHrs;
 
deleteNode(deadNode);
}
 
public boolean toHeadNode()
{
if(head == NULL_INDEX)
displayMessageAndExit("to head node");
 
else
curr = head;
 
return true;
}
 
public boolean toNextNode()
{
 
if(curr == NULL_INDEX)
displayMessageAndExit("to next node");
 
else
curr = theNodes[curr].nextNum;

return notAtHead();
}
 
public boolean notAtHead()
{
if(curr == NULL_INDEX || head == NULL_INDEX)
displayMessageAndExit("not at head");
 
return curr != head;
}
 
private void displayMessageAndExit(String methodName )
{
  System.out.println( "Fatal error in " + methodName + " .");
  System.exit(0);
}
 
 
private void insertAscending(int n)
{
boolean found = false;
boolean found2 = false;

int curr2 = theNodes[head].nextNum;
int curr3 = theNodes[head].nextHrs;
 
if(theNodes[curr2].nextNum == head && theNodes[curr3].nextHrs == head)
{
theNodes[head].nextNum = n;
theNodes[head].prevNum = n;
theNodes[n].nextNum = head;
theNodes[n].prevNum = head;
 
theNodes[head].nextHrs = n;
theNodes[head].prevHrs = n;
theNodes[n].nextHrs = head;
theNodes[n].prevHrs = head;
 

}

else
{
while(theNodes[curr2].nextNum != head && theNodes[curr3].nextHrs != head)
{

if(found == false)
{

if(theNodes[curr2].EmpNum > theNodes[n].EmpNum)
{
insertNum(n,theNodes[curr2].prevNum,curr2);
found = true;
}
}
 
if(found2 == false)
{

if(theNodes[curr3].EmpHrs > theNodes[n].EmpHrs)
{
insertHrs(n,theNodes[curr3].prevHrs,curr3);
found2 = true;
}
}

if(theNodes[n].EmpNum > theNodes[curr2].EmpNum && theNodes[curr2].nextNum == head)
insertNum(n,curr2,theNodes[curr2].nextNum);
 
if(theNodes[n].EmpHrs > theNodes[curr3].EmpHrs && theNodes[curr3].nextHrs == head)
insertHrs(n,curr3,theNodes[curr3].nextHrs);

curr2 = theNodes[curr2].nextNum;
curr3 = theNodes[curr3].nextHrs;
}


}
found = true;
found2 = true;

}
 
 
public void insertNum( int newNode ,int prevNode, int nextNode )
  {
       
                                   
  theNodes[newNode].nextNum = nextNode;      
 theNodes[newNode].prevNum = prevNode;
          
  theNodes[prevNode].nextNum = newNode;     
  theNodes[nextNode].prevNum = newNode;       
  }  
 
//////////////////inserts a node containing hours between two nodes////////////////
 
public void insertHrs( int newNode ,int prevNode, int nextNode )
  {
       
                                   
  theNodes[newNode].nextHrs = nextNode;      
 theNodes[newNode].prevHrs = prevNode;
          
  theNodes[prevNode].nextHrs = newNode;     
  theNodes[nextNode].prevHrs = newNode;       
  }
 
 
 
public void input(int num, File file)
{

Scanner scan = null;
boolean second = false;
try
{
scan = new Scanner(file);
}
catch(FileNotFoundException e)
{
System.out.println("file not found");
}

String Answer = "", Answer2 = "";
int Int = 0;
double Dbl = 0;
int count = 0;
curr = theNodes[head].nextNum;
 
while( count < num)
{

 
Answer = scan.next(); 
Int = Integer.parseInt(Answer);
 
Answer2 = scan.next();
Answer2 = scan.next();
Answer2 = scan.next();
Answer2 = scan.next();
Answer2 = scan.next();
 
Dbl = Double.parseDouble(Answer2); 
 
int noo = newNode();
 
theNodes[noo].EmpNum = Int;
theNodes[noo].EmpHrs = Dbl;


insertAscending(noo);



Answer = scan.nextLine();
count ++;
 
}

 
}
 
 
 
public String toString()
{
 
String result1 = "";
String result = ""; 
int count = 0;
curr = theNodes[head].nextNum; 
 
while(curr != head)
{

result1 ="\n\n\t Employee Name:\t Employee hours:\n\t\t";
result += theNodes[curr].EmpNum + "\t\t" + theNodes[curr].EmpHrs+"\n\t\t";
 



curr = theNodes[curr].nextNum;
 
}
 
return result1 + result;
}
}

[ July 17, 2006: Message edited by: Justin Fox ]

[marc weber]

Originally posted by Justin Fox:
...a non-static method can't call a static method...

A non-static (instance) member cannot be accessed from a static context, but the reverse is not true.

[Justin Fox]

ok, i have the static memeber data Node[] theNodes = new Node[60];

i need to modify the next pointer to be the next index of the current.

for example:

theNodes[0].nextNum = 1;

so that the node at index 0 points to 1 and 1 points to 2 and so on

but the Node[] is static, so i can't

say

theNodes[i] = new Node();
theNodes[i].nextNum = i +1;

i get a static/non-static conflict....

plz help,
Justin

[marc weber]

It would help if you provide some context (I don't see these lines anywhere in the 356 lines of code you posted earlier), along with the exact error message.

My guess is that these lines are inside a static method, and you are getting an error like...

...non-static variable this cannot be referenced from a static context
    theNodes[ i ] = new Node();
                    ^

In the context of your original code, Node is an inner class of StaticDDLL. An inner class is simply a nested class that is not static. Because they're not static, instances of inner classes are tied to an instance of the enclosing class. And in this context, when you say "new Node()," the implication is "this.new Node()," where "this" references an instance of the enclosing class. But in a static context, there is no "this" reference, which should explain the error message.
[ July 17, 2006: Message edited by: marc weber ]

[Justin Fox]

ok in the very beginning of my StaticDDLL class, i import Scanner and io

like so:

    
import java.util.Scanner;
import java.io.*;

im getting this error,

 
 
  
StaticDDLL.java:1: cannot resolve symbol
symbol  : class Scanner
location: package util
import java.util.Scanner;
                 ^
StaticDDLL.java:293: cannot resolve symbol
symbol  : class Scanner
location: class StaticDDLL
        Scanner scan = null;
        ^
StaticDDLL.java:297: cannot resolve symbol
symbol  : class Scanner
location: class StaticDDLL
        scan = new Scanner(file);
                   ^
3 errors
 

umm i'm most definately positive that you're supposed to capitalize the
's' on scanner.

help plz,
Justin

[Joanne Neal]

Are you using JDK1.5 ? Scanner didn't exist in earlier versions.

[Justin Fox]

I believe so, i mean, I'm using the univerities computers in the Computer Science Labs, would think they'd be up to date...

its using... (jdk1.5.0_06)

so... I don't know what the deal is...

justin

[marc weber]

Originally posted by Justin Fox:
I believe so, i mean, I'm using the univerities computers in the Computer Science Labs, would think they'd be up to date...

its using... (jdk1.5.0_06)...

Are you sure? At the command prompt, try typing "javac -version" (without the quotes). You will get a long error message for not including a source file, but the compiler version should appear at the top...

H:\>javac -version
[B]javac 1.5.0_06[/B]
javac: no source files
Usage: javac <options> <source files>
where possible options include:
...