Another programmer was mentioning that they haven't found a use case for using a linked list data structure in any professional software in his career. I couldn't think of any good examples off the top of my head. He is mostly a C# and Java developer
Can anyone give some examples where this was the correct data structure to solve a particular real world problem?
Related: What is a practical, real world example of the Linked List?
For problems where the number of maximal nodes are constrained to 100 or below or so, linked lists are a reasonable solution. The same can be true of things like bubble sort and other things that are thought to be sub-optimal.
Linked Lists offer several advantages over comparable data structures such as static or dynamically expanding arrays.
Any place where these advantages would be significantly valuable to a program (and the disadvantages of a LinkedList were negligible) would be a place to use a LinkedList.
As daustin777 points out, linked lists are all around you and you may not even know it. But the practicality of the matter is that they allow for some pretty basic operations to be performed with relative ease and flexibility. For example, not to sort, just swap pointers around. Need to insert or remove at arbitrary places? Insert or remove your pointers within the list. Need to iterate forwards and backwards ... linked list. While not precisely a business example, I hope this clarifies it enough for you to apply it to your own real world business case.
An immutable linked list is a very valuable structure, since you can 'share structure' with other lists with the same tail. Most functional languages include an immutable linked list type as one of their fundamental data structures, and these types are used all over the place.
Linked list pros:
Linked list cons:
Out of my head, I'd implement stacks, queues and messagepumps using linked lists. I'd also implement a datatree using multi-reference linked-lists for fast insertion / removal.
Stacks and queues are very clear examples of linked lists, but as other already have mentioned them I'd like to add a few other examples:
DOM stores nodes as linked lists. A simple javascript sample that is really the same in any language:
for (var node = parent.firstChild; node != null; node = node.nextSibling) {
// ..
}
I would imagine that a java developer has come across XML at some point.
Trees are another good examples of linked lists, even though they aren't simple one dimensional ones. Someone who's done a lot of java development has probably come across TreeMaps and TreeSets.
The entire discussion seems a bit silly to me. Linked lists are a fundamental data structure that is used everywhere. The only reason that one might think that he/she hasn't come across them is that you don't really have to worry about the implementation of data structures in todays high level languages, but of course they're still there.
They occur all the time, anywhere an object has a property that points to another object of the same type. In the CLR, exceptions form a linked list, due to the InnerException property.
A real-world example would be a FIFO queue. An simple array-based list is pretty bad for that because you need to add at one end and remove at the other end, and one of those operations will be O(n) with an array-based list (unless you add extra logic to work with a start AND end index), while both are O(1) with a linked list without extra effort.
As said already linked lists are very useful when you need to insert and delete elements.
For example to help debug memory management in my code I recently implemeneted a link list between all my refrence counted objects so that at the end of the program (when the refrences should all have hit zero and deleted the objects) I could see exactly what was still left, useually resulting in me being able to find a single object at the root of the problem.
CPython implements something similir with a massive linked list between nearly every when its built with debugging.
Intrusive linked lists are interesting beasts for game development. For example, it's somewhat common practice to have an intrusive singly- or doubly-linked "render" list:
class Renderable /* or class Object, whatever */
{
// ...
Renderable * m_pNext;
Renderable * m_pPrev; // or not, if singly-linked
// ...
}
As Renderables come into and out of existence they can register themselves with this list -- without causing any memory allocation. If their render depth or priority is changed they can remove and reinsert themselves, etc.
When it comes time to render, all you need to do is find the head of the list and zip through, calling the appropriate method!
(There are, of course, many variations on this theme, with multiple separate lists, etc. And you don't need to have an intrusive list to make this work, I just find the intrusive ones interesting.)
Linked Lists (paired with a hashtable) are really useful for LRU Caches.
Every Get needs to bump a node to the front of the list, an operation that is really cheap with linked lists.
Answering to the tag 'Data Structures', at a low level such as assembly, linked lists are an ideal way to store variable length lists of other data structures. There is no overhead for maintaining the list length or end, and there no is need for fixed size list items. The last reason also applies to higher level languages.
As perhaps the best real world example in .Net consider the MultiCastDelegate.
Linked lists implemented in this way, where the list chaining aspect is backed directly into the type rather than as a separate container, can be extremely powerful and efficient. They come however with a variety of trade offs.
One obvious one is code duplication, you must bake this logic in each type. Techniques such as extending a base class providing the pointer are messy (you lose strong typing without generics) and often unacceptable from a performance point of view.
Another is that you are limited to one implementation per type. You cannot make a singly linked structure into a doubly linked one without inserting an extra field in every instance and updating all the relevant code.
I wrote a BIOS extension (basically a device driver for a BIOS, written in assembly) for a USB host controller. -- Implementing a high-level seemingly abstract data structure like a linked list in assembly isn't as hard as it sounds. -- The controller serviced I/O requests for keyboard and disk using a linked list of packets in main memory. I maintained a pool of free packets in another linked list. Performing I/O basically involved grabbing a free packet from the beginning of the free list, configuring the packet, adding the packet to the device's list, and re-adding the packet to the beginning of the free pool when the I/O finished. Linked lists are lightning fast for moving around objects like this, especially when the objects are large, since the objects don't actually have to move. Only their pointers need to be updated.
An array-based queue would have required:
So, linked lists are a nice way to implement an arbitrarily long first-in-first-out queue of large objects.
Another thing to be careful about is that for small objects or where you allocate objects from a conventional heap instead of a custom free pool, arrays can be faster because copying isn't really that slow if it's not done that often, and the repeated allocation from the heap that a linked list would require every time a new element is added is slow.
Of course, you may want to simulate and measure your particular scenario with some throwaway test code to find the answer. I like to run loops a few million times with linked lists and arrays, with small and large objects, and time how long each takes in real time. Sometimes you'll be surprised.
I code mostly C# and I find linked and double linked list useful in two specific situations:
Ordinary generic collections won't let you change the collection during a for-each traversion. This is not a problem with a linked list.
Linked lists are more tolerant of multithreading. Different threads can work on different parts of the linked list, without colliding. They only have to lock two items to do an insert, not the whole collection.
Linked lists are simple and elegant.
Linked list is the essential data structure for Dancing Links, which is the technique used to efficiently implement Algorithm X, which is a backtracking algorithm to find all solutions to the NP-complete exact cover problem, to which many hard problems are naturally reducible to.