Hi all,
Thanks for the feedback so far. I am implementing it to further my understanding of how they work. My intent would be to use the .NET implementation.
I did think as I was implementing the loops with indexes that what happens if the list gets too big? I know that each node is stored, non-sequentially, in memory which makes it longer to iterate over.
I have thought about adding a reference for the tail; making it the result of AddNode().
What I'm stuck on is the idea of holding a place in the list. Isn't this just as slow as starting from the beginning? If you start at the beginning then you don't have to worry about going backwards. Otherwise I need to create a doubly Linked List to be able to traverse back and forth.
I have some great feedback to work on from this.
Thanks,
Stitchs.
You cannot just focus on low-level details such as memory footprint and cache usage. There's a place for that, but before you get there, you should at least be aware of some basic algorithm analysis. Yes, a doubly-linked list has an extra cost, and non-sequential memory access has an extra cost, but you're forgetting about the plain old cost of having to do N steps when there's an alternative that would take a constant amount of time.
Before you even get to insertion, let's say I want to loop over the whole list and do something with each string. I'm curious, what would that code look like, to the list user and internally?