Linked list programming
I've been meaning to brush up on my coding and wanted to get back to linked list. I've done it in the past of course, but I'm trying to think of a program concept that is best suited for it in practical terms. What are possible programs I can make with linked list that can have value in a business setting or something along those lines?
These days, not much. Until you get big objects or really big lists, you're better off with a container in which the items are contiguous in memory:
https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
I am an array kind of guy, so with some admitted bias...
to me the best use of a list is a stack.
why?
the push is really easy: tmp = new memory, fill in tmp's data parts, head = tmp. No fuss there. Pop is also easy: result = head, head = head->next, result->next = null (possibly not important).
you can keep a second list of popped pointers to re-use in pushes, if empty, then grow with new. You can even allocate blocks of nodes as dynamic arrays here when you grow, keeping the cache miss problems in check. (I assume you want to play with pointers. If not, array indices as 'pointers' into a vector lets you reshape a vector into a list and keeps the memory as a solid block and makes the code here extremely short and sweet, but its also silly since vectors perform fine as stacks straight up).
you can keep track of the # of items in push/pop so you don't have to iterate the list to count if you care about its size.
there isnt much more to it, the above is a pretty good first cut at a stack that will perform fairly well.
the above idea grows to show that LL is also a decent queue, if you maintain a tail pointer, the middle is ignored and the extreme ends are all you care about. When you start searching the whole list, that is the weakness of lists.
there are some other edge cases where a list may be the right choice, but I do not care for them for most other uses.
lists are also good for temporary things. in a business setting, say you want to sort all your people by last name. Or by zip code. Or by how much they owe you. Or any of a dozen other ways to slice the same data? Instead of re-sorting fat data items a bunch of times, you can generate a sorted list of pointers to the data more efficiently.
to me the best use of a list is a stack.
why?
the push is really easy: tmp = new memory, fill in tmp's data parts, head = tmp. No fuss there. Pop is also easy: result = head, head = head->next, result->next = null (possibly not important).
you can keep a second list of popped pointers to re-use in pushes, if empty, then grow with new. You can even allocate blocks of nodes as dynamic arrays here when you grow, keeping the cache miss problems in check. (I assume you want to play with pointers. If not, array indices as 'pointers' into a vector lets you reshape a vector into a list and keeps the memory as a solid block and makes the code here extremely short and sweet, but its also silly since vectors perform fine as stacks straight up).
you can keep track of the # of items in push/pop so you don't have to iterate the list to count if you care about its size.
there isnt much more to it, the above is a pretty good first cut at a stack that will perform fairly well.
the above idea grows to show that LL is also a decent queue, if you maintain a tail pointer, the middle is ignored and the extreme ends are all you care about. When you start searching the whole list, that is the weakness of lists.
there are some other edge cases where a list may be the right choice, but I do not care for them for most other uses.
lists are also good for temporary things. in a business setting, say you want to sort all your people by last name. Or by zip code. Or by how much they owe you. Or any of a dozen other ways to slice the same data? Instead of re-sorting fat data items a bunch of times, you can generate a sorted list of pointers to the data more efficiently.
Last edited on
For small- to mid-sized containers, the classic linked list will probably perform relatively lousy, mostly because it's a bunch of random pointers to non-contiguous data that the CPU can't cache or predict.
Where I would bet a linked list might actually be good is for parallel-computing, where different threads/processes might look at/update just one local section of a linked list without affecting the structure as a whole. Just an idea; maybe a vector would be better there, too. Must measure. My actual bet would be that a combination of vectors (contiguous data) and linked lists would be the best for parallel computing
Where I would bet a linked list might actually be good is for parallel-computing, where different threads/processes might look at/update just one local section of a linked list without affecting the structure as a whole. Just an idea; maybe a vector would be better there, too. Must measure. My actual bet would be that a combination of vectors (contiguous data) and linked lists would be the best for parallel computing
Last edited on
Topic archived. No new replies allowed.