Thread: Linked List

Hello,

I am trying to solve this problem but I don't really know where to start.
My task is to fill the empty methods in the class SimpleLinkedList

I started by trying to fill the method insert (the empty one) but I couldn't find how to fill it on the given index. I know that if I can if and else in order to insert the node either at the head or the tail of the list but since I need to insert it on the given index I do not know how to solve this.

I have tried to write a code in the insert method but it is not working properly. My indexes are wrong, when I type index 1 it writes the name on the first position instead of the second position and so on. Also I need it to show me an error if the index is larger than the list's size.

I need to fill the methods size, remove and toString as well but I haven't started yet because I don't understand where to start.

Thanks in advance for your advice and help.

 
import java.sql.SQLOutput;
import java.util.*;
 
/**
 * The class SimpleLinkedList is a linked list that includes nodes of objects.
 * The first node in the list includes no objects.
 */
 
public class SimpleLinkedList
{
    private ListNode header;
 
    public SimpleLinkedList( )
    {
        header = new ListNode( null );
    }
 
    /**
     Creates a new ListNode with a new object and adds it to the list.
     */
    public void insert(String theobj)
    {
        ListNode nynode = new ListNode(theobj);
 
        ListNode temp = header;
 
        while(temp.next != null)
        {
            temp = temp.next;
        }
 
        temp.next = nynode;
    }
 
 
    /*
    Removes the node that includes the respective object.
      */
    public void remove(String theobj)
    {
        ListNode node = header;
 
        while(node.next != null)
        {
            if(node.next.element.equals(theobj))
            {
                node.next = node.next.next;
                break;
            }
 
            node = node.next;
        }
    }
 
    /**
     Prints the content of the list.
     */
    public void print()
    {
        ListNode node = header.next;
        while(node != null)
        {
            System.out.println(node.element);
            node = node.next;
        }
    }
 
    public void insert2(String theobj)
    {
        ListNode nynode = new ListNode(theobj, header.next);
        header.next = nynode;
    }
 
    // This method has to be filled.
    // Adds an object at the given index (position). The index must not be negative or bigger than the list's size.
    public void insert(String obj, int index)
    {
        ListNode node = new ListNode(obj);
 
        if (header == null)
        {
            if (index != 0)
            {
                return;
            }
 
            else
            {
                header = node;
            }
        }
 
        if (header != null && index == 0)
        {
            node.next = header;
            header = node;
            return;
        }
 
        ListNode current = header;
        ListNode previous = null;
 
        int i = 0;
 
        while (i < index)
        {
            previous = current;
            current = current.next;
 
            if (current == null)
            {
                break;
            }
 
            i++;
        }
 
        node.next = current;
        previous.next = node;
    }
 
    // Returns and removes the object from the given index in the list. 
    public String remove(int index)
    {
        // temporary return
        return null;
    }
 
//Returns the size of the list. 
//Task: Add a variable in the class and update it when needed.
 
    public int size()
    {
        // temporary return
 
 
        return 0;
    }
 
    public String toString()
    {
 
 
        return null;
    }
 
    public static void main (String[] cmdLn)
    {
        SimpleLinkedList klassLista = new SimpleLinkedList();
        klassLista.insert("Olle");
        klassLista.insert2("Nina");
        klassLista.insert("Mario");
        //klassLista.print();
        //klassLista.remove("Nina");
        //klassLista.print();
        klassLista.insert("Stef", 0);
        klassLista.print();
    }
}

This is the ListNode class that I am using:

 
import java.util.*;
 
class ListNode
{
    public String element;
    public ListNode next;
 
    // Constructors
 
    public ListNode( String theElement )
    {
        this( theElement, null );
    }
 
    public ListNode( String theElement, ListNode n )
    {
        element = theElement;
        next    = n;
    }
 
    public static void main (String [] a)
    {
 
        ListNode n1=new ListNode("Nina");
 
        ListNode n2=new ListNode("Kalle",n1);
        ListNode n3=new ListNode("Olle",n2);
        ListNode n4=new ListNode("Mio",n3);
 
        ListNode n=n4;
        while(n!=null)
        {
            System.out.println(n.element);
            n=n.next;
        }
    }
}

I understand, the insert method is supposed to add an item on a specific index.

I have written this code:

public void insert(String obj, int index) {
ListNode node = new ListNode(obj);
 
        if (header == null)
        {
            if (index != 0)
            {
                return;
            }
 
            else
            {
                header = node;
            }
        }
 
        if (header != null && index == 0)
        {
            node.next = header;
            header = node;
            return;
        }
 
        ListNode current = header;
        ListNode previous = null;
 
        int i = 0;
 
        while (i < index)
        {
            previous = current;
            current = current.next;
 
            if (current == null)
            {
                break;
            }
 
            i++;
        }
 
        node.next = current;
        previous.next = node;
}

But my code is somewhat wrong. When I add an item and then I want it to be on the index 0 the output is "null" and when I do index 1 it puts it on the beginning of the list.
But index 0 is supposed to be the beginning of the list and index 1 is supposed to be the second item in the list not the first.

The tasks says to only fill the methods insert(String obj, int index), remove(int index), size() and toString(). In other words the last 4 methods.
And I wrote the code that I posted in the reply on the insert(String obj, int index) and as I said above the indexes are not correct. I am a beginner so I don't understand all of the above code but I am only required to fill the last 4 methods, as u can see the last 3 methods are still empty as I did not write in them anything yet.

This is the method I want to work on. I have 2 problems with it.
1st problem: The indexes are not correct, index 0 gives output null and index 1 adds the item on the first position on the list instead of second.
2nd problem: It doesn't give me error when the index is larger than the list's size.

public void insert(String obj, int index)
    {
        ListNode node = new ListNode(obj);
 
        if (header == null)
        {
            if (index != 0)
            {
                return;
            }
 
            else
            {
                header = node;
            }
        }
 
        if (header != null && index == 0)
        {
            node.next = header;
            header = node;
            return;
        }
 
        ListNode current = header;
        ListNode previous = null;
 
        int i = 0;
 
        while (i < index)
        {
            previous = current;
            current = current.next;
 
            if (current == null)
            {
                break;
            }
 
            i++;
        }
 
        node.next = current;
        previous.next = node;
    }

Thanks for the help, I will apply the second and the third code that you have provided but unfortunately I am not supposed to change anything in the ListNode class.
My task is to only fill the last 4 methods in the SimpleLinkedList class.

Then in the testing code in main() add this statement to show the current list contents:

        System.out.println("after ... list="+klassLista);

For example:



--- Update ---


I am confused about that statement.
The insert method should not GIVE anything. It should change the list.[/QUOTE]

I dont really understand what you mean by System.out.println("after ... list="+klassLista);

By index 0 I mean that in the main() if I add klassLista.insert("Steve", 0); then it will not add Steve to the beginning of the list but instead it will print out "null"
But if I add this instead klassLista.insert("Steve", 1); it will then add Steve to the beginning of the list instead of adding it to the second position of the list.

I have changed my insert(String obj, int index) method
The index are working fine now, when I add a new name to index 1 it is added on the second position of the list so all is correct.
Now the only problem is that when I choose to add a name to index 0 I get an error
Here is the insert method.

public void insert(String obj, int index)
    {
        ListNode node = new ListNode(obj);
 
        ListNode current = header;
        ListNode previous = null;
 
        if (index == 0)
        {
            node.next = header;
            header = node;
        }
 
        int i = 0;
 
        while (i < index)
        {
            previous = current;
            current = current.next;
            i++;
        }
 
        ListNode n = new ListNode(obj, current.next);
        previous.next.next = n;
    }

Also here is my print method.

 public void print()
    {
        ListNode node = header.next;
        while(node != null)
        {
            System.out.println(node.element);
            node = node.next;
        }
    }

I am not meant to change anything in that method.

This is the error message:
Exception in thread "main" java.lang.NullPointerException
at SimpleLinkedList.insert(SimpleLinkedList.java:99)
at SimpleLinkedList.main(SimpleLinkedList.java:135)

Process finished with exit code 1

and here is my complete code

import java.sql.SQLOutput;
import java.util.*;
 
/**
 * Klassen SimpleLinkedList är en länkad lista som innehåller noder av objekt.
 * Första noden i listan innehåller inget objekt.
 */
 
public class SimpleLinkedList
{
    private ListNode header;
 
    public SimpleLinkedList( )
    {
        header = new ListNode( null );
    }
 
    /**
     Skapar en ny ListNode  med ett nytt objekt och lägger den i listan
     */
    public void insert(String theobj)
    {
        ListNode nynode = new ListNode(theobj);
 
        ListNode temp = header;
 
        while(temp.next != null)
        {
            temp = temp.next;
        }
 
        temp.next = nynode;
    }
 
 
    /*
    Ta bort noden som innehåller respektive objekt
      */
    public void remove(String theobj)
    {
        ListNode node = header;
 
        while(node.next != null)
        {
            if(node.next.element.equals(theobj))
            {
                node.next = node.next.next;
                break;
            }
 
            node = node.next;
        }
    }
 
    /**
     Skriver ut innehållet i listan
     */
    public void print()
    {
        ListNode node = header.next;
        while(node != null)
        {
            System.out.println(node.element);
            node = node.next;
        }
    }
 
    public void insert2(String theobj)
    {
        ListNode nynode = new ListNode(theobj, header.next);
        header.next = nynode;
    }
 
    // Detta skall du göra
    // läger objekt på plats index. Index får inte vara negativ eller större än listans storlek
    public void insert(String obj, int index)
    {
        ListNode node = new ListNode(obj);
 
        ListNode current = header;
        ListNode previous = null;
 
        if (index == 0)
        {
            node.next = header;
            header = node;
        }
 
        int i = 0;
 
        while (i < index)
        {
            previous = current;
            current = current.next;
            i++;
        }
 
        ListNode n = new ListNode(obj, current.next);
        previous.next.next = n;
    }
 
    // Returnerar och tar bort ett objkt från lista
    public String remove(int index)
    {
        return null;
    }
 
    //returnerar storleken på listan. Lägg till i klasssen  en variabel för detta
    // uppdatera variabeln när det är fallet
 
    public int size()
    {
        return 0;
    }
 
    public String toString()
    {
        return header.toString();
    }
 
    public static void main (String[] cmdLn)
    {
        SimpleLinkedList klassLista = new SimpleLinkedList();
        klassLista.insert("Olle");
        klassLista.insert2("Nina");
        klassLista.insert("Mario");
        //klassLista.print();
        //klassLista.remove("Nina");
        //klassLista.print();
        klassLista.insert("Osama", 0);
        klassLista.print();
    }
}