Buenas,

Java nos da muchas herramientas muy útiles. Una es la clase ArrayList. Es un vector de objetos, pero la diferencia con un array normal es que el ArrayList puede variar de tamaño.

Yo haría lo siguiente.

Una clase vehículo, con sus dos atributos, marca (string) y estaAlquilado (boolean). En el atributo marca guardaremos la marca de cada objeto vehiculo y en estaAlquilado true si lo está y false si no lo está.

De esta manera haces tu lista declarando tu arraylist y luego le metes tantos vehiculos como quieras ya que partimos con la ventaja de que el arraylist es dinámico. No dejo el código para que lo hagas tú mismo y puedas aprender, si quieres que te lo deje puedes decirlo y te lo dejaré comentado.

Otro detalle es que ignoro tus conocimientos en el tema de objetos en Java. Pero te recomiendo que aprendas rápido el ArrayList, que es muy útil.

Puedes hacer un array bidimensional.

String[][] listaVehiculos = new String[tantos coches como quieras][2];

De manera gráfica quedaría así.

{"mercedes-benz", "bmw", "audi"}
{"alquilado","no alquilado", "no alquilado"}

De esta manera en tu array de dos dimensiones tienes todo almacenado. Si luego quieres mostrar los que estan o no alquilados haces dos bucles que recorran el array ( dos porque es bidimensional, uno dentro de otro) y pones un if

Si no lo entiendes así puedo hacerte el código comentado.

Haz dos vectores más.

String[] alquilados = new String[1];
String[] libres = new String[marca.lenght-2] // esto hace que el libres sea del tamaño de marca menos el coche que quitaste porque lo alquilaste

//ahora recorremos el marcas a ver si el valor que metiste en "alquilar existe"

for(int i=0; i<marcas.lenght; i++){
if(marcas.equals(alquilar))
{
alquilados[0]=marcas;
System.out.println("Coche alquilado");
}
else // si no esta alquilado
{
for(int j=0; j<libres.lenght;j++) // recorremos la array de libres
{
if(libres[j]==null) // en el primer hueco que pille vacio
{
libres[j]=marcas; // metemos la marca que no esta alquilada
break; // rompemos el bucle pequeño
}
}
}
}

No lo he probado, tendrá errores seguramente, pero es para que cojas la idea.