With increasing popularity of cloud storage, efficiently proving the integrity of data stored on an untrusted server has become significant. Authenticated skip lists and rank-based authenticated skip lists (RBASL) have been used to provide support for provable data update operations in cloud storage. However, in a dynamic file scenario, an RBASL based on block indices falls short when updates are not proportional to a fixed block size; such an update to the file, even if small, may result in O ( n ) updates on the data structure for a file with n blocks. To overcome this problem, we introduce FlexList, a flexible length-based authenticated skip list. FlexList translates variable-size updates to O (⌈ u/B ⌉) insertions, removals, or modifications, where u is the size of the update and B is the (average) block size. We further present various optimizations on the four types of skip lists (regular, authenticated, rank-based authenticated, and FlexList). We build such a structure in O ( n ) time and parallelize this operation for the first time. We compute one single proof to answer multiple (non)membership queries and obtain efficiency gains of 35%, 35%, and 40% in terms of proof time, energy, and size, respectively. We propose a method of handling multiple updates at once, achieving efficiency gains of up to 60% at the server side and 90% at the client side. We also deployed our implementation of FlexDPDP (dynamic provable data possession (DPDP) with FlexList instead of RBASL) on PlanetLab, demonstrating that FlexDPDP performs comparable to the most efficient static storage scheme (provable data possession (PDP)) while providing dynamic data support.