проблема с реализацией связанного списка в java - PullRequest
Новая
       19

проблема с реализацией связанного списка в java

0 голосов
/ 08 марта 2020

Я пытался реализовать связанный список в java, используя следующий код: 

    class Linkedlist<T>{

    private node head, tail;

    public Linkedlist(){
        head = new node(null);
        tail = head;
    }

    public boolean insert(T value){
        if(head.getValue() == null){
            this.head.setValue(value);
            head.setNext(null);
            return true;
        }
        node insertNode = new node(value);
        tail.setNext(insertNode);
        tail = insertNode;
        return true;
    }
    public boolean insert(T value, int index)  {

        if ( sizeOfList() == index + 1 ) return false;
        node temp = this.head.getNext();
        node prvtmp = this.head;
        for (int i = 0; i <= index; i++) {
            temp = temp.getNext();
            prvtmp = temp;
            System.out.println("for loop");
        }
        node insertNode = new node(value);
        System.out.println("node created");
        prvtmp.setNext(insertNode);
        insertNode.setNext(temp);
        System.out.println("temps");
        return true;
    }
    public int sizeOfList(){

        int size = 0;
        node temp = this.head;
        while(temp.getNext() != null){
            temp = temp.getNext();
            size++;
        }
        return size;
    }
    public String[] rtrnList(){
        node temp = this.head;
        int listSize = sizeOfList();
        String[] resualt = new String[listSize + 1];
        for (int i = 0;i <= listSize;i++){
            resualt[i] = String.valueOf(temp.getValue());
            temp = temp.getNext();
        }
        return resualt;
    }
}

Узел класса: 

public class node<T> {

    private  T value;
    private node next;

    public node(T value){
        this.value = value;
        this.next = null;
    }
    public void setValue(T value) {
        this.value = value;
    }

    public void setNext(node next) {
        this.next = next;
    }

    public T getValue() {
        return value;
    }

    public node getNext() {
        return next;
    }


}

Когда я пытаюсь запустить метод insert с одним аргументом он работает нормально, но когда я запускаю его с двумя аргументами: 

import java.util.Arrays;
public class main {
    public static void main(String[] args){
        Linkedlist list = new Linkedlist();
        list.insert(2);
        list.insert(2);
        list.insert(2);
        list.insert(2);
        list.insert(2);
        list.insert(2);
        list.insert(11, 3);

        System.out.println(Arrays.toString(list.rtrnList()));
        System.out.println("finished");
    }
}

Программа не достигает строки, которая печатает закончено, но если мы удаляем строку: list.insert(11, 3); Тогда программа работает просто отлично.

вывод: 

for loop
for loop
for loop
for loop
node created
finish insert

Ответы [ 2 ]

1 голос
/ 08 марта 2020

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

public boolean insert(T value, int index)  {


    if(index > sizeOfList())
    {
        return false;
    }
    else if(index == sizeOfList())
    {
        if(insert(value))
            return true;
        else
            return false;
    }
    else
    {
        node previous = this.head;

        for (int i = 1; i <= index; i++) {
            if(i==index-1)
            {
                node newnode = new node(value);

                newnode.setNext(previous.getNext());
                previous.setNext(newnode);
                break;
            }
            previous = previous.getNext();

        }
    }

    return true;
}

Выход 

[2, 2, 11, 2, 2, 2, 2]
1 голос
/ 08 марта 2020

Проблемы находятся внутри for l oop вашего метода вставки (значение T, индекс int), когда вы обновляете значения prvtm и temp. В вашем коде вы сначала устанавливаете значение temp в temp.getnext () и, поскольку temp уже изменено, вы устанавливаете prvtmp в temp, создавая al oop, поэтому, когда вы пытаетесь напечатать список, он попадает в бесконечное число. oop при расчете размера списка.

Просто поместите строку prvtmp = temp перед temp = temp.getNext (), как в следующем фрагменте кода. Это решит проблему. 

public boolean insert(T value, int index)  { // 2 2 2 2 2 2

    if ( sizeOfList() == index + 1 ) return false;
    node temp = this.head.getNext();
    node prvtmp = this.head;
    for (int i = 0; i <= index; i++) {
        prvtmp = temp;
        temp = temp.getNext();
        System.out.println("for loop");
    }
    node insertNode = new node(value);
    System.out.println("node created");
    prvtmp.setNext(insertNode);
    insertNode.setNext(temp);
    System.out.println("temps");
    return true;
}

Также, если вы пытаетесь вставить в данный индекс, обновите условие для l oop с: 

i <= index to i < index - 1

Удачного кодирования!

...