Вставить в двойной список ссылок

Question

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

Это мой приведенный ниже код.

theList.insertReverseLexicographicalOrder("B");
theList.insertReverseLexicographicalOrder("A");
theList.insertReverseLexicographicalOrder("H");
theList.insertReverseLexicographicalOrder("D");
theList.insertReverseLexicographicalOrder("E");

public void insertReverseLexicographicalOrder(String dd) {
    Link newLink = new Link(dd);
    if (isEmpty()){
        last = newLink;
    }           
        first.previous = newLink;
    }
    newLink.next = first;
    first = newLink;
}

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

Answer 1

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

Z, Y, X, W, L, K, A

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

Answer 2

Вам нужно будет просмотреть список, сравнивающий каждый из элементов.Остановитесь, когда найдете элемент, который идет после элемента, который вы пытаетесь вставить.Я предлагаю вам реализовать метод CompareTo в классе вашего узла: http://www.javapractices.com/topic/TopicAction.do?Id=10 и использовать его для сравнения

Удачи.

Answer 3

Как вставить узел в связанный список:

1. Если список пуст, новый узел станет первым, а если мы будем отслеживать это, также последним
2. В противном случае найдите позицию, куда вставить, есть три возможности:
   a) новый узел должен быть вставлен перед первым
   b) новый узел должен быть вставлен после последнего
   c) новый узел должен быть вставлен между двумя существующими узлами
3. Обновите соответствующие ссылки, которые могут быть полями first, last и некоторыми next и previous, в зависимости от того, где он долженбыть вставленным

if (first == null) {
    // the list is empty so far
} else

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

if (newLink.iData.compareTo(first.iData) > 0) {
    // put newLink before first
} else {

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

    Link focus = first; // focus first node
    while(focus.next != null && newLink.iData.compareTo(focus.next.iData) < 0) {
        focus = focus.next;
    }
    // now you have to insert the new value behind focus, left as exercise
    if (focus.next == null) {
        // newLink becomes the last node in the list
    } else {
       // newLink has to be inserted between focus and focus.next
    }
}

Затем вставьте.Остерегайтесь краевых чехлов, вставка спереди и конец немного отличаются.