在 java 中实现链表时遇到问题

Question

我尝试使用下面的代码在 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;
    }
}

Class节点：

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

Answer 1

当您更新 prvtm 和 temp 的值时，问题出在 insert(T value, int index) 方法的 for 循环内。在您的代码中，您首先将 temp 的值设置为 temp.getnext() 并且由于 temp 已经更改将 prvtmp 设置为 temp 创建一个循环，这就是为什么当您尝试打印列表时它会进入无限循环在计算列表的大小时。

只需将 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;
}

此外，如果您尝试在给定索引中插入，请更新 for 循环的条件：

i <= index to i < index - 1

编码愉快！

Answer 2

插入时会产生循环引用，您可以使用此代码实现上述目的

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]

在 java 中实现链表时遇到问题

trouble implementing a linked list in java

java

data-structures

singly-linked-list