This thesis proposes the use of "Adaptive" Data-Structures (ADSs) that invoke reinforcement learning schemes from the theory of Learning Automata (LA). The ADSs work in conjunction with select re-organization rules to update themselves as they receive queries from the Environment. The result of such a process is to minimize the cost of query accesses. The Environments under consideration are those that exhibit a so-called "locality of reference", and are referred to as Non-stationary Environments (NSEs). A hierarchy of data "sub"-structures is used to design Singly-Linked Lists (SLLs) on SLLs, which contains outer and sub-list contexts. The Object Migration Automaton (OMA) family of reinforcement schemes are employed to capture the probabilistic dependence of the elements query accesses from the Environment within sub-lists. The Enhanced-OMA (EOMA), the Pursuit-EOMA (PEOMA), and the Transitivity-PEOMA (TPEOMA) are incorporated into the hierarchical SLLs. The results are currently the state-of-the-art methods for SLLs operating in NSEs.