import java.util.*;

interface sortedList{
	public boolean isEmpty();
	public int size();
	public void add(Object o);
	public void remove(Object o);
	public int locateIndex(Object o);
	public Vector<Object>get();
}
class A02Q01 implements sortedList{
	private int k = 100;
	protected static final int NOTHING = -1;
	protected Object[]data=new Object[k];
	protected int[]prev=new int[k];
	protected int[]next=new int[k];
	protected int count=0;
	protected int start=0;
	public A02Q01(){
		for(int i=0;i<k;i++){
			prev[i]=NOTHING;
			next[i]=NOTHING;
		}
	}
	public boolean isEmpty(){
		return count==0;
	}
	public int size(){
		return count;
	}
	public 	void add(Object o){
		if(count==k-1)return;
		int where = NOTHING;
		for(int i=0;i<k;i++){
			if(data[i]==null){
				where=i;
				break;
			}
		}
		if(where==NOTHING)return;
		add(o,start,where);
		count++;
	}
	protected void add(Object o,int from,int where){
		Comparable<Object>a=(Comparable<Object>)data[from];
		Comparable<Object>b=(Comparable<Object>)o;
		if(data[from]==null){
			data[where]=o;
			prev[where]=NOTHING;
			next[where]=NOTHING;
		}else if(a.compareTo(b)>0){
			data[where]=o;
			next[where]=from;
			if(from==start){
				start=where;
				prev[where]=NOTHING;
			}else{
				prev[where]=prev[next[where]];
				next[prev[where]]=where;
			}
			prev[next[where]]=where;
		}else if(next[from]==NOTHING){
			data[where]=o;
			prev[where]=from;
			next[where]=NOTHING;
			next[prev[where]]=where;
		}else{
			add(o,next[from],where);
		}
	}
	public void remove(Object o){
		int where = locateIndex(o);
		if(where==NOTHING)return;
		if(prev[where]==NOTHING){
			start=next[where];
			if(next[where]!=NOTHING){
				prev[next[where]]=NOTHING;
				next[where]=NOTHING;
			}
		}else{
			if(next[where]!=NOTHING){
				prev[next[where]]=prev[where];
				next[prev[where]]=next[where];
				next[where]=NOTHING;
			}
			prev[where]=NOTHING;
		}
		data[where]=null;
		count--;
	}
	public int locateIndex(Object o){
		return recursiveSearchFunction(o,start);
	}
	protected int recursiveSearchFunction(Object target,int where){
		if(size()==0)return NOTHING;
		if(target.equals(data[where]))return where;
		if(where==NOTHING)return NOTHING;
		return recursiveSearchFunction(target,next[where]);
	}
	public Vector<Object>get(){
		Vector<Object>v=new Vector<Object>();
		for(int i=start;i!=NOTHING;i=next[i]){
			v.add(data[i]);
		}
		return v;
	}
}
public class Main{
	public static void main(String[]args){
		A02Q01 obj=new A02Q01();
		obj.add((Object)"3");
		obj.add((Object)"1");
		obj.add((Object)"2");
		for(Object o:obj.get()){
			System.out.println(o);
		}
		System.out.println("---");
		obj.remove((Object)"2");
		for(Object o:obj.get()){
			System.out.println(o);
		}
		System.out.println("---");
		obj.add((Object)"4");
		for(Object o:obj.get()){
			System.out.println(o);
		}
	}
}