We consider a network with several users trying to access a database of files stored at a server through a shared link. Each user is equipped with a cache, where files can be prefetched according to a caching policy which is mainly based on the popularities of the files. Coded caching tries to exploit coding opportunities created by cooperative caching and has been shown to significantly reduce the load on the shared link. Most of the prior works focused on optimizing the caching policy so as to minimize this expected load. Given the caching policy and the user demands, the problem of minimizing the load over the shared link is essentially an index coding problem. In this paper, we design a novel delivery scheme that builds on a prior scheme for the uniform demand case, but performs better in the non-uniform demand case. We also evaluate this delivery scheme for different caching policies.