Published Paper Details:

This review paper presents a comprehensive performance analysis of two fundamental pointer-based data structures, the linked list and the skiplist, through the lens of the modern multi-level CPU cache hierarchy (L1, L2, L3). While traditional algorithmic analysis focuses on asymptotic complexity, contemporary hardware realities indicate that memory access patterns and their interaction with the cache often dominate real-world performance. The discussion begins by establishing essential principles of cache architecture and the principle of locality, followed by a survey of seminal works in cache-conscious data structure design that highlight key optimization strategies such as clustering and layout transformation. The comparative analysis exposes the inherent spatial locality limitations of both standard linked lists and skiplists, stemming from their reliance on discontiguous, heap-allocated nodes. Evidence shows that the skiplist's logarithmic search complexity can be undermined by its irregular memory access patterns, frequently producing a higher rate of cache misses than a linear scan over a linked list. The paper concludes by examining modern cache-optimized skiplist variants that blend pointer-based and array-based designs to mitigate these hardware-level penalties, emphasizing that a cache-aware design philosophy is essential for achieving high performance in memory-intensive applications.