Java, LinkedList строк. Вставить в алфавитном порядке

Question

У меня есть простой связанный список. Узел содержит строку (значение) и целое число (число).

В связном списке, когда я вставляю, мне нужно вставить новый узел в алфавитном порядке. Если в списке есть узел с таким же значением, я просто увеличиваю количество узлов.

Я думаю, что мой метод действительно испорчен.

 public void addToList(Node node){
        //check if list is empty, if so insert at head
        if(count == 0 ){
            head = node;
            head.setNext(null);
            count++;
        }
        else{
            Node temp = head;
            for(int i=0; i<count; i++){
                //if value is greater, insert after
                if(node.getItem().getValue().compareTo(temp.getItem().getValue()) > 0){
                    node.setNext(temp.getNext());
                    temp.setNext(node);                   
                }
                //if value is equal just increment the counter
                else if(node.getItem().getValue().compareTo(temp.getItem().getValue()) == 0){
                    temp.getItem().setCount(temp.getItem().getCount() + 1);
                }
                //else insert before
                else{
                    node.setNext(temp);
                }
            }
        }      

    }

Хорошо, это вставляет все мои строки, но не в алфавитном порядке. Вы видите какую-либо ошибку?

 public Node findIsertionPoint(Node head, Node node){
        if( head == null)
            return null;

        Node curr = head;
        while( curr != null){
            if( curr.getValue().compareTo(node.getValue()) == 0)
                return curr;
            else if( curr.getNext() == null || curr.getNext().getValue().compareTo(node.getValue()) > 0)
                return curr;
            else
                curr = curr.getNext();
        }

        return null;
    }

    public void insert(Node node){
        Node newNode = node;
        Node insertPoint = this.findIsertionPoint(this.head, node);
        if( insertPoint == null)
            this.head = newNode;
        else{
            if( insertPoint.getValue().compareTo(node.getValue()) == 0)
                insertPoint.getItem().incrementCount();
            else{
                newNode.setNext(insertPoint.getNext());
                insertPoint.setNext(newNode);
            }
        }
        count++;
    }

Answer 1

В вашем коде есть несколько ошибок:

• Вставка в / до head на самом деле должна происходить в двух разных сценариях:
  • Если список пуст, head становится node
  • Если список не пустой, но node меньше первого элемента, head также становится node
    • В любом случае node ссылается на то, на что head указывал раньше (null или реальный узел), а head теперь указывает на node.
• Если вы не вставляете до head, тогда вы должны вставлять после какого-либо узла. Нам просто нужно найти, где это место. Есть два сценария:
  • node.getValue() > temp.getValue() и node.getValue() < temp.getNext().getValue()
  • node.getValue() > temp.getValue() и temp.getNext() == null
    • В любом случае, node вставляется между temp и temp.getNext()

Я предлагаю инкапсулировать после поиска точки вставки в своей собственной функции. То есть, учитывая список и значение, он должен возвращать узел. Если этот узел имеет то же значение, что и поисковое значение, просто увеличьте его; в противном случае вставьте после . В качестве особого случая, верните null, чтобы указать, что точка вставки до head.

---

В псевдокоде это будет выглядеть так:

FUNCTION findInsertionPoint(Node head, V value) RETURNS Node
  // return null if value needs to be inserted before head
  IF head == null OR value < head.getValue()
     RETURN null;

  // otherwise, either return a node with the given value,
  // or return a node after which value should be inserted
  Node curr = head;
  REPEAT
     IF curr.value == value
        RETURN curr;
     ELSEIF curr.getNext() == null OR curr.getNext().getValue() > value
        RETURN curr;
     ELSE
        curr = curr.getNext();

