Проверка кода для связанного списка add (i, x) Метод

Question

В настоящее время я пытаюсь освежить в памяти реализацию ADT, в частности реализацию связанного списка (для этого я использую Java 5).

У меня два вопроса:

(1) Является ли эта реализация, написанная для add (i, x), корректной и эффективной?

public void add(int i, Object x) {

    // Possible Cases:
    //
    //     1. The list is non-empty, but the requested index is out of
    //        range (it must be from 0 to size(), inclusive)
    //
    //     2. The list itself is empty, which will only work if i = 0
    //
    // This implementation of add(i, x) relies on finding the node just before
    // the requested index i.

    // These will be used to traverse the list
    Node currentNode = head;
    int indexCounter = 0;

    // This will be used to mark the node before the requested index node
    int targetIndex = i - 1;

    // This is the new node to be inserted in the list
    Node newNode = new Node(x);

    if (currentNode != null) {

        while (indexCounter < targetIndex && currentNode.getNext() != null) {

            indexCounter++;
            currentNode = currentNode.getNext();
        }

        if (indexCounter == targetIndex) {

            newNode.setNext(currentNode.getNext());
            currentNode.setNext(newNode);

        } else if (i == 0) {

            newNode.setNext(head);
            head = newNode;
        }

    } else if (i == 0) {

        head = newNode;
    }     
}

(2) Я нашел этот метод очень сложным для реализации. Если честно, это заняло у меня несколько дней. Это трудно признать, потому что я люблю программирование и считаю себя на среднем уровне в нескольких языках и платформах. Я программирую с 13 лет (Applesoft BASIC на Apple IIc!) И получил степень по CS. В настоящее время я работаю тестером программного обеспечения и планирую стать разработчиком в какой-то момент. Итак, вторая часть моего вопроса: я обманываю себя, что это тот тип работы, в котором я бы преуспел, или почти все находят проблему такого рода сложной? Что-то подсказывает мне, что даже опытным разработчикам, столкнувшимся с реализацией этого метода, будет сложно.

Спасибо за ваши отзывы и советы по второй части.

Answer 1

Я думаю, что это хорошее начало ... Несколько предложений:

• Я думаю, что ваш currentNode == нулевые случаи должны быть учтены в начале, а затем возвращены.Мне не нравится, когда все находится внутри "if (currentNode! = Null)"
• Вы должны где-то отслеживать размер вашего связанного списка, чтобы вы могли легко проверить, если i> list_size
• Я бы не стал переименовывать "i-1" в targetIndex
• Не создавайте новый узел, пока вам не понадобится
• Писать модульные тесты, тогда вы сможете легко изменить ситуациюи знайте, что ваша реализация все еще работает.
• Не просто игнорируйте недопустимые аргументы.Если индекс i <0 или> size, бросить исключение IllegalArgumentException или IndexOutOfBoundsException (спасибо @JB Nizet)

Answer 2

Эта реализация неэффективна, но это отчасти потому, что операция add (i, x) неэффективна в обычном связанном списке. Связанные списки не предназначены для произвольного доступа. Я думаю, что если вы создали хеш-таблицу или что-то еще, вы могли бы создать более эффективный индекс в списке. Например, рассмотрим карту. Затем ваша подпрограмма вставки (очевидно, есть особый случай для i = 0) map.ContainsKey (i-1) map.get (i-1), и вы сразу же получите предыдущий индекс. И если я! = 0, и у вас нет ключа для этого индекса, то вы сразу же знаете об ошибке. Карта в теории O (1), если не слишком много коллизий, так что это гораздо более эффективно (но за счет некоторого дискового пространства), чем повторять список каждый раз. Опять же, это действительно зависит, потому что чистый связанный список не очень эффективен для добавления (i, x).

Мне не особенно нравится этот метод, потому что он молча терпит неудачу, если вы говорите add (32, x) и в списке есть только 15 элементов. Он должен по крайней мере выдать исключение, вернуть false или что-то еще, чтобы указать, что вставка не удалась.

Также вы можете объединить два особых случая. Предполагая, что newNode.setNext (NULL) работает, вам просто нужно выполнить одну проверку для i == 0, а затем вы можете выполнить newNode.setNext (head), head = newNode, потому что список пустой или нет, это работает. Если список пуст, вы устанавливаете следующий указатель на NULL. Это, по крайней мере, устраняет повторяющийся код.

Взятие недели действительно кажется немного большим, но у некоторых людей возникают большие проблемы с тем, чтобы обернуть голову вокруг указателей (ну, ссылки на классы в javaspeak ....). Тот факт, что у вас есть что-то для работы, является отличным шагом в правильном направлении.

Answer 3

Я предлагаю вам начать с написания некоторых модульных тестов. В частности, попробуйте добавить узел за пределы списка и посмотрите, что произойдет. ;)

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

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