Это эффективный способ удаления дубликатов из связанного списка?

Question

Я пишу функцию, которая берет заголовок связанного списка, удаляет все дубликаты и возвращает новый заголовок.Я проверил это, но я хочу посмотреть, можете ли вы поймать какие-либо ошибки или улучшить их.

removeDuplicates(Node head)
    if(head == null) throw new RuntimeException("Invalid linked list");

    Node cur = head.next;
    while(cur != null) {
        if(head.data == cur.data) {
            head = head.next;
        } else {
            Node runner = head;
            while(runner.next != cur) {
                if(runner.next.data == cur.data) {
                    runner.next = runner.next.next;
                    break;
                }
                runner = runner.next;
            }
        cur = cur.next;
    } 
    return head;
}

Answer 1

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

Для настольных приложений я обычно предпочитаю использовать больше оперативной памяти и выигрывать с некоторой скоростью. Так что я бы сделал что-то вроде этого.

removeDuplicates(Node head) {
    if (head == null) {
        throw new RuntimeException("Invalid List");
    }

    Node current = head;
    Node prev = null;
    Set<T> data = new HashSet<T>(); // where T is the type of your data and assuming it implements the necessary methods to be added to a Set properly.
    while (current != null) {
        if (!data.contains(current.data)) {
            data.add(current.data);
            prev = current;
            current = current.next;
        } else {
            if (prev != null) {
                prev.next = current.next;
                current = current.next;
            }
        }
    }
}

Это должно выполняться за O (n) время.

EDIT

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

Answer 2

Для эффективного удаления дубликатов вы должны держаться подальше от связанного списка: используйте вместо этого java.util.PriorityQueue; это отсортированная коллекция, для которой вы можете определить критерии сортировки. Если вы всегда вставляете в отсортированную коллекцию, удаление дубликатов может быть выполнено либо сразу после вставки, либо по требованию с одним O (n) -проходом.

Answer 3

Я не проверял ваш код на наличие ошибок, но у меня есть предложение по его улучшению.Выделите Hashtable или HashMap, который отображает Node в Boolean.По мере обработки каждого элемента, если он не является ключом в хэше, добавьте его (со значением Boolean.TRUE).Если он существует в качестве ключа, то он уже появился в списке, и вы можете просто удалить его.

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

Кроме того, вы можете подумать, имеет ли смысл использовать тест equals() вместо == для вашего приложения.

Answer 4

Помимо использования элементов списка для создания хэш-карты и тестирования каждого элемента с использованием его в качестве ключа, что было бы желательно только для большого числа элементов, где large зависит от ресурсы, необходимые для создания хэш-карты, последовательное сканирование списка является практичным вариантом, но есть и другие, которые будут быстрее. См. Пользовательский ответ 138170 здесь - сортировка слиянием на месте - это операция O (n log (n)) , которая не использует лишний пробел, тогда как решение использует отдельный массив будет работать в O (n) времени. На практике вам может потребоваться профилировать код и установить разумное значение n, , где n - количество элементов в списке, после чего будет использовано решение, выделяющее память. вместо того, который не.

Редактировать: Если эффективность действительно важна, я бы предложил не использовать связанный список (в основном для сохранения когерентности кэша) и, возможно, использовать JNI и реализовывать функцию изначально; данные также должны быть предоставлены в собственно выделенном буфере.