代码之家 › 专栏 › 技术社区 › witcheR

java-递归地插入/删除排序列表

sortedlist recursion java

witcheR · 技术社区 · 8 年前

我有一个我正在实现的抽象类,其中所有实现的函数都必须使用递归:

public abstract class List<E> implements Iterable<E> {
protected class Node<T> {

    protected Node(T data) {
        this.data = data;
    }

    protected T data;
    protected Node<T> next;
}

public abstract void insert(E data);
public abstract void remove(E data);
public abstract E retrieve(int index);
public abstract boolean search(E data);

protected Node<E> head;
}

下面是我迄今为止的实现。我相信我已经正确地完成了搜索和检索方法,并且大多数remove方法都是正确的。我担心的一个问题是插入方法的错误(我不需要特别的工作代码,但可能需要一个类似伪代码的解释,说明当抽象类只接受一个数据参数时如何插入,从而需要一个私有类)。另一个问题是在移除方法的这种情况下:

if (key.compareTo(temp.data) == 0){

        }

import java.util.Iterator;
import java.util.Random;

public class SortedList<E extends Comparable<? super E>> extends List<E> {

public static void main(String[] args) {

    Random rand = new Random(1);
    SortedList<Integer> list = new SortedList<Integer>();

    list.insert(1);
    System.out.println(list.search(1));
}
 public Iterator<E> iterator() {

        return new Iterator<E>() {
            public boolean hasNext() {
                return curr != null;
            }
            public E next() {
                E temp = curr.data;
                curr = curr.next;
                return temp;
            }
            public void remove() {
                throw new UnsupportedOperationException();
            }
            private Node<E> curr = (Node<E>)head;
        };
    }


public void insert(E data) {
    Node<E> temp = new Node<E>(data);
    Node<E> curr = head;
     if (head == null || data.compareTo(head.data) < 0) {
            temp.next = head;
            head = temp;
        }
    insert(curr, data);
}
    private void insert(Node<E> curr, E data){
        if (curr.next == null) {
            curr.next.data = data;
        } else {
            curr.next.insert(curr, data);
        }
    }


public void remove(E data) {
    Node<E> curr = head;
    remove(curr, data);
}
    private void remove(Node<E> temp, E key){
        if (temp == null){
            return;
        }
        if (key.compareTo(temp.data) == 0){

        }
        if (key.compareTo(temp.next.data) == 0){
            temp.next = temp.next.next;
            return;
        }
        if (key.compareTo(temp.next.data) < 0){
            remove(temp.next, key);
        }

    }




public E retrieve(int index) 
{
    Node<E> curr = head;
    int counter = 0;
    return retrieve(curr, index, counter);
}
 private E retrieve(Node<E> temp, int idx, int c)
   {
      if (idx == c){
          return temp.data;
      }
      return retrieve(temp.next, idx, c++);
   }


 public boolean search(E data)
   {
     Node<E> curr = head;
     return search(curr, data);
   }
   private boolean search(Node<E> temp, E key)
   {
      if (temp == null){
         return false;
      }
      if (key.compareTo(temp.data) == 0){
        return true;
      }
      if (key.compareTo(temp.data) < 0){
         return search(temp.next, key);
      }
      return false;
   }

}

1 回复 | 直到 8 年前

Brion 8 年前

从头部移除:

因为您知道您的列表应该始终排序,如果您删除(当前)头值,那么下一个头应该是行中的“下一个”。您最初只能访问“head”节点,并且必须一个一个地向下移动列表。

在这种情况下,假设有一群人按名字顺序排队。如果他们都手牵着手,形成一条链子,按顺序排到下一个人,你就把第一个人排在后面。从逻辑上讲,你可以假设握着他们手的人是新的头。

Node<E> temp = new Node<E>(data);
if(check to see if you want to remove head){
     temp.next = head.next; //current head points to next in line so so shall new head(temp);
     head = temp; //head ref variable points to only new head and old one is inaccessible and will be cleared out during garbage collection. 
}

中间插入和移除:

使用前面的牵手的相同类比。如果我需要在两个人中间“插入”一个人,我首先要找到他们属于哪里,然后让他们与“当前”和“下一个”之前和之后的人牵手。

对于插入代码,您必须搜索直到找到正确的插入位置,该位置可以位于两个节点之间,而不是假设如果下一个值为空,则只插入。

private void insert(Node<E> curr, E data){
    if (curr.next == null) {
        curr.next.data = data; //only inserts if next value is null
    } else { // what about inserting 3, into a list of {1,5}. 
        curr.next.insert(curr, data);
    }
}

您需要检查当前值和下一个值在排序顺序中是否正确。

else if(curr.data <= data && curr.next.data > data){
        // you've found the nodes you want to insert in between
}else{
  ... keep searching until you hit a null
}