I'm writing a Single Linked List that has the capability of sorting objects by a specific field as they are entered into the list. It's not adding everything, then sorting, but checking where it would be added before actually adding it. With this, I've developed a regex for three different types of sorted lists. My question is specifically about automatically sorting objects by a variable as they are added.
private void addDescending(E item)
{
if(head == null)
{
head = new Node<E>(item, null);
size++;
}
else
{
Node<E> p = head;
while(p.next != null)
{
if(p.data.compareTo(item) > 0)
{
Node<E> n = findPrev(p);
if(n == null)
{
Node<E> p1 = head;
head = new Node<E>(item, p1);
size++;
break;
}
n.next = new Node<E>(item, p);
size++;
break;
}
}
}
}
public int compareTo(Object o)
{
if(init == ((Person)(o)).getAge())
{
return 0;
}
else if(init > ((Person)(o)).getAge())
{
return 1;
}
else
{
return -1;
}
}
The compareTo(Object o) method is within the Person class. findPrev(Node<E> currentNode) is similar to a node.previous in a Double Linked List. For my project, a Single Linked List is easier to implement.
The access is private within the class but there is a public add(E item).
First, it checks to see if the head is null, creating one if it doesn't exist. If the head exists, it compares to the head. The compare code is in the Person class.
It checks the p.data that is checked as a Person to get its and compare it to the Person object that is being added's age. If it is larger, it goes before. If it is smaller, it goes after. If it is between, it goes before the larger number and before the smaller number. Meaning the head could be smaller than the number added, and as such the new head becomes the larger number with the old head becoming the next.
In my main, I'm adding four Person objects. They have the ages of 3, 10, 9, and 6 as tests. As the names are unimportant, they are simply Test1 through Test4. For some reason, it is only adding the first object. On a few occasions, I've had it add four objects, but four of the same object, even though all four are different. Why would it be adding only the same object repeatedly or only a single object?
Edit: I have just redone and updated the code. Here is the addDescending(E item) method now.
private boolean addDescending(E item)
{
if(head == null)
{
head = new Node<E>(item, null);
size++;
}
else
{
Node<E> p = head;
if(head.next == null && p.data.compareTo(item) > 0)
{
p.next = new Node<E>(item, null);
head = p;
size++;
return true;
}
else if(head.next == null && p.data.compareTo(item) < 0)
{
head.next = new Node<E>(item, null);
size++;
return true;
}
while(p.next != null && p.data.compareTo(item) < 0)
{
if(p.data.compareTo(item) > 0)
{
Node<E> n = findPrev(p);
Node<E> p1 = p.next;
p.next = new Node<E>(item, p1);
size++;
return true;
}
p = p.next;
}
}
return false;
}
This code checks each node's object's age against the input age. If the current node object age is larger than the input, it goes to the next node until it finds one that is smaller than it. It then gets the previous and next nodes, creating a new node and placing itself between those two.
However, my inputs are still the four Person objects. I am adding the ages 3, 10, 9, and 6 in order.
The expected result is to initially create a head with a the object's age as 3. Then when adding 10, 10 is greater than 3, so it would be added before the head, becoming the new head. 6 would be added, check against 10, and because 10 is greater than 6, move to the next node. The next node, 3, is smaller than 6, so it would add itself right between 10 and 3. Similar with 9, but between 10 and 6.
The problem is one I'm not quite sure of. As I said, I have four inputs. I am getting two objects now, but they are both the same. The object with name = "Test1"; and age = 3;. I don't see any other objects but these two, and I can guarantee they are only entered once each.
Edit2: Here's the code that creates the Person objects, the regex for the list constructor, the get, the result of the get, and the output.
Constructor and Regex:
public LList(String regex) throws IllegalArgumentException
{
size = 0;
this.regex = regex;
head = null;
if(!(regex.equals("A") || regex.equals("D") || regex.equals("U")))
{
throw new IllegalArgumentException("Unexpected Regex");
}
}
public void add(E item)
{
if(regex.equals("D"))
{
addDescending(item);
}
else if(regex.equals("A"))
{
addAscending(item);
}
else if(regex.equals("U"))
{
addUnsorted(item);
}
}
Get:
public E get(int index)
{
int i = 0;
Node<E> p = head;
if(index == 0 && head != null)
{
return head.data;
}
else
{
while(p.next != null)
{
if(i == index)
{
return p.data;
}
p = p.next;
i++;
}
}
return null;
}
Main:
Person ch0 = new Person("Test1", 3);
Person ch1 = new Person("Test2", 10);
Person ch2 = new Person("Test3", 9);
Person ch3 = new Person("Test4", 6);
// Create Descending Order List
System.out.printf("Descending List%n%n");
System.out.printf("%-10s %-4s%n", "Name", "Age");
System.out.printf("%-10s %-4s%n", "----------", "---");
LList<Person> dList = new LList<Person>("D");
dList.add(ch0);
dList.add(ch1);
dList.add(ch2);
dList.add(ch3);
dList.get(0).print();
dList.get(1).print();
dList.get(2).print();
dList.get(3).print();
Person print method:
System.out.printf("%-10s %-4d%n", name, age);
Thanks for all the help!
my 2 ct:
private boolean addDescending(E item){
if(head == null){ //case new list
head = new Node<E>(item, null);
size++;
return true;
} else if(head.data.compareTo(item)>0){ // case insert befor head
head = new Node<E>(item, head);
size++;
return true;
} else {
Node<E> p;
for(p = head;p.next!=null; p=p.next){//compare all except head
if(p.next.data.compareTo(item) > 0){
p.next = new Node<E>(item, p.next);
size++;
return true;
}
}
//not found: insert at the end
p.next = new Node<E>(item, null);
size++;
return true;
}
}