Структура данных — LinkedList

В предыдущем блоге мы обсуждали массивы — одну из самых известных линейных структур данных в мире программирования. Несмотря на свою простоту и популярность, Array по своей природе имеет мало ограничений,

• Массивы по своей природе статичны, что делает их менее гибкими, когда объем данных увеличивается или уменьшается.
• Массивы довольно затратны для обычных операций, таких как вставка и удаление.

В этом блоге мы собираемся обсудить другую линейную структуру данных под названием LinkedList, которая поможет преодолеть несколько ограничений.

Связанный список:

LinkedList — это линейная структура данных, в которой каждый элемент является объектом. В отличие от Array, LinkedList не имеет непрерывной структуры памяти. Каждый элемент связан со следующим через указатель.

Каждый элемент в LinkedList называется Node. Каждый узел содержит ключ (интересующие данные) и дополнительный указатель для указания на следующий элемент в списке. Начальный указатель в LinkedList называется Head. Необходимо отметить, что "Head" — это не очередной узел, а указатель на первый элемент LinkedList. Для пустого LinkedList значение Head будет нулевым.

Чтобы сохранить связанный список, нам просто нужно помнить, где находится первый элемент. Мы можем найти остальные, следуя указателям.

Здесь на диаграмме, как мы видим, Head — это указатель на узел (объект), который содержит две части: ключ со значением «7» и другой указатель, указывающий на следующий узел, содержащий значение «10».

Выполнение:

public class LinkedList {
    Node head; // head of list 

    /* Linked list Node*/
    class Node {
        int data;
        Node next;

        // Constructor to create a new node 
        // Next is by default initialized 
        // as null 
        Node(int d) {
            data = d;
            next = null;
        }
    }
}

Характеристики связанного списка:

Динамический характер:

LinkedList — это динамическая структура, то есть список может увеличиваться или уменьшаться в зависимости от данных, что делает его более мощным и гибким, чем массивы. В отличие от массивов, LinkedList не хранится в непрерывной области памяти. Каждый элемент списка разбросан по памяти и связан указателями в Node. Таким образом, всякий раз, когда необходимо добавить новый элемент, выделяется отдельная память, достаточная для хранения ключа и указателя на следующий элемент.

Такая природа LinkedList позволяет использовать его в качестве базовой структуры данных для нескольких других динамических структур, таких как стеки, очереди и т. д.

Упрощенная вставка и удаление:

Вставка и удаление — самые затратные операции в массивах. Требуется перестановка всех элементов вокруг места работы. В худшем случае, когда массив заполнен, мы в конечном итоге копируем весь массив в больший, чтобы он соответствовал.

LinkedList делает это немного проще. нам нужно выделить память для вставляемых данных, создав узел, и простая настройка указателя сделает эту работу.

Таким образом, LinkedList выиграл себе лучший выбор, в то время как общее количество объектов изначально неизвестно.

Линейный обход

Как мы знаем, массивы обеспечивают постоянное время доступа, а также допускают произвольный доступ к элементам. Напротив, LinkedList обеспечивает только линейный обход, поэтому время выполнения в худшем случае может быть O(n) .

Кроме того, сложно перемещаться по LinkedList в обратном направлении (однако мы можем упростить его с помощью двусвязного списка).

Использование памяти

Эта характеристика LinkedList весьма спорна. Совершенно очевидно, что LinkedList занимает дополнительное место в памяти для указателя. Но, наоборот, в большинстве случаев Array может оказаться с выделенной, но не используемой памятью. LinkedList набирает здесь дополнительные очки, эффективно занимая только необходимые места. Это перевешивает Array даже с дополнительной памятью для указателя.

Сложность во времени и пространстве:

Импровизация в LinkedList

Двойной связанный список:

Одиночный LinkedList или LinkedList проще в реализации, довольно сложно пройти, что в обратном порядке, чтобы преодолеть это, мы можем использовать Double LinkedList, в котором каждый узел берет дополнительный указатель, чтобы указать предыдущий элемент на элемент в дополнение к указателю на элемент следующий пункт.

Двусвязный список имеет более эффективную итерацию, особенно если вам нужно когда-либо выполнять итерацию в обратном порядке и более эффективное удаление определенных узлов.

Использование указателя «Хвост»:

В некоторых случаях может быть удобно иметь указатель на последний элемент в LinkedList. Очень часто можно увидеть указатель «Хвост», указывающий на последний элемент в списке. Хвостовой указатель не всегда является импровизатором производительности, но он никогда не повредит. Возможно, не гарантируется, что он будет полезен всегда, но разумно иметь его, когда это уместно.

Не так уж часто можно увидеть LinkedList в вашей повседневной разработке, но LinkedList играет ключевую роль в большинстве других часто используемых вещей, таких как стеки и очереди. Одно очень интересное применение LinkedList заключается в полиномиальном представлении их манипуляций. Основное преимущество связанного списка для полиномиального представления состоит в том, что он может вместить количество полиномов растущего размера, так что их общий размер не превышает общей доступной памяти. Если вам нужна структура, которая должна быть достаточно гибкой для растущего объема данных, вы знаете, где искать.

Ссылки:

полный PDF в LinkedList и его приложениях