LinkedList – это линейная коллекция данных, в которой каждый узел или элемент коллекции связан со следующим узлом. Каждый узел содержит некоторые данные и имеет ссылку на следующий узел. Первый и последний узлы в коллекции называются head и хвостом коллекции соответственно. LinkedList является одним из самых простых и понятных структур данных, но довольно эффективным и простым в реализации. Как и многие другие Структуры данных, LinkedList предоставляет общие операции, такие как вставка, удаление. и поиск.

Основное преимущество LinkedList заключается в его операциях вставки и удаления. Поскольку LinkedList хранится иначе, чем обычный массив, где элементы хранятся в памяти непрерывно, нет необходимости перераспределять или реорганизовывать всю структуру во время выполнения после операций. вставки и удаления. Узлы LinkedList хранятся в памяти случайным образом, и для доступа к ним достаточно сохранить ссылку на узлы. Поскольку перераспределение или реорганизация всей структуры во время выполнения является дорогостоящей операцией, применение LinkedList в таких случаях является хорошей идеей. Операции вставки и удаления выполняются за постоянное время — O(1) . Такая производительность достигается простым изменением связей узлов.

public class Node{
    public int value;
    public Node next;

    public Node(int value){
        this.value = value;
        this.next = null;
    }

}

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

public class LinkedList {
    public Node head;
    public Node tail;
    public int count;

    public LinkedList() {
        head = null;
        tail = null;
    }

}

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

Вставка — O (1)

Удаление — O (1)

Поиск — O (N)

Давайте обсудим операции одну за другой.

Вставка или Добавление нового узла — добавить(узел) реализован довольно просто. Вставка нового узла возможна только в одном направлении и только в хвост коллекции. Всякий раз, когда вставляется новый узел, он становится хвостом. Следующий узел после tail всегда нулевой, т. е. не имеет значения или не существует. Важно отметить, что при добавлении первого узла он одновременно является головой и концом коллекции. Временная сложность алгоритма равна постоянному времени — O(1).

Удаление или удаление узла — remove(node) также реализован простым способом. Для удаления необходимо сохранить или получить ссылку узла, предшествующего удаляемому узлу. Следовательно, мы просто меняем ссылку предыдущего узла, чтобы она ссылалась на следующий узел. Как показано, может быть задан набор букв [a — b — c — b — e]. Удаление буквы —a приводит к следующему набору [b — c — b — e ]. Важно отметить, что если head коллекции удаляется, следующий элемент становится head коллекции; или если хвост удаляется, предыдущий узел становится хвостом. Временная сложность алгоритма равна постоянному времени — O(1).

Однако LinkedList не является решением всех проблем. LinkedList не обеспечивает быстрый произвольный доступ к узлам или элементы коллекции. Следовательно, невозможно получить доступ к данному элементу за постоянное время. Чтобы получить доступ к нужному узлу или элементу, необходимо перебрать коллекцию и найти ее. В конечном итоге операция поиска занимает — O(N)время на выполнение, где N — количество узлов в коллекции.

Это первая статья из серии Структуры данных. Если вам интересно погрузиться глубже и поиграть с LinkedList, я рекомендую реализовать обсуждаемые операции самостоятельно и протестировать.

Ниже приведены ссылки для:

Необработанные классы для самостоятельной реализации LinkedList
Пример реализации LinkedList
Тестовые примеры