Doubly Linked list

[charliebhoy]

Hi again,
I have updated the program to a doubly linked list
but were printing backwords it only prints first number/s (last Number/s as its going backwards)
does anyone have any idea whats up ?
below are the 3 files................................


// Test class
import java.io.*;

public class IntListTest
{

static BufferedReader keyboard = new
BufferedReader(new InputStreamReader(System.in));
static PrintWriter screen = new PrintWriter(System.out,true);



public static void main(String[] args) throws IOException
{

IntList list = new IntList();
int choice,element;


do {
screen.println();
screen.println();
screen.println( "1. Add 2. Display 3.Reverse 4.Remove 5.Quit");
screen.print( "Enter choice ");
choice = new Integer(keyboard.readLine()).intValue();
switch (choice)
{
case 1 : screen.println("Enter new value ");
element = new
Integer(keyboard.readLine()).intValue();
list.add(element);
break;

case 2 : list.display();
break;

case 3 : list.displayR();
break;

case 4: screen.println("Enter Value to Remove");
element = new Integer(keyboard.readLine()).intValue();

list.remove(element);
break;

case 5 : screen.println("Quitting");
break;
default: screen.println("Invalid choice");
}
} while (choice != 4);
}
}


// Test class
import java.io.*;

public class IntListTest
{

static BufferedReader keyboard = new
BufferedReader(new InputStreamReader(System.in));
static PrintWriter screen = new PrintWriter(System.out,true);
public static void main(String[] args) throws IOException
{

IntList list = new IntList();
int choice,element;


do {
screen.println();
screen.println();
screen.println( "1. Add 2. Display 3.Reverse 4.Remove 5.Quit");
screen.print( "Enter choice ");
choice = new Integer(keyboard.readLine()).intValue();
switch (choice)
{
case 1 : screen.println("Enter new value ");
element = new
Integer(keyboard.readLine()).intValue();
list.add(element);
break;

case 2 : list.display();
break;

case 3 : list.displayR();
break;

case 4: screen.println("Enter Value to Remove");
element = new Integer(keyboard.readLine()).intValue();

list.remove(element);
break;

case 5 : screen.println("Quitting");
break;
default: screen.println("Invalid choice");
}
} while (choice != 4);
}
}



// IntList class
public class IntList
{
Node head,tail,current;

// Constructor
IntList()
{
head = new Node(0, null);
tail= new Node(0,null);
}

// Add
void add(int newElement)
{

Node newNode = new Node(newElement, null);

if (head.next == null)
{
head.next = newNode;
tail.previous = newNode;
} else {

if (newNode.element < head.next.element)
{
newNode.next = head.next;
head.next = newNode;
tail.previous=newNode;
} else {
Node probe;
for (probe = head.next;probe.next != null && newNode.element > probe.next.element;
probe = probe.next);
newNode.next = probe.next;
probe.next = newNode;
tail.previous=newNode;
}
}
}

// Display
void display()
{
for (Node probe = head.next; probe != null; probe = probe.next)

probe.display();
}

// Display reverse
void displayR()
{
for (Node probe = tail.previous; probe != null; probe = probe.previous)
probe.display();
}
//remove
void remove(int targetElement) {
Node probe,previous;
if (head.next.element == targetElement)
head.next = head.next.next;
else {
previous = head.next;
probe = head.next.next;
while (probe != null && probe.element != targetElement) {
previous = probe;
probe = probe.next;
}
if (probe != null)
previous.next = probe.next;
}
}
}


__________________

[JGRobinson]

Hi Charlie,

I cannot compile it, it is complaining that it cannot find the Node class and I cannot find it in the J2SE SDK.

Can you tell me where it is, or post the source if its hand rolled.

Cheers
Graham

[charliebhoy]

Hi Graham
I pasted same file twice methinks,
anyway heres the node class file:


import java.lang.Exception;
// Node class
class Node
{

int element;
Node next,previous,current;

// Constructor
Node(int newElement, Node newNode)
{
element = newElement;
next = newNode;
previous = newNode;
current = newNode;
}

int getElement()
{
return element;
}

Node getNext()
{
return next;
}

Node getPrevious()
{
return previous;
}

Node getCurrent()
{
return current;
}


void display()
{
System.out.println(element);
}
void displayR()
{
System.out.println(element);
}
void remove(int targetElement)
{

}

}

[doredson]

Seems like Node.current should not be a member of Node at all...

Why would each Node instance have to have a "current" reference? They just need to know previous and next.

Lists need to know head, tail, and current (current is actually arguable here, in that only a loop need worry about current).

ie:

for(Node current = head; current != null; current = current.getNext()) {
//do something with the current Node
System.out.println(current.toString());
}

The print() method on Lists should probably be changed to override toString();

This way you don't have to send that info to System.out, necessarily. You could put it in a MessageBox or TextArea, for instance.

[JGRobinson]

Hi,

I think the problem is that when you are adding the nodes to the tree, you are resetting the forward (next) pointers, but not the reverse (previous) pointers.

The only exception to this is the tail pointer which you are updating, this is why during the reverse display you only get the last item displayed.

Hope this helps.
Graham

[doredson]

Fixed.
Node:

package list;

//Node class
class Node {
	int element;

	private Node next;
	private Node previous;

	Node(int newElement) {
		this(newElement, null, null);
	}

	// Constructor
	Node(int newElement, Node prev, Node next) {
		element = newElement;
		setPrevious(prev);
		setNext(next);
	}

	int getElement() {
		return element;
	}

	public String toString() {
		return String.valueOf(element);
	}

	/**
	 * @return Returns the next.
	 */
	public Node getNext() {
		return next;
	}

	/**
	 * @param next
	 *            The next to set.
	 */
	public void setNext(Node nextNode) {
		if (nextNode == null) {
			nextNode = this;
		}

		next = nextNode;
		nextNode.previous = this;
	}

	/**
	 * @return Returns the previous.
	 */
	public Node getPrevious() {
		return previous;
	}

	/**
	 * @param previous
	 *            The previous to set.
	 */
	public void setPrevious(Node previousNode) {
		if (previousNode == null) {
			previousNode = this;
		}

		previous = previousNode;
		previousNode.next = this;
	}
}

IntList:

package list;

// IntList class
public class IntList {
	Node head;

	// Constructor
	IntList() {
		head = null;
	}

	// Add
	void add(int newElement) {
		if (head == null) {
			head = new Node(newElement, null, null);
		} else {
			Node sentinel = head.getPrevious();
			if(sentinel.getElement() <= newElement) {
				new Node(newElement,sentinel,head);
			} else {
				Node current = head;
				do {
					if(newElement <= current.getElement())
						break;
					current = current.getNext();
				} while (current != head);

				if(newElement >= current.getElement()) {
					Node newNode = new Node(newElement, current, current.getNext());
				} else {
					//else insert before
					Node newNode = new Node(newElement, current.getPrevious(), current);
					if(current == head) {
						// the new node is now the head of the list
						head = newNode;
					}
				}
			}
		}
	}

	// Display
	public String toString(boolean forward) {
		StringBuffer sb = new StringBuffer();

		if (head != null) {
			Node probe = null;
			if(forward)
				probe = head;
			else
				probe = head.getPrevious();
			
			Node sentinel = probe;

			do {
				sb.append(probe.toString());
				if (forward)
					probe = probe.getNext();
				else
					probe = probe.getPrevious();
				if (probe != sentinel)
					sb.append(", ");
			} while (probe != sentinel);
		}

		return sb.toString();
	}

	// Display reverse
	public String toString() {
		return toString(true);
	}

	//remove
	void remove(int targetElement) {
		if(head != null) {
			Node probe = head;
			
			while(probe.getElement() != targetElement && (probe = probe.getNext()) != head) {
			}
			
			if(probe.getElement() == targetElement) {
				Node prev = probe.getPrevious();
				Node next = probe.getNext();
				
				if(next == probe) {
					//the simple case is that there was one element, so set head to null
					head = null;
				} else {
					probe.setNext(null);
					//not really necessary, but IntList shouldn't know about the inner workings of Nodes
					probe.setPrevious(null);
					
					prev.setNext(next);
					//not really necessary, but IntList shouldn't know about the inner workings of Nodes
					next.setPrevious(prev);
					
					if(probe == head) {
						head = next;
					}
				}
			}
		}
	}
}

IntListTest:

package list;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class IntListTest {

	static BufferedReader keyboard = new BufferedReader(new InputStreamReader(
			System.in));

	static PrintWriter screen = new PrintWriter(System.out, true);

	public static void main(String[] args) throws IOException {

		IntList list = new IntList();
		int choice, element;

		do {
			screen.println();
			screen.println();
			screen.println("1. Add 2. Display 3.Reverse 4.Remove 5.Quit");
			screen.print("Enter choice ");
			screen.flush();
			choice = new Integer(keyboard.readLine()).intValue();
			screen.println();
			switch (choice) {
			case 1:
				screen.print("Enter new value ");
				screen.flush();
				element = new Integer(keyboard.readLine()).intValue();
				list.add(element);
				break;

			case 2:
				screen.println(list.toString());
				break;

			case 3:
				screen.println(list.toString(false));
				break;

			case 4:
				screen.print("Enter Value to Remove ");
				screen.flush();
				element = new Integer(keyboard.readLine()).intValue();

				list.remove(element);
				break;

			case 5:
				screen.println("Quitting");
				break;
			default:
				screen.println("Invalid choice");
			}
		} while (choice != 5);
	}
}

[doredson]

er, head should be private, too.

[charliebhoy]

Hi lads
thanks Graham & doredson,
I just logged on there and read your
helps, will get onto it just now
thanks