The true cost of linked lists · YKarroum
Linked lists are often overused in introductory algorithmics courses, due to a heavy focus on theorical complexities. Unfortunatly, in practice, computers are complex beasts. They don’t execute instructions sequentially 1 with the same cost 2. This means that a data structure with faster theorical complexities does not necessarily translate to a more efficient data structure in practice.
The true cost of linked lists · YKarroum Just another personal blog, where I write about python, c++ and other stuff. © 2024. All rights reserved. YKarroum The true cost of linked lists 30 May 2022 Linked lists are often overused in introductory algorithmics courses, due to a heavy focus on theorical complexities. Unfortunatly, in practice, computers are complex beasts. They don’t execute instructions sequentially 1 with the same cost 2 . This means that a data structure with faster theorical complexities does not necessarily translate to a more efficient data structure in practice
Explore this link on the map →related reading
- abseil / Performance Hintsabseil.io
- Linked list - Wikipediaen.wikipedia.org
- Intrusive linked lists - Data structures in practicedata-structures-in-practice.com
- Introduction - Learning Rust With Entirely Too Many Linked Listsrust-unofficial.github.io
- Infographics: Operation Costs in CPU Clock Cycles - 6IT6it.dev
- abseil / Performance Hintsabseil.io
- Memory location matters for performancepythonspeed.com
- CS106B Linked Structuresweb.stanford.edu
- Algorithms for Modern Hardware - Algorithmicaen.algorithmica.org
- Memory access is O(N^[1/3])vitalik.eth.limo
- Static search trees: 40x faster than binary search · CuriousCodingcuriouscoding.nl
- list - C++ Referencecplusplus.com