Вставка узла в середину связанного списка, а также случайная вставка нулевого узла

Я работаю над программой, которая не использует встроенный в Java класс Linked List; Я строю его с нуля. Я преуспел во всем, кроме написания метода, который вставляет узел в определенную позицию связанного списка.

У меня есть метод, который устанавливает определенный узел как «текущий» узел. Так, например, у меня есть связанный список, который выглядит так: кошки --> собаки --> делать --> хорошо --> питомцы, а "текущий" равен 2; это означает, что «текущий» узел — это «собаки».

Отсюда, скажем, я хочу вставить новый узел в позицию «текущего», информационное поле которого читается как и. Если все сделано правильно, окончательный связанный список будет таким: кошки --> и --> собаки --> делают --> хорошо --> домашние животные; «и» заменит «собаки» на позиции 2.

Итак, вот моя проблема: мой метод работает для вставки нового узла во вторую позицию, но что-то идет не так с привязкой вновь созданного узла к уже существующим узлам. Я не только вставляю свой новый узел в список, но также вставляю узел без информации перед «собаками». Пока мой код работает, вывод выглядит следующим образом: кошки --> и --> (пусто) --> собаки -- > заводить --> хорошо --> домашних животных.

Я на 99,9% уверен, что проблема заключается в (if current != null) части кода, я просто не могу понять, как это исправить.

Любые мысли о том, почему я вставляю пустой узел в дополнение к узлу, который я действительно хочу добавить?

public void insert () {

    System.out.println("Please enter the text you wish to insert, or type \"end\" if you are done inserting.");
    String theString;
    theString = console.nextLine();

    while (!theString.equals("end")){
        newNode = new Node ();
        newNode.info = theString;
        newNode.next = null;

        if (first == null){
            first = newNode;
            last = newNode;
        } else if (current != null){
            Node p = new Node (current.info, current.next);
            current.info = newNode.info;
            current.next = p;
        }
        else {
            last.next = newNode;
            last = newNode;
        }

        System.out.println("Please enter the text you wish to insert, or type \"end\" if you are done inserting.");
        theString = console.nextLine();
    }   
}

ИЗМЕНИТЬ

Вся программа довольно длинная, но вот метод «setLine», который устанавливает текущий равным любой позиции, в которую пользователь хочет вставить свой узел. Он принимает параметр «int line», который получается через приглашение пользователя.

public Node setLine(int line) {

    int index = 0;
    current = first;
    while (index < line) {
        previous = current;
        current = current.next;
        index++;
    }
    return current;
}

java singly-linked-list
person JayneCobb's_HatDesigner    schedule 07.11.2012    source источник
comment
С такими вещами вам просто нужно работать шаг за шагом, как правило, с большим количеством вызовов System.out.println. Это действительно довольно распространенная проблема, но вам нужно решить ее самостоятельно.   -  person Hot Licks    schedule 07.11.2012
comment
Обратите внимание, что вы должны с подозрением относиться к случаю, когда вы создаете второй новый узел — вам всегда нужен только один для любой вставки.   -  person Hot Licks    schedule 07.11.2012
comment
Что такое console, java.util.Scanner?   -  person Daniel Fischer    schedule 07.11.2012
comment
Пожалуйста, опубликуйте остальную часть кода.   -  person Zzz    schedule 07.11.2012
comment
Да, было бы полезно, если бы мы имели представление о том, как устанавливается ток.   -  person Hot Licks    schedule 07.11.2012
comment
И обратите внимание, что если текущий когда-либо == последний, последний не будет обновляться.   -  person Hot Licks    schedule 07.11.2012
comment
Вместо того, чтобы угадывать/проверять вывод, почему бы не настроить JunitTestSuite? Это позволит вам программно проверять вещи и выполнять разработку/регрессионное тестирование через тестирование. Это очень просто, если вы используете eclipse.   -  person Blaskovicz    schedule 07.11.2012
comment
@Hot Licks: у меня было ощущение, что проблема заключается в дополнительном конструкторе, но я подумал, что вам нужен способ сохранить значение узла, которое находится перед позицией, в которую вам нужно вставить, поскольку вам придется установить ссылку этого узла на узел, который вы вставляете. Это односвязный список, а не двусвязный, поэтому нет ссылки на предыдущий Node. Есть ли способ временно сохранить предыдущий узел, не создавая еще один ненужный узел?   -  person JayneCobb's_HatDesigner    schedule 07.11.2012
comment
@DanielFischer: да, консоль - это java.util.Scanner.   -  person JayneCobb's_HatDesigner    schedule 07.11.2012
comment
@JayneCobb's_HatDesigner Вы можете реализовать свой односвязный список с указателем на предыдущий вместо нулевого, проверьте мой ответ.   -  person Zzz    schedule 07.11.2012
comment
Ваш узел имеет только два значения. Вы можете хранить эти значения в обычных локальных переменных — для этого не нужно создавать дополнительный узел.   -  person Hot Licks    schedule 07.11.2012

