[mike_rotch]

1st post

This is a homework assignment. The task is to create a doubly linked list in ascending order by weight and name using input from the console.

Currently, I have a singly linked list that prints the list in ascending order by weight.
What I am missing is another pointer/link that points to the next name in ascending order. I would like some guidance in the right direction for making the rest of the insert method so that it points to the next name in ascending order.

Here are my classes:

Person.java

/*
Simple person class encapsulating the idea of a person as including a name and weight.
*/

public class Person {
	private String name;
	private double weight;

	public Person (String newName, double newWeight) {
		name = newName;
		weight = newWeight;
	}

	//Returns a copy of the object x.
	public Person (Person x) {
		name = x.name;
		weight = x.weight;
	}
	
	//Accessors
	public String getName () {
		return name;
	}
	
	public double getWeight () {
		return weight;
	}
	
	//Print List
	public String toString () {
		return (name + " - " + weight + " ");
	}
}

PersonNode.java

public class PersonNode {

	private Person person;
	
	//Pointer to next weight
	private PersonNode next;
	
	//Pointer to next name
	private PersonNode previous;

	public PersonNode () {
		person = null;
		next = null;
	}
	
	public PersonNode (Person x) {
		setPerson(x);
		next = null;
	}

	public Person getPerson () {
		return new Person(person);
	}
	
	public PersonNode getNext () {
		return next;
	}
	
	public PersonNode getPrevious () {
		return previous;
	}

	public void setPerson (Person x) {
		person = new Person(x);
	}

	public void setNext (PersonNode newNode) {
		next = newNode;
	}

	public void setPrevious (PersonNode newNode) {
		previous = newNode;
	}
	
}

ShellLinkedList.java

//Abstract class that has methods common to all sub classes that manipulate linked 
//lists

public abstract class ShellLinkedList {
	//head points to weight front
	protected PersonNode head;

	//headName points to name front
	protected PersonNode headName;

	//Count number of nodes
	protected int nodeCount;

	public ShellLinkedList () {
		head = null;
		headName = null;
		nodeCount = 0;
	}
	
	public String toString () {
		String listString = "";

		PersonNode current = head;

		for (int i = 0; i < nodeCount; i++) {
			listString += current.getPerson().toString();
			current = current.getNext();
		}

		return listString;
	}

}

PersonLinkedList.java

public class PersonLinkedList extends ShellLinkedList {

	public PersonLinkedList () {
		super();
	}
	
	public void insert(Person x) {
	
	//Create node
	PersonNode pn = new PersonNode(new Person(x));
	
	//current points to the weightFront head node
	PersonNode current = head;

	//Previous points to current's previous node
	PersonNode previous = null;


	while (current != null && (current.getPerson()).getWeight() < x.getWeight()) {
		previous = current;
		current = current.getNext();
	}

	//if 1st element insert as head
	if (previous == null) {
		pn.setNext(head);
		head = pn;
	}
	else {
		pn.setNext(current);
		previous.setNext(pn);
	}
	
	nodeCount++;
	
	}

}

PersonLinkedListTest.java

import java.util.Scanner;

public class PersonLinkedListTest {
	public static void main (String [] args) {
		int count = 0;
		Person person;
		String info;
		String name;
		Double weight;
		int whiteSpace;

		PersonLinkedList people = new PersonLinkedList();
		Scanner input = new Scanner(System.in);
		
		//Prime read, prompt for name and weight convert to double and feed to person
		System.out.print("Enter person name and weight: ");
		info = input.nextLine();
		whiteSpace = info.indexOf(' ');
		name = info.substring(0,whiteSpace);
		weight = new Double(info.substring(whiteSpace+1,info.length()));
		person = new Person(name,weight);

		//Insert into linked list
		people.insert(person);

		//Loop
		while (count != 2) {
			System.out.print("Enter person name and weight: ");
			info = input.nextLine();
			whiteSpace = info.indexOf(' ');
			name = info.substring(0,whiteSpace);
			weight = new Double(info.substring(whiteSpace+1,info.length()));
			person = new Person(name,weight);
			people.insert(person);
			count++;
		}	
		
		System.out.println("List sorted by weights in ascending order:");
		System.out.println(people.toString());

		System.out.println("\nList sorted by names in ascending order:");
		
	}
}

In PersonNode.java, I've created a next pointer that acts as the pointer for the next weight and I'm guessing head would point to the front of the weights.

Does that mean I will need another "head" pointer to point to the head of names and then traverse the list in the direction of another pointer called "previous" that points to the next node in ascending name order?

Also, for the string comparison the code I will need would be something along the lines of
int result = ((current.getPerson().getName()).compareTo(x.getName());
right?

Thank you for taking your time to read this post.

[macosxnerd101]

In your LinkedList class, you would traverse the LinkedList normally when inserting the elements. The difference is, as you described, you need the comparison to assure that the new element does not exceed the element before it. Are you familiar with Insertion Sort; if not, that is a great algorithm for dealing with Linked Lists. Essentially what you are building is a PriorityQueue.

[mike_rotch]

Thanks for the reply. I got a doubly linked list that is inserting by weight in ascending order. But somehow I need to set the previous pointer so that it is always pointing to the next node in alphabetical order. I can't call a sort on the weight doubly linked list so what would I need to change so that the previous pointer always points to the next node in alphabetical order and the next pointer always points to the next node by weight in ascending order?

public class PersonLinkedList {

	private PersonNode head;
	private int nodeCount;

	public PersonLinkedList () {
		head = null;
		nodeCount = 0;
	}
	
public void insert(Person x) {
	
	//Create node
	PersonNode pn = new PersonNode(new Person(x));

	PersonNode current = head;
	PersonNode previous = null;
	
	while (current != null &&
        	(current.getPerson()).getWeight() < x.getWeight()) {

        	previous = current;
        	current = current.getNext();
    	}

	if (previous == null) {

        	pn.setNext(head);
        	head = pn;
    	}
	else  {

        	pn.setNext(current);
        	previous.setNext(pn);
        	pn.setPrevious(previous);

    	}

	nodeCount++;
}

	public String toString () {
		String listString = "";

		PersonNode current = head;

		for (int i = 0; i < nodeCount; i++) {
			listString += current.getPerson().toString();
			current = current.getNext();
		}

		return listString;
	}

}