Java - 递归链表实现

Question

我已经完全实现了一个单链表(代码如下)，但是，该作业特别要求它使用递归来实现。我一直在尝试将我编写的 while 循环转换为递归调用，但是陷入困境并且需要一些帮助。我最近的递归尝试包含在代码中，但已被注释掉。提前感谢您的帮助。

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

}

Record 类，如果您也需要的话:

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

}

Answer 1

递归addToBack相当简单。在伪代码中，您现有的非递归是:

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

作为递归，它必须有两种方法:

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

更好的实现可能是更可重用的 findLast 内部方法:

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