An example of using a linked list?

Question

Java

Please tell us about a case from the practice of programming in a C-like language, when a linked list was really needed. I have never had such a case, and I couldn’t come up with a situation in which it would be needed right away.

This should be the case when you need to constantly remove and insert elements using an iterator that constantly lives somewhere inside the list.

Linked list lobbying surprises me. On Github, the standard Java linked list LinkedList is more common than TreeSet, TreeMap and ArrayDeque combined: github.com/search?l=java&q=LinkedList&ref=searchresults&type=Code. Every day, just because of the presence of a linked list in the standard libraries of C-like languages, tens of thousands of dollars of extra electricity is burned on servers.

True, I know one use of a linked list as a model - for the implementation of lock-free lists and queues, but not as an independent structure.

Answer 1

In general, I don’t want to argue, you most likely simply didn’t like LinkedList “algorithmically” and troll it :)
Yes, it has few applications, specifically so few. Basically, someone will stick it where it is not necessary out of ignorance and then sit and rake what the problem is.
But still, for the list of listeners, I use LinkedList. everything I listed above + it behaves as expected in all situations with this use and will not create unexpected performance drops (small, but still) for me, like the same ArrayList if I just want to add / remove a listener without worrying about their number in advance.
You will like the approach to separating LinkedList in C # from just lists, where it does not implement IList and it will not work by accident, only if it is unlikely as a collection, ArrayList is called List there and most do not even know about LinkedList.
In the article below, a list with the results of the average time for operations:
(nanoseconds, less is better)

ArrayList add:    13265642
LinkedList add:    9550057

ArrayList get:       1543352
LinkedList get:     85085551

ArrayList remove:    199961301
LinkedList remove:    85768810

Here. It just feels like you asked a question to make sure your opinion is right and you don’t want to listen to others :)

Answer 2

A memory allocator, such as the classic malloc .

Answer 3

Hash tables use linked lists, not array lists.

Answer 4

I can't speak for all languages, but in C++ std::list is rarely more efficient than other containers. But there are times when it is preferable, such as in graph data structures such as the Boost Graph Library .

Answer 5

I will answer as a developer in Java and C #, I use linked lists very rarely and carefully, but there is one case in which there is no structure better than it - a list of listeners of some garbage. Why? Because it eats little memory and is used only for sequential reading, deleting from any place in the list, and a linked list is the most optimal data structure for this.
Java example:

public class ObservableValue {

        public interface Observer {
            void onValueChanged(Object newValue);
        }

        private Object value;
        private final List<Observer> observers = new LinkedList<Observer>();

        public Object getValue() {
            return value;
        }

        public void setValue(Object newValue) {
            this.value = newValue;
            notifyOnValueChanged(newValue); // уведомляем слушателей
        }

        // дешевая вставка объекта
        public void addObserver(Observer observer) {
            observers.add(observer);
        }

        // дешевое удаление с любого места в списке
        public boolean removeObserver(Observer observer) {
            return observers.remove(observer);
        }

        // дешевое чтение т.к. не по индексу, а последовательно
        private void notifyOnValueChanged(Object newValue) {
            for (Observer observer : observers) {
                if (observer != null) observer.onValueChanged(newValue);
            }
        }

    }

If you find a data structure that fits better - please tell me :)

Answer 6

FAT file system table. I don't know about other systems.

Answer 7

LinkedList is needed where, on the one hand, sheets are needed. And on the other - quick inserts in the middle. There are not many examples, but here are two:
1) We periodically receive updates that an object from the list has disappeared. And this happens often, and there are many objects. For example, we are told that the car has been sold.
2) It is convenient to create chains of events where intermediate events can be inserted.

Answer 8

As mentioned above - a hash table. If you look at the implementation of std::unordered_map, then all the elements are arranged in a list, and iterators to the elements of this list are stored in the table. Such a structure allows both to iterate over all elements of the table and to remove an element in constant time.

Answer 9

In java, LinkedList is the ideal queue implementation for most cases.