Hello! I've created a sorted linked list and now I'm trying to figure out how to remove duplicates. I wanted to add code that would do this in the Add method I created but I can't seem to figure it out. I feel like this should be relatively easy but I'm a bit brain dead right now.
In my add method I check the index to see where an item is to be added. "Index" is an int variable but I wanted to check to see if "item", a comparable, was the same item stored before it. I wanted to use the compareTo method but I would get a type mismatch. Does anyone have an idea of a better way to do this?
Here is the code for my add method:
package sortedListReferenceBased;
public class SortedListReferenceBasedIterativeNoDuplicates
implements SortedListInterface {
// reference to linked list of items
private Node head;
private int numItems; // number of items in list
public SortedListReferenceBasedIterativeNoDuplicates() {
numItems = 0;
head = null;
} // end default constructor
public boolean sortedIsEmpty() {
return numItems == 0;
//TODO
} // end sortedIsEmpty
public int sortedSize() {
return numItems;
//TODO
} // end sortedSize
private Node find(int index) {
// --------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: index is the number of the desired
// node. Assumes that 1 <= index <= numItems+1
// Postcondition: Returns a reference to the desired
// node.
// --------------------------------------------------
Node curr = head;
for (int skip = 1; skip < index; skip++) {
curr = curr.getNext();
} // end for
return curr;
} // end find
public Comparable sortedGet(int index)
throws ListIndexOutOfBoundsException {
if (index >= 1 && index <= numItems){
Node curr = find(index);
Object dataItem = curr.getItem();
return (Comparable) dataItem;
}
else {
throw new ListIndexOutOfBoundsException("List index out of bounds on get.");
}
//TODO
} // end sortedGet()
public void sortedAdd(Comparable item) throws ListException{
int index = locateIndex(item); //to find location where item should be added
if( index >=1 && index <= numItems+1){
//if adding an item to the very beginning of list
if (index == 1){
Node newNode = new Node(item,head);
head = newNode;
}
if (item.compareTo(something something?)== 0){ //if item is a duplicate of previous item do nothing
System.out.println("No duplicates!");
}
//advances
else {
Node prev = find(index-1); //finds out where previous node is
Node newNode = new Node(item, prev.getNext()); //creates Node with item you wish to add
prev.setNext(newNode); //links new node with previous node
}
numItems++;
}//end main if statement
else {
throw new ListIndexOutOfBoundsException("List index out of bounds on add.");
}
//TODO
} // end sortedAdd()
public void sortedRemove(Comparable item) throws ListException {
int index = locateIndex(item);
if (index >= 1 && index <= numItems){ //if the index is greater than 1 (meaning list not empty) and
//index doesn't exceed list size do the following:
//if index is value of one then delete first node in this special way
if (index == 1) {
head = head.getNext();
}
//if there is only one item in the list then set head to nothing so index out of bounds error won't occur
if (numItems == 1){
head = null;
}
else { //if none of these things occur go ahead and delete item, allocating Nodes accordingly
Node prev = find(index-1);
Node curr = prev.getNext();
prev.setNext(curr.getNext());
}
numItems--;//must account for one less item
}
if (!sortedIsEmpty()){
System.out.println("Item does not exist!");
}
else { //if index doesn't meet if statement requirements
throw new ListIndexOutOfBoundsException("List index out of bounds on remove.");
}
//TODO
} // end sortedRemove
public void sortedRemoveAll() {
// setting head to null causes list to be
// unreachable and thus marked for garbage
// collection
head = null;
numItems = 0;
} // end sortedRemoveAll
//Returns the position where item belongs or exists in a sorted list;
//item and the list are unchanged.
public int locateIndex(Comparable item) {
Node curr = head;
for (int i = 1; i <= sortedSize(); i++){
if (item.compareTo(curr.getItem())<= 0){
return i;
}//end if
else {
curr = curr.getNext();
}//end else
}//end for
return sortedSize()+1;
//TODO
} //end locateIndex()
} // end ListReferenceBased
I apologize for the strange formatting. It's pretty rough right now. I also apologize if this question is really obvious! Haha