Связанный вручную список - вставить перед методом

Question

Это часть упражнения, которое мы выполнили в классе, я просто не могу понять ...

Необходимый метод - это метод insertBefore (объектные данные), в котором, когда пользователь выбирает этот метод, онпредложит ввести данные для вставки перед справочными данными (введенными пользователем)

Пример того, как он должен выполняться:

// assuming linked list has data 1,2,3 inserted already

Choose Method:
1)Insert Before

choice: 1 // input by user


====Insert Before====
Enter Reference data: 2 // input by user
Enter Data to be inserted: 5 // input by user

supposed output: 1,5,2,3

Вот мой код для этого упражнения: (Он находится внутри класса LinkList с переменными

protected int end;
protected Node start;

и внутреннего класса с именем Node)

private class Node
{
    public char data;
    public Node next;
    public Node(char data)
    {
        this.data = data;
    }
}


public void insertBef(char ref,char data)
{
    Node temp = new Node(data);
    Node current = start;

    if(end!=0)
    {
        for(int i = 1; i<end; i++)
        {
            if(current == start)
            {
                Node newNode = start;
                newNode.data = current.data;
                newNode.next = temp;
                current = current.next;
            }
            else if(current.data == ref)
            {
                Node newNode = current;
                newNode.data = current.data;
                newNode.next = temp;
                current = current.next;
            }
        }
        end++;

    }
    else
    {
        temp.next = start;
        start = temp;
    }
    end++;
}

Но когда я запускаю свой код, он выдает 3,5, а не 1,5,2,3!Я не могу понять, где я мог ошибиться ...

Может кто-нибудь сказать мне, где ошибка, и объяснить, как я могу ее исправить?

Я понимаю, что можночтобы вставить перед ссылочным значением, вы должны:

• Создать новый узел для новых данных
• Создать временный узел для ссылочного значения и ссылки
• Сделатьссылка данных до того, как эталонное значение указывает на новый узел и заставляет ссылку нового узла указывать на временный узел

Я просто не могу понять, как реализовать это в Javaкод ...

Answer 1

При программировании, если это кажется сложным, вы, вероятно, делаете это неправильно ...

Вам нужна только одна строка кода для выполнения задачи!

list.add(list.indexOf(reference), data);

Вот эта строка, завернутая как метод insertBefore:

public static void insertBefore(List<Integer> list, int reference, int data) {
    list.add(list.indexOf(reference), data);
}

Вот тест, использующий ваш пример:

public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>(Arrays.asList(1, 2, 3));
    insertBefore(list, 2, 5);
    System.out.println(list);
}

Вывод:

[1, 5, 2, 3]

Примечание. Этот код вызовет исключение, если элемент ссылки не найден.
Я оставлю вам право закрыть эту дыру.

Answer 2

Перво-наперво: for петли, как правило, плохая идея со связанными списками.while петли намного лучше;Вы можете сделать что-то вроде while(next != null).

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

Ваш цикл for слишком сложен и, кажется, не имеет большого смысла.Вот как должен выглядеть ваш цикл:

1. Получить головной узел
2. Начать цикл по списку, проверяя значение следующего узла по ходу
3. Как только вы обнаружите, чтозначение следующего узла - это то, что вы ищете, создавая новый узел.
4. Вставьте новый узел, установив его значение Next равным значению Next текущего узла, затем установите следующее значение текущего узла равнымбыть новым узлом.
5. Возврат из функции.

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

Теперь я не уверен, какой у вас start.Содержит ли оно значение или это выделенный головной узел?Я бы проголосовал за выделенный головной узел, с которым мне обычно легче работать, потому что вам не нужно добавлять код для особого случая, когда число должно стоять перед заголовком.Таким образом, ваш начальный узел должен быть «пустым»;значение, которое он содержит, игнорируется, единственное, для чего он используется, - это сохранить указатель на первый законный узел в списке.Если вы сделаете это, метод insertBef станет невероятно простым.ПРИМЕЧАНИЕ: непроверенный код для подражания.

public void insertBef(char ref, char data)
{
    Node current = start;

    while( current.next != null )
    {
        if( current.next.value == ref )
        {
            Node n = new Node(data);
            n.next = current.next;
            current.next = n;
            return;
        }

        current = current.next;
    }
}

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