Java - Recursive Linked List implementation

Question

I have fully implemented a singly Linked List (code below), however, the assignment specifically requests that it be implemented using recursion. I've been attempting to translate the while loops that I wrote into recursive calls, but Have gotten stuck and could use some help. My most recent attempts at the recursion are included in the code, but have been commented out.Thanks in advance for your help.

public class AddressList
{
public Record firstLink ;
public String name, tel, email, addr, state, dob; 
AddressList()
{
    firstLink = null;
}

public boolean isEmpty()
{
    return(firstLink == null);
}

public void addToFront(Record record)
{
    if(firstLink == null)
    {
        firstLink = new Record(record.getName(), record.getTel(), record.getEmail(), record.getAddr(),
            record.getState(), record.getDob());
    }
    else
    {
        Record newRecord = new Record(record.getName(), record.getTel(), record.getEmail(), record.getAddr(),
                record.getState(), record.getDob());
        newRecord.setNext(firstLink);
        firstLink = newRecord;
    }
}

public void addToBack(Record record)
{
    if(firstLink == null)
    {
        firstLink = new Record(record.getName(), record.getTel(), record.getEmail(), record.getAddr(),
            record.getState(), record.getDob());
    }
    else 
    {
        Record newRecord = new Record(record.getName(), record.getTel(), record.getEmail(), record.getAddr(),
                record.getState(), record.getDob());
        Record currentRecord = firstLink;
        while(currentRecord.getNext() != null)
        {
            currentRecord = currentRecord.getNext();
        }
        currentRecord.setNext(newRecord);
    }
    /*
    if(firstLink == null)
    {
    firstLink = new Record(record.getName(), record.getTel(), record.getEmail(), record.getAddr(),
    record.getState(), record.getDob());
    }
    else if (firstLink.getNext() == null)
    {
    firstLink.setNext(new Record(record.getName(), record.getTel(), record.getEmail(), record.getAddr(),
    record.getState(), record.getDob()));
    }
    else
    {
    Record newRecord = new Record(record.getName(), record.getTel(), record.getEmail(), record.getAddr(),
    record.getState(), record.getDob());
    newRecord.setNext(firstLink);
    firstLink = newRecord;
    addToBack(newRecord);
    }*/

    /*
    else
    {
    add
    }
    {
    Record newRecord = new Record(record.getName(), record.getTel(), record.getEmail(), record.getAddr(),
    record.getState(), record.getDob());
    Record current = firstLink;
    if(current.getNext() == null)
    current.setNext(newRecord);
    else
    addToBack(current.getNext());
    }
     */

}

public String toString()
{
    if(firstLink == null)
        return "Empty List\n\n";
    String result = "";
    Record current = firstLink;
    result += "\nName: "+current.getName()+"\nTelephone: "+current.getTel()+"\nEmail: "+current.getEmail()+
    "\nAddress: "+current.getAddr()+"\nState: "+current.getState()+"\nDOB: "+current.getDob()+"\n\n"; 
    while(current.getNext() != null)
    {
        current = current.getNext();
        result += "\nName: "+current.getName()+"\nTelephone: "+current.getTel()+"\nEmail: "+current.getEmail()+
        "\nAddress: "+current.getAddr()+"\nState: "+current.getState()+"\nDOB: "+current.getDob()+"\n\n";
    }
    return "List: \n\n"+result;
}

public void reverse()
{   
    Record previousRecord = null;
    Record currentRecord = firstLink;
    while (currentRecord != null) 
    {
        Record nextRecord = currentRecord.getNext();
        currentRecord.setNext(previousRecord);
        previousRecord = currentRecord;
        currentRecord = nextRecord;
    }
    firstLink = previousRecord;
}

public int sizeOf()
{
    Record currentRecord = firstLink;
    int size = 1;
    if (currentRecord == null)
    {
        return 0;
    }
    else
    {
        while (currentRecord.getNext() != null)
        {
            size++;
            currentRecord = currentRecord.getNext();
        }
    }
    return size;
}

public String phoneNumberByName(String name)
{
    Record currentRecord = firstLink;
    while(currentRecord.getName().equals(name) == false)
    {
        currentRecord = currentRecord.getNext();
    }
    return currentRecord.getTel();
    /*
    Record currentRecord = firstLink;
    if (currentRecord.getName().equals(name))
    {
    return currentRecord.getTel();
    }
    else
    {
    firstLink = currentRecord.getNext();
    phoneNumberByName(name);

    }
    return "Unexpected behaviour. You should never see this message.";
     */

}

public String emailByName(String name)
{
    Record currentRecord = firstLink;
    while(currentRecord.getName().equals(name) == false)
    {
        currentRecord = currentRecord.getNext();
    }
    return currentRecord.getEmail();
}

public String nameByPhoneNumber(String tel)
{
    Record currentRecord = firstLink;
    while(currentRecord.getTel().equals(tel) == false)
    {
        currentRecord = currentRecord.getNext();
    }
    return currentRecord.getName();
}

public String dobByName(String name)
{
    Record currentRecord = firstLink;
    while (currentRecord.getName().equals(name) == false)
    {
        currentRecord = currentRecord.getNext();
    }
    return currentRecord.getDob();
}

}

The Record class, in case you need that too:

public class Record
{
private String name;
private String tel; // Telephone number
private String email;
private String addr; // Address
private String dob; // Date of birth
private String state;
private Record next = null; 

public Record(String name, String tel, String email, String addr, String state, String dob)
{
    this.name = name;
    this.tel = tel;
    this.email = email;
    this.addr = addr;
    this.dob = dob;
    this.state = state;
    //this.next = null;
} // end of the constructor

public String getName()
{ return name; }

public String getTel() 
{ return tel; }

public String getEmail() 
{ return email; }

public String getAddr()
{ return addr; }

public String getState()
{ return state; } 

public String getDob() 
{return dob; }

public void setName(String name)
{ this.name = name; }

public void setTel(String tel)
{ this.tel = tel; }

public void setEmail(String email) 
{ this.email = email; }

public void setAddr(String addr)
{ this.addr = addr; }

public void setState(String state)
{ this.state = state; }

public void setDob(String dob)
{ this.dob = dob; }

public Record getNext()
{ return next; }

public void setNext(Record record)
{ next = record; }

}

Andreas · Accepted Answer · 2017-12-06 21:44:29Z

3

Recursive addToBack is fairly simple. In pseudo-code, your existing non-recursive is:

public void addToBack(rec) {
    if (first == null)
        first = new(rec)
    else {
        curr = first;
        while (curr.next != null)
           curr = curr.next
        curr.next = new(rec)
    }
}

As recursive, it would have to be two methods:

public void addToBack(rec) {
    if (first == null)
        first = new(rec)
    else
        addToBackInternal(first, rec)
}

private void addToBackInternal(curr, rec) {
    if (curr.next == null)
        curr.next = new(rec)
    else
        addToBackInternal(curr.next, rec)
}

A better implementation might be a more reusable findLast internal method:

public void addToBack(rec) {
    if (first == null)
        first = new(rec)
    else
        findLast(first).next = new(rec)
}

private Node findLast(curr) {
    if (curr.next == null)
        return curr
    return findLast(curr.next)
}

answered Dec 6, 2017 at 21:44

Andreas

160k13 gold badges164 silver badges262 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Justiciar Over a year ago

This definitely worked for the addToBack method, and I was able to get that working with recursion after looking over your examples. I had been thinking about a helper method, but wasn't sure how it should look. Thanks!

Justiciar Over a year ago

This actually helped me see how I could also convert the other while loops (specifically for the methods that search the list for a result) into recusive calls using a helper method. I'm going to mark the question as answered. Thanks for the thorough help.

Collectives™ on Stack Overflow

Java - Recursive Linked List implementation

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related