PROCEDURE insert(V value) {
  Node newNode = NEW Node(value);
  Node insertPoint = findInsertionPoint(this.head, value);
  IF insertPoint == null // insert before head
     newNode.setNext(this.head);
     this.head = newNode;
  ELSE
     IF insertPoint.getValue() == value
        insertPoint.incrementCounter();
     ELSE // insert after insertPoint
        newNode.setNext(insertPoint.getNext());
        insertPoint.setNext(newNode);

---

Обновление : я вижу, что вы перевели мой псевдокод на Java, но по какой-то причине вы пропустили коды, которые занимаются вставкой до head, когда head не пусто. В частности, вы необъяснимо пропустили эту часть:

IF head == null OR value < head.getValue()
             // ^^^^^^^^^^^^^^^^^^^^^^^^^^

и эта часть:

IF insertPoint == null 
   newNode.setNext(this.head); // <<<<<<<<<<<
   this.head = newNode;

Оба они необходимы ; это то, что позволяет вставлять "A" перед head в [ "B", "C", "D" ].

Вам нужно понять, почему они важны, и действительно спросить себя, почему вы решили удалить их. Объясните нам, мне, себе, почему вы это сделали; осознать ошибку и извлечь из нее урок.

Answer 2

Для этого вместо разработки с нуля своего собственного отсортированного списка я бы реализовал интерфейс очереди или расширил уже существующий PriorityQueue (или любую другую отсортированную коллекцию, которая может применяться лучше). Я бы определил класс Node как реализацию интерфейса Comparable или создал бы мою очередь с экземпляром Comparator и переопределил бы метод добавления PriorityQueue, чтобы добавить новый Node, только если другой объект еще не находится в очереди, иначе увеличивая счетчик. Если для безопасности типов используется java> 5.0, я бы использовал generic, чтобы разрешить только объекты Node в очереди.

Answer 3

Поскольку это домашнее задание, я не собираюсь давать вам исходный код. Есть одна большая проблема, которую я вижу с кодом:

Предположим, в вашем списке уже есть два разных элемента, и вы вставляете новый элемент. В своем коде вы проверяете, больше ли node, чем head, и, если это так, вставляете его сразу после, игнорируя остальные элементы в списке.

Вы код делаете что-то вроде этого. Есть некоторые недостающие детали, которые вы можете заполнить самостоятельно.

1. Если список пуст, задайте head = node, head->next = NULL, и все готово.

2. В противном случае, если node->value < head->value, установите node->next = head, head = node.

3. В противном случае, если node->value == head->value, head->count++;

4. В противном случае установите tmp = head. Пока tmp->next->value < node->value, установите tmp=tmp->next. (проверьте на нули!).

5. Если tmp->next == NULL, (т.е. вы достигли конца списка), тогда установите tmp->next = node, и все готово.

6. В противном случае, если tmp->next->value == node->value, (т.е. вы достигли узла с тем же значением) tmp->next->count++.

7. В противном случае, если node->next = tmp->next, tmp->next = node, и выйти

Answer 4

• Вы позаботились о случае, когда list изначально пуст. Вы следует также позаботиться о специальных случай, когда новый узел идет в начало списка. Если ваш список B->C->D и вы вставляете A.
• Хорошо установить node.next на null (если это еще не сделано). Так что если узел вставляется в конец, у нас есть null как следующий из последний узел.
• Вам нужно обновить темп для перемещения к следующему узлу, если нет вставки возможный. Итак, вам не хватает temp = temp.next;

Answer 5

Не видя полного кода, сложно выполнить отладку. Я думаю, проблема в том, что вы установили

 Node temp = head; 

перед циклом, но вам нужно переназначить temp при переходе от списка к текущему элементу. В этом случае вы продолжаете сравнивать с head.

Answer 6

Я думаю, что вы хотите использовать одну из Multiset реализаций из Google Collections.

Мультисеть работает аналогично набору, но допускает дубликаты (и считает их!). Посмотрите на TreeMultiset :

Мультимножество, которое поддерживает упорядочение его элементов, согласно либо их естественный порядок или явный компаратор.