We present the possibility of tuning the spin-wave band structure, particularly the bandgaps in a nanoscale magnonic antidot waveguide by varying the shape of the antidots. The effects of changing the shape of the antidots on the spin-wave dispersion relation in a waveguide have been carefully monitored. We interpret the observed variations by analysing the equilibrium magnetic configuration and the magnonic power and phase distribution profiles during spin-wave dynamics. The inhomogeneity in the exchange fields at the antidot boundaries within the waveguide is found to play a crucial role in controlling the band structure at the discussed length scales. The observations recorded here will be important for future developments of magnetic antidot based magnonic crystals and waveguides.