trouble implementing a linked list in java

Question

I tried to implement a linked list in java using the code below:

    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 node:

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;
    }


}

When I try to run the insert method with one argument it works fine, but when I run it with two arguments:

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");
    }
}

The program doesn't reach the line that prints finished, but if we delete the line: list.insert(11, 3); Then the program works just fine.

output:

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

your insert method, as declared, only accepts a single argument, if you wanted to handle multiple arguments, you would need to other rewrite this method, or overload it with a different signature that handles multiple arguments. — solid.py
– solid.py, Commented Mar 8, 2020 at 11:34
It would be helpful, if you can also post the output of your program. You have a lot of System.out.println() which could help to track down the bug. — Uwe Plonus
– Uwe Plonus, Commented Mar 8, 2020 at 12:04

Md Golam Rahman Tushar · Accepted Answer · 2020-03-08 12:48:48Z

The problems is inside the for loop of your insert(T value, int index) method when you are updating the value of prvtm and temp. In your code you are first setting the value of temp to temp.getnext() and as the temp is already changed setting prvtmp to temp creating a loop which is why when you are trying to print the list it's getting into an infinite loop while calculating the size of the list.

Just put the prvtmp = temp line before temp = temp.getNext() like following code snippet. This will solve the problem.

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;
}

Also if you are trying to insert in the given index update the condition of the for loop from:

i <= index to i < index - 1

Happy coding!

Adnan · Accepted Answer · 2020-03-08 13:00:48Z

1

while inserting there is a cyclic refrence made , you can use this code for above purpose

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;
}

Output

[2, 2, 11, 2, 2, 2, 2]

answered Mar 8, 2020 at 13:00

Adnan

4963 silver badges9 bronze badges

1 Comment

sinammd Over a year ago

I admire your coding skills. that's helped me so much

Collectives™ on Stack Overflow

trouble implementing a linked list in java

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related