Los contactos puedes tenerlos almacenados en muchos sitios. En el teléfono, en la tarjeta sim, sincronizados con una cuenta google, facebook, whatsapp...
Si quieres que quede vacío del todo por alguna razón, tendrás que eliminar las cuentas con las que sincronizas, limpiar la sim y también los contactos del teléfono.