Ответы (2)


arrow_upward
1
arrow_downward

Вот код, который правильно вставляет узел. Это должно быть хорошей отправной точкой, удачи (вы можете прочитать больше здесь: http://www.algolist.net/Data_structures/Singly-linked_list/Insertion).

public class SinglyLinkedList {

      public void addLast(SinglyLinkedListNode newNode) {    
            if (newNode == null)    
                  return;    
            else {    
                  newNode.next = null;    
                  if (head == null) {    
                        head = newNode;    
                        tail = newNode;    
                  } else {    
                        tail.next = newNode;    
                        tail = newNode;    
                  }    
            }    
      }

      public void addFirst(SinglyLinkedListNode newNode) {    
            if (newNode == null)    
                  return;    
            else {    
                  if (head == null) {    
                        newNode.next = null;    
                        head = newNode;    
                        tail = newNode;    
                  } else {    
                        newNode.next = head;    
                        head = newNode;    
                  }    
            }    
      }

      public void insertAfter(SinglyLinkedListNode previous,    
                  SinglyLinkedListNode newNode) {    
            if (newNode == null)    
                  return;    
            else {    
                  if (previous == null)    
                        addFirst(newNode);    
                  else if (previous == tail)   
                        addLast(newNode);    
                  else {    
                        SinglyLinkedListNode next = previous.next;    
                        previous.next = newNode;    
                        newNode.next = next;    
                  }    
            }    
      }    
}
person Zzz    schedule 07.11.2012
comment
Почему newNode когда-либо будет нулевым? И почему бы вам не бросить NPE вместо того, чтобы просто игнорировать его? - person user207421; 20.08.2017

arrow_upward
0
arrow_downward

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

public boolean insertInMiddle(int index, int data){

    boolean isInserted = false;

    Node node = new Node(data);
    Node temp = head;
    int i=0;
    if(index >= 0 && index <= size()){
        isInserted = true;
        if(index == 0){
            if(head !=null){
                node.nextNode = head;
                head.prevNode = node;
                head = node;
            }else{
                head = node;
                tail=node;
            }
        }else{
            while(i<index){
                temp = temp.nextNode;
                i++;
            }               
            if(temp == null){
                node.nextNode = temp;
                node.prevNode = tail;
                node.prevNode.nextNode = node;
                tail=node;
            }else{
                node.nextNode = temp;
                node.prevNode = temp.prevNode;
                temp.prevNode = node;
                node.prevNode.nextNode = node;
            }
        }
    }       
    return isInserted;
}

//Method to get the size
public int size(){
    int size = 0;

    Node node = head;
    if(node !=null){
        while (node !=null){
            size++;
            node = node.nextNode;
        }
    }

    return size;
}
person Venky    schedule 27.07.2016
comment
Не то, что просили. - person user207421; 20.08.2017