4 ms·
Open Data Structures: An Introduction – Pat Morin (pdf and source code)
- nkurz 10y agoI like that this exists, but I find myself bothered that all mentions of efficiency (that I saw at a quick skim) are based only on asymptotics of the storage space and number of operations per element as the number of elements goes to infinity without any mention of the constants involved. While this is standard for the theoretical side of computer science, it seems at odds with the emphasis on real working code. For example, (from what I saw) the chapter on linked lists talks about different ways of cutting down on storage space, but there is no mention that of the problem of "pointer chasing". Worse, as the number of elements increases, the cost of each memory access increases to, so even the assumption of "constant time" is wrong. While you can still gain a theoretical understanding of linked lists without this awareness, it's unlikely that you would apply them correctly.