0
Я создал отсортированный связанный список, и теперь я пытаюсь выяснить, как удалить дубликаты. Я хотел добавить код, который будет делать это в методе «Добавить», который я создал, но я не могу понять его. Я чувствую, что это должно быть относительно легко, но сейчас я немного мертв мозгом.Поиск дубликатов в отсортированном, связанном списке
В моем методе добавления я проверяю индекс, чтобы увидеть, где элемент должен быть добавлен. «Индекс» является переменной int, но я хотел проверить, был ли «элемент», сопоставимый, тем же самым предметом, который был сохранен перед ним. Я хотел использовать метод compareTo, но я бы получил несоответствие типа. Есть ли у кого-нибудь идеи лучшего способа сделать это?
Вот код для моего метода добавления:
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
Я извиняюсь за странное форматирование. Сейчас это довольно грубо. Я также извиняюсь, если этот вопрос действительно очевиден! Ха-ха
Это назначение для класса Data Structures. Мой учитель попросил нас создать его таким образом. Мы не узнали о деревьях. hashtables или что-то в этом роде, но мы пытаемся сделать это задание с очень небольшим знанием. Поэтому почему это так странно. Спасибо за ваше понимание! – Bell
Вы должны добавить тег домашней работы к этому вопросу. –