Spotify has an option to show songs in your playlists which have been removed. In the mobile app, Settings->Content and Display->Show unplayable songs.

Hope this helps!