Массивы, связанные списки, очереди и стеки, подробное объяснение четырех основных структур данных.

Эта статья является первой подписанной статьей сообщества Nuggets, и ее перепечатка без разрешения запрещена.

последовательность

Откройте новую яму, на этот раз数据结构与算法专题, гарантирую не голубить, эта тема будет разделена на три части:

базовая структура данных: В дополнение к этим в заголовке этой главы будут структуры данных, такие как хэш-таблицы, деревья и кучи.
Алгоритм сортировки: отдельное введение в некоторые часто используемые алгоритмы, такие как всплытие, выделение, вставка, слияние, быстрая сортировка, сортировка кучей и т. д.
Расширенные структуры данных: Расширенная структура данных не означает, что она более продвинутая, это в основном расширение базовой структуры данных из предыдущей статьи, например дерево B+ (разновидность дерева N в дереве), красно-черное дерево (собственно -дерево балансировки, обычно используемое в индустрии) и некоторые улучшенные хэши вроде кукушки или что-то в этом роде.

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

Прежде чем мы начнем эту главу, давайте поговорим о моих взглядах на структуры данных Старая поговорка гласит:

Программа = Структура данных + Алгоритм.

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

Во-первых, все должны знать, что структуры данных и алгоритмы создаются для решения практических задач. Например, у нас в базе данных 1000 Вт данных. Я хочу мгновенно запрашивать нужные мне данные. Можно ли это сделать?

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

Есть ли лучший способ решить эту проблему?

Да, через哈希表Структура данных организует эти данные, хэш-таблица позволяет нам быстро запрашивать любые данные, которые мы хотим, со сложностью времени O(1), будь то 1000 Вт или 2000 Вт, мы можем запросить любые данные, которые мы хотим, в одно мгновение, что такое удивительное эффект, промежуточное ПОRedisи новичок в отечественной базе данныхTiDBВсе запросы выполняются через хеш-таблицу.

В дополнение к хеш-таблицам мы также можем сделать это с помощью древовидных структур данных, таких как те, которые обычно используются в реляционных базах данных.B+索引, это древовидная структура, это N-дерево, оно может выполнять запросы со скоростью O(logN), хотя скорость не такая высокая, как у хэш-таблицы, но поддерживает диапазонные запросы, что очень важно для базы данных , поэтому база данных обычно выбирает его в качестве индекса первичного ключа.

Выше я вкратце привел два примера структур данных, а алгоритмы? Алгоритмы и структуры данных часто идут рука об руку.

Как и дерево, почему оно выполняет запросы быстро?

Он использует идею алгоритма «разделяй и властвуй».В запросе данных двоичный алгоритм будет использоваться для непрерывного уменьшения размера данных для достижения временной сложности O (logN).

Благодаря деформации дерева также родилась структура данных кучи. Куча — это то, что мы часто называем приоритетной очередью. Благодаря характеристикам структуры данных кучи также родилась концепция сортировки кучи. много общего с проблемой topK.Хороший эффект.

Говоря о деревьях, как насчет хеш-таблиц?

Хороший эффект от хеш-таблицы или нет, в значительной степени зависит от ее хеш-алгоритма.В принципе, все языки имеют встроенную структуру данных хэш-таблицы, например HashMap в Java, и некоторые языки сценариев. словарь (Dict) из , все они реализованы с помощью хеш-таблицы, а словарь Python 2.7 также имеет лазейки из-за проблем с реализацией.

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

Без лишних слов, давайте начнем~

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

1. Обозначение «большое О»

Любой инженер-разработчик, даже без профессионального образования, должен был более или менее слышать о нотации Big O.

Это числовое представление, используемое для измерения временной и пространственной сложности. Проще говоря, оно предназначено для измерения того, занимает ли алгоритм много времени и много памяти. В этой статье оно в основном используется для выражения времени. сложность, а пространство пока не задействовано.

Например, если мы хотим измерить скорость алгоритма, вашей первой реакцией может быть оценка того, сколько времени требуется для его выполнения, но один и тот же алгоритм работает на старых процессорах Pentium и новейших процессорах I9-9700K. .

Поэтому нам нужна более точная запись, а именно запись Big O. В записи Big O,Мы измеряем скорость алгоритма количеством шагов.

    public void test(int[] items) {
        
    }

Предполагая, что это алгоритм обхода, он должен посетить каждый элемент в элементах, поэтому, если длина элементов равна N, то алгоритм обхода должен выполнить N шагов, а его временная сложность равна O (N).

Предположим, что это алгоритм обхода, тогда есть вход N, он обязан посетить каждый элемент, поэтому ему нужно выполнить N шагов, тогда его временная сложность равна O(N).

Временную сложность нотации Big O можно условно разделить на следующие уровни:

O(1): постоянный уровень, независимо от того, насколько велик ввод, количество шагов, которые он выполняет, постоянно, оно не будет увеличиваться по мере увеличения ввода, поиск в хеш-таблице - это этот уровень.
O(N): Линейный уровень, количество шагов, потребляемых по мере увеличения входных данных, также имеет положительную корреляцию, и алгоритм обхода находится на этом уровне.
O(logN): Логарифмический уровень.Каждый раз, когда ввод удваивается, шаг стоимости увеличивается на 1. Алгоритм бинарного поиска относится к этому уровню.
O(N²): Квадратный уровень, количество используемых шагов будет экспоненциально увеличиваться по мере увеличения входных данных. Обычно этот уровень используется, когда ваш алгоритм использует двухуровневый цикл for, например пузырьковую сортировку.

Кроме того, есть кубический уровень, который описан не слишком подробно, и он такой же, как и квадратный уровень, только больше.

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

Логарифмический уровень можно понять на небольшом примере: у нас есть отсортированный массив и мы находим одно из чисел по двоичному алгоритму.

Предполагая, что в массиве 16 чисел, вам нужно искать 4 раза, потому что 2 в 4-й степени равно 4.

Предполагая, что в массиве 2 147 483 647 чисел (2,1 миллиарда), вам нужно искать 31 раз, потому что 2 в 31-й степени равно 2 147 483 648, что уже является довольно быстрой скоростью.

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

Еще одна вещь, которую я хочу подчеркнуть в нотации Big O,это не так точно, как математика.

Предположим, у вас есть алгоритм, который каждый раз требует 2N обходов для завершения выполнения, тогда его временная сложность также равна O(N), а константа будет игнорироваться в большой нотации O, потому что константа фиксирована и не изменится.

Другим примером является O(1), даже если вы не изучали хеш-таблицы, вы должны быть в состоянии понять, что ни один алгоритм не может найти определенное число, выполнив только один шаг, это должно быть выполнено в несколько шагов, но выполняется ли это 5 шагов Независимо от того, сколько шагов это занимает, это O (1), потому что количество шагов постоянно и не зависит от размера входных данных.

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

2. Массив

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

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

В массиве каждый массив имеет адрес, и адрес памяти каждого элемента может быть легко вычислен через индекс массива, чтобы добиться быстрого доступа и присвоения, поэтому эффективность его поиска по индексу O (1) уровень .

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

Еще одна огромная слабость массивов заключается в том, что когда массив заполнен, невозможно загрузить больше элементов.

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

на ЯвеArrayListКлассы делают именно это.

Далее я просто реализую динамический массив:

public class DiyList<T> {

    private Object[] items;

    private int size = 0;

    public DiyList() {
        items = new Object[16];
    }

    public T get(int index) {
        if (index > size) {
            throw new NoSuchElementException();
        }
        return (T) items[index];
    }

    public boolean add(T item) {
        if (Objects.isNull(item)) {
            throw new NullPointerException();
        }

        if (size >= items.length / 2) {
            grow();
        }

        items[size++] = item;
        return true;
    }

    private void grow() {
        Object[] newItems = new Object[items.length * 2];
        System.arraycopy(items, 0 , newItems, 0 , items.length);
        items = newItems;
    }

    public int size() {
        return size;
    }

}

Поскольку универсальный тип в Java будет иметь универсальное стирание, я не могу определить универсальный массив, поэтому я могу только реализовать массив Object и принудительно преобразовать этот элемент в универсальный элемент, когда я его получу.

В этом примере я реализовал только базовые методы get и add.Самый важный метод для динамического расширения — это метод Grow, который отвечает за расширение массива.Метод расширения также может быть простым, просто скопируйте его.

Хотя динамические массивы помогают автоматически расширяться, они также влекут за собой затраты на копирование элементов:

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

Поэтому динамические массивы больше подходят для индексных запросов, вставка и удаление требуют дополнительных затрат времени и места.

2.1 Внешкольные занятия

На основе приведенного выше примера добавлен метод удаления.Пример прошел самопроверку и может быть скопирован и запущен напрямую.

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

Массивы в предыдущем разделе более удобны для доступа к элементам.связанный списокЕго легче вставлять и удалять.

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

Структура кода связанного списка обычно выглядит следующим образом:

public class DiyLinked<T> {
    private int size = 0;
    private Node<T> item;

    private static class Node<T> {
        private T item;
        private Node<T> next;
        public Node(T t) {
            item = t;
        }
    }
}

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

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

Почему я упоминаю головной узел, потому что, если вы хотите вставить и удалить в хвостовом узле, вы должны пройти по связанному списку, найти последний узел связанного списка, а затем вставить, стоимость обхода связанного списка O (N) .

Упомянутый выше имеет только одинnextСвязанный список, на который ссылаются, называется односвязным списком.Чтобы решить проблему вставки хвоста, появляется двусвязный список.

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

Картина постепенно разваливается

Код для двусвязного списка обычно выглядит так:

public class DiyLinked<T> {
    private int size = 0;
    private Node<T> first;
    private Node<T> last;

    private static class Node<T> {
        private T item;
        private Node<T> next;
        private Node<T> prev;
        public Node(T t) {
            item = t;
        }
    }
 }

Двусвязный список будет поддерживаться одновременноfirstиlastЕсть два узла, поэтому, когда вам нужно вставить конец, вставляйте или удаляйте непосредственно через последний узел.

на ЯвеLinkedListЭто двусвязный список, и реализация также очень проста. Связный список является еще одним краеугольным камнем структуры данных. Многие структуры данных могут быть деформированы на основе связанного списка.

3.1 Упражнения после занятий

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

4. Очередь

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

Характеристики очереди подобны нашим ежедневным очередям за покупками в порядке живой очереди.

Из диаграммы видно, что в очереди всего два действия:入队(enqueue)и出队(dequeue), как правило, он вставляется в хвост и вынимается из головы.

Существует два типа очередей:

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

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

4.1 Очередь построения массива

Массивы тоже упоминались в предыдущей статье, и у них есть два недостатка:

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

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

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

Две операции для циклических очередей:

Вылет: выйти из команды напрямуюfirstДанных узла достаточно, затем установите для первого элемента индекса значение null и добавьте 1 к индексу, на который указывает first.
Присоединяйтесь к команде: вам нужно судить, прежде чем присоединиться к командеend+1Есть ли элемент в индексе, если элемента нет, то в очередь можно нормально войти, если есть элемент, то очередь заполнена.

4.2 Очередь построения связанного списка

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

LinkedList, обычно используемый в Java, также реализует интерфейс Queue, что означает, что LinkedList также поддерживает операции с очередями.

Поскольку связанный список был упомянут выше и очень прост, я не буду его здесь реализовывать~

4.3 Упражнения после занятий

Реализуйте ограниченную очередь, используя массив.

5. Стек

куча, представляет собой структуру данных "первый поступил - последним вышел/последним пришел - первым вышел". Если я хочу привести пример из жизни, я думаю, что наиболее ярким является журнал. Пули, которые вставляются первыми, часто являются быть расстрелянным последним.

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

В компьютерном мире стек часто используется для стека вызовов программы.Исключение StackOverFlow, которое иногда возникает в программе, связано с тем, что стек вызовов программы исчерпан, поэтому стек обычно имеет относительно фиксированную глубину.С этого момента из представления Это хорошая идея, чтобы построить стеки из массивов. (На глубину стека часто также влияет установленная память)

Стек использует push для вставки элементов, использует pop для чтения элементов, а последний элемент, который нужно поместить, часто является первым элементом, который будет извлечен.

Точно так же структура данных стека существует и в Java, ее имя называется Stack, но она не только имеет две операции стека, но также имеет некоторые доступные операции массива, потому что наследует класс List, широкий интерфейс, подобный этому Дизайн — это модель провала дизайна библиотеки классов, надеюсь, вы не будете подражать ему~

5.1 Внешкольные занятия

Реализовать стек с массивом.

6. Заключение

В заключительном эпилоге я познакомлю вас с этими четырьмя структурами данных:

Массивы: поиск по индексу выполняется быстро, вставка и удаление — медленно.
Связанный список: быстрая вставка и удаление в начале и в конце, медленный поиск.
Очередь: вставка хвоста и выход, временная сложность O (1), очень быстро.
Стек: вставка хвоста и вывод хвоста, временная сложность O (1), очень быстро.

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

При выборе массива вы можете оценить размер коллекции и инициализировать более подходящий динамический массив, чтобы избежать многократного расширения.
При выборе связанного списка вы можете сначала спросить себя, есть ли больше сценариев запроса или больше сценариев вставки.
При использовании очередей и стеков вы также можете сначала понять, является ли базовая реализация используемой вами библиотеки классов массивом или связанным списком.Когда то, с чем вы сталкиваетесь, больше не является для вас черным ящиком, вы можете легко принять решение ~

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

Поиск по дереву, вставка и удаление составляют O(logN), что принадлежит структуре данных с преимуществами во всех аспектах. Дерево может решить проблему эффективности вставки посередине. Я дам вам подробное объяснение в следующем статья, в том числе несколько книг по алгоритмам.Дерево AVL не упоминается.

Наконец, я хотел бы попросить всех лайкнуть.Если у вас есть какие-либо вопросы, вы можете оставить сообщение в области комментариев, и я отвечу вовремя.