Linked List Applications

Question

What are some examples of using a linked list? I know this is a good idea for implementing queues and stacks as linked lists, but is there a practical and direct example of a linked list, solving a problem that specifically uses fast insertion time? Not only other data structures based on linked lists.

Waiting for answers like this question about priority queues: Priority queue applications

I myself found one: the LRU cache (the least recently used) implemented with a hash table and linked list.

There is also an example Exception class with InnerExeption

What else do you have?

Answer 1

I work as a developer in the "big stock market" in the USA. Part of what makes us work at a very high speed is that after initialization (before the start of the day on the market) we do not allocate / distribute a bunch of heaps. This method is not unique to the exchange, it is also common in most real-time systems.

First of all, for us, linked lists are preferable to array-based lists, because they do not require heap allocation when the list grows or shrinks. We use linked lists in several applications on the exchange.

• One application is to pre-assign all objects to pools (which are linked lists) during initialization; therefore, whenever we need a new object, we can simply remove the list header.
• Another application is in order processing; each Order object implements the input interface of the linked list (has the previous and next link), therefore, when we receive an order from the client, we can remove the Order object from the pool and put it in the "for processing" list. Because each Order object implements a Linked List entry, adding to any point in the list is as simple as filling in the previous and next links.

Example above:

 Interface IMultiListEntry { public IMultiListEntry getPrev(MultiList list); public void setPrev(MultiList list, IMultiListEntry entry); public IMultiListEntry getNext(MultiList list); public void setNext(MultiList list, IMultiListEntry entry); } Class MultiListEntry implements IMultiListEntry { private MultiListEntry[] prev = new MultiListEntry[MultiList.MAX_LISTS]; private MultiListEntry[] next = new MultiListEntry[MultiList.MAX_LISTS]; public MultiListEntry getPrev(MultiList list) { return prev[list.number]; } public void setPrev(MultiList list, IMultiListEntry entry) { prev[list.number] = entry; } public IMultiListEntry getNext(MultiList list) { return next[list.number]; } public void setNext(MultiList list, IMultiListEntry entry) { next[list.number] = entry; } } Class MultiList { private static int MAX_LISTS = 3; private static int LISTS = 0; public final int number = LISTS++; private IMultiListEntry head = null; private IMultiListEntry tail = null; public IMultiListEntry getHead() { return head; } public void add(IMultiListEntry entry) { if (head==null) { head = entry; } else { entry.setPrevious(this, tail); tail.setNext(this, entry); } tail = entry; } public IMultiListEntry getPrev(IMultiListEntry entry) { return entry.getPrev(this); } public IMultiListEntry getNext(IMultiListEntry entry) { return entry.getNext(this); } } 

Now all you have to do is either extend MultiListEntry or implement IMultiListEntry and delegate the interface methods of the internal reference to the MultiListEntry object.

Answer 2

The answer can be infinite, and “a good example” is a subjective term, so the answer to your question is very controversial. Of course, there are examples. You just need to think about the possible needs of a quick insert.

For example, you have a list of tasks, and you need to solve all the problems. When you look at the list when the task is solved, you understand that you need to quickly solve a new task so that you insert the task after the task that you just solved. This is not a queue, because the list may be needed in the future for viewing, so you need to keep your list intact, in this case you cannot use the pop method.

To give you another example: you have a set of names in alphabetical order. Suppose that in some way you can quickly identify an object that has the next pointer to the object in which the specific name is stored. If you want to quickly delete the name, just go to the previous element of the object you want to delete. Deletion is also faster than with stacks or queues.

Finally, imagine a very large set of elements that you need to keep even after you insert or delete. In this case, it is much faster to search for the item to be deleted, or the item before the position at which your item should be inserted, and then perform the operation, than copy your entire large set.

Answer 3

hashmaps in java uses a list of links view. When more than one hash is contained in the same place, it leads to a collision, and at this time the keys are tied to a list of links.