I started in June last year and booked the Land End YHA a week in advance and then the Inverness SYHA a few days before arrival and secured the last bed. Other than that, I camped and always arrived un-announced. There was usually plenty of room and I only got turned away once; that was at Banff Links Caravan Park and they were full because the Scottish school holidays had just started. I cycled on a couple of hundred yards and wild camped by the sea then popped back and used their facilities without shame, as I would have happily paid. Edited to add, I also had one night in an independent hostel at Anstruther, that I booked the day before.