Recursively Add Node to Linked List at Specific Index

Question

I am writing a recursive function that will add an item to the list given an index by recursively iterating to the index and then adding the item. The function should take in 2 parameters (String value and integer index) and also check that the index is valid. Here is what I have so far which does not check for validity and only works when passing in just a String value.

Test Bench (Main)

public class TestBench {

public static void main(String[] args) {
    RecLinkedList list = new RecLinkedList();
    list.add("A");
    list.add("B");
    list.add("D");
    list.add("C", 2);
    list.add("E", 4);
    list.add("G", 6); //this should be invalid

    System.out.println( list );
    System.out.println( list.remove( 1 ).getValue() );
    System.out.println( list.remove("D").getValue() );
    System.out.println( list.remove("G").getValue() );
    System.out.println( list.size() );
    System.out.println( list );
}

Linked List Class

public class RecLinkedList {
private Node first;

public RecLinkedList(){
    first = null;
}
public boolean isEmpty() {
    return first == null;
}
public void add( String s){
    first = add( s, first);
}
private Node add( String s, Node list){
    if( list == null ){
        return new Node(s);
    }else{
        list.setNext( add( s, list.getNext() ) );
    return list;
    }
}
public String toString() {
    return helperString(first);
}
private String helperString(Node list) {
    if (list.getNext() != null) {
        return list.getValue() + "," + helperString(list.getNext());
    }
    else {
        return (String) list.getValue();   
    }
}

What I need help on is would I need to make another add function that takes in both parameters(String and int values) or if I can modify what I have? Also, as far as checking if the index is valid, I am not really sure how to check.

user3248346 · Accepted Answer · 2015-04-09 09:20:46Z

It would be best to write another add method with arguments String and int as it is different behaviour compared to the other add function. If you look at the Java API for many classes, method names are overloaded. So this is good practice.

To determine if the index is valid, you first need to declare a field which holds the current size of your linked list. Every time you add or remove an element, this counter is updated. When you call your new add method, you would first do a check to see if the index where you want to insert the new element is either below zero or greater than the size of the linked list. If it is below zero then this is not a valid index. If it is greater than the size of the list then this does not make sense and so you could either reject it or more dubiously add the element to end of the list.

Timo Hanisch · Accepted Answer · 2015-04-09 09:34:02Z

1

Regarding the valid index you could add a size field counting existing Nodes.

public class RecLinkedList {
    private int size = 0;

    //...
    private Node add( String s, Node list){
        if( list == null ){
            this.size += 1;
            return new Node(s);
        }else{
            list.setNext( add( s, list.getNext() ) );
            return list;
        }
    }
    //...
}

Then while adding a new Node with a method public void add(String value, int index) you could check if index is greater than the current size or less than zero.

To add the Node at the correct position just count the number of Nodes you've allready visited and when the correct position is reached add the Node.

edited Apr 9, 2015 at 9:34

answered Apr 9, 2015 at 9:23

Timo Hanisch

2241 silver badge7 bronze badges

2 Comments

JCCS Over a year ago

Ok, I created new add method public void add(String value, int index) and I use if statement if(index < 0 || index > size) what would go inside this if statement and what would be the else.

Timo Hanisch Over a year ago

You could throw an exception indicating the index out of range. In the else statement you have to add the string to your list :)

Collectives™ on Stack Overflow

Recursively Add Node to Linked List at Specific Index

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related