1. Предисловие
Недавно при рассмотрении структур данных и алгоритмов некоторые проблемы алгоритма используют идею стеков, и когда дело доходит до стеков, мы должны поговорить о связанных списках. Массивы и связанные списки являются основой линейных структур хранения, а стеки и очереди являются приложениями линейных структур хранения ~
В этой статье в основном объясняются основные знания в односвященных списках и делают простое введение. Если есть ошибка, пожалуйста, поправьте ее.
2. Обзор и знания
Говоря о связанных списках, давайте сначала упомянем массив. Сравнение их с массивами очень хорошо понимает структуру хранения связанных списков.
2.1 Просмотрите массив
Мы выучили массивы как в C, так и в Java:
Преимущества массивов:
Недостатки массивов:
2.2 Описание списка ссылок
После прочтения массива вернитесь к нашему связанному списку:
N -узлы дискретно выделяются и связаны друг с другом через указатели. У каждого узла есть только один узел предшественника, каждый узел имеет только один последующий узел, первый узел не имеет узела предшественника, а узел хвостового узела не имеет последующего узла.
Преимущества связанного списка:
Недостатки связанных списков:
Я объясню термины, связанные со связанным списком через картинку выше:
Чтобы определить связанный список, нам нужен только указатель головы, и весь связанный список может быть выведен через указатель головы ~
Есть несколько категорий связанных списков:
1. Таблица односторонних ссылок
2. ТАБЛИЦА ДИСТОРОВНАЯ ТАБЛИЦА
3. Список ссылок утилизации
При эксплуатации связанного списка вам нужно помнить:
Поле указателя в узле указывает на узел!
3. Список ссылок на реализацию Java
алгоритм:
Сначала мы определяем класс как узел
Для удобства операции я напрямую определил ее как публичную.
открытый класс Node {// Домен данных Public Int Data; // указатель домен, указывая на следующий узел общего узла следующим; public node () {} public node (int data) {this.data = data; } public node (int data, node next) {this.data = data; this.next = Далее; }} 3.1 Создать связанный список (добавить узлы)
Вставьте данные в связанный список:
/*** Добавить данные в связанный список** @param значения Данные, которые будут добавлены*/public static void adddata (int value) {// инициализировать узел для добавления NewNode = new Node (value); // временный узел узла Temp = Head; // Найти хвостовой узел while (temp.next! = Null) {temp = temp.next; } // Случай, когда head node.next is null был включен ~ temp.next = newnode; } 3.2 Проверка связанного списка
Мы написали метод добавления выше, и теперь мы пройдем через него, чтобы посмотреть, правильно ли он ~~~
Начните с первого узла и продолжайте искать, пока не появится данные о последующем узле:
/ *** Переход к соединенному списку** @param головка головки головки*/ public static void traverse (головка узла) {// Временный узел, запустите с первого узла узла Temp = Head.next; while (temp! = null) {System.out.println («Следуйте официальной учетной записи java3y:» + temp.data); // продолжить со следующим temp = temp.next; }}результат:
3.3 Вставьте узел
/*** Вставьте узел узел** @param головочный указатель головки* @param индекс индекса, который будет вставлен* @param значения для вставки*/public static void insertnode (головка узла, int index, int value) {// Во -первых, вам нужно определить, является ли указанная позиция законной, if (index <1 || позиция незаконна. "); возвращаться; } // Временный узел, начните с начального узла узла Temp = Head; // щелкните текущую позицию Traversal Int CurrentPos = 0; // инициализировать узел для вставки узла insertNode = new Node (значение); while (temp.next! = null) {// Местоположение предыдущего узла было найдено, если ((index - 1) == currentPos) {// Temp представляет предыдущий узел // указать исходный указатель из предыдущего узла в вставленный узел в insertnode.next = temp.next; // указать поле указателя предыдущего узла на узел, который должен быть вставлен temp.next = insertnode; возвращаться; } currentPos ++; temp = temp.next; }} 3.4 Получите длину связанного списка
Очень просто получить длину связанного списка. Это можно сделать, пройдя его и получить +1 для каждого узла ~
/ *** Получить длину связанного списка* @param головка головки*/ public static int linklistlength (head узла) {int length = 0; // Временный узел, запустите с первого узла узла Temp = head.next; // Найти хвостовой узел, пока (temp! = Null) {length ++; temp = temp.next; } return длины; } 3.5 Удалить узлы
Удаление узла в определенном месте на самом деле очень похоже на узел вставки, и вам также необходимо найти предыдущий узел. Измените поле указателя предыдущего узла, и вы можете удалить его ~
/** * Удалить узлы в соответствии с местоположением * * @param Head Head Pointer * @param Индекс местоположение, которое должно быть удалено */public static void deleteNode (head node, int index) {// Во -первых, вам необходимо определить, является ли указанное местоположение законным, if (index <1 || index> linklidelenge (head) + 1) (System.out.print.print. возвращаться; } // Временный узел, начните с начального узла узла Temp = Head; // текущее местоположение обхода записи IS int currentpos = 0; while (temp.next! = null) {// местоположение предыдущего узла найдено, если ((index - 1) == currentPos) {// Temp представляет предыдущий узел // temp.next представляет узел, который вы хотите удалить // хранилище Узел, который вы хотите удалить node deleteNode = temp.next; // Следующий узел, который вы хотите удалить узел, передается предыдущему узлу для управления temp.next = deletenode.next; // java перерабатывает его, и не должно иметь большого смысла установить его на нулевое (я лично думаю, если это неверно, укажите его ~) deleteNode = null; возвращаться; } currentPos ++; temp = temp.next; }} 3.6 Сортировать связанный список
Я уже говорил о 8 алгоритмах сортировки [сводка из восьми алгоритмов сортировки]. На этот раз я выберу простую сортировку пузырьков (на самом деле, я хочу быстро написать, но это немного сложно попробовать ...)
/ ** * Сортировка связанного списка * * @param head * */ public static void sortlinklist (node head) {node currentNode; Узел NextNode; for (currentNode = head.next; currentNode.next! = null; currentNode = currentNode.next) {for (nextnode = head.next; nextnode.next! = null; nextnode = nextnode.next) {if (nextnode.data> nextnode.next.data) {int extnode.data; nextnode.data = nextnode.next.data; nextnode.next.data = temp; }}}} 3.7 Найти узел k-last в связанном списке
Этот алгоритм довольно интересный: установите два указателя P1 и P2, чтобы сделать P2 K узлы быстрее, чем P1, и одновременно пройти назад. Когда P2 пуст, P1-K-Th Last Node
/ *** Найдите k-й до последнего узла в связанном списке (установите два указателя P1 и P2, сделайте P2 k быстрее, чем P1, и одновременно пройти назад. Когда P2 пуст, P1-это k-й, пока последний узел** @param* @param k k-th до последнего узла. LinkLide (Head) P1;
3.8 Удалить дубликаты данных в связанном списке
Это похоже на пузырьковую, если она равна, его можно удалить ~
/ ** * Удалить дублируемые данные в связанном списке (аналогично пузырькам, он эквивалентен удалению) * * @param головной головки головки */ public static void leteteduplecate (head узла) {// Временный узел, (начиная с первого узла-> узел с реальными данными) node temp = head.next; // Следующий узел текущего узла (первый узел) Node nextNode = temp.next; while (temp.next! = null) {while (nextnode.next! = null) {if (nextnode.next.data == nextnode.data) {// удалить следующий узел (текущий узел указывает на следующий узел) nextnode.next = nextnode.next.next; } else {// продолжить с nextnode = nextnode.next; }} // Следующий раунд сравнения temp = temp.next; }} 3.9 Запрос промежуточных узлов связанного списка
Этот алгоритм также довольно интересный: указатель, который занимает 1 шаг каждый раз, указатель, который занимает 2 шага каждый раз, а затем делает один шаг, то есть промежуточный узел
/ *** Запросить промежуточный узел одного связанного списка*/ public Static Node SearchMid (head узла) {Узел P1 = Head; Узел P2 = голова; // Сделайте один шаг и один шаг два шага, пока он не станет нулевым. Средний узел, которого вы достигаете (P2! = NULL && P2.NEXT! = NULL && P2.NEXT.NEXT! = NULL) {P1 = P1.NEXT; P2 = p2.next.next; } return p1; }3.10 рекурсивно вывод одно связанных таблиц от хвоста до головы
/ *** Вывод единого связанного списка от хвоста к головке от рекурсивно** @param Head Head Node*/ public static void printlistersely (head узла) {if (head! = Null) {printlistreversely (head.next); System.out.println (Head.data); }} 3.11 Список обратных ссылок
/ *** Реализовать инверсию связанного списка** @param Узел Головой узел связанного списка*/ public static node reverselinklist (узлы узла) {node prev; if (node == null || node.next == null) {prev = node; } else {node tmp = reverselinklist (node.next); node.next.next = node; node.next = null; prev = tmp; } return prev; } Ссылка на список обратных ссылок от: //www.vevb.com/article/136185.htm
4. Наконец
Нетрудно понять сам связанный список, но он может вызвать головные боли при выполнении соответствующих операций. Head.next Next Next .... (я все еще слаб в алгоритме ... У меня недостаточно мозгов ...) Я написал эту маленькую вещь через два дня ...
Вы можете сделать что угодно, просто зная его указатель головы при использовании связанного списка.
1. Добавить данные в связанный список
2. Переверните связанный список
3. Вставьте узлы в связанный список в данном месте
4. Получите длину связанного списка
5. Удалить узел в данном месте
6. Сортировать связанный список
7. Найдите узел k-last в связанном списке
8. Удалить дубликаты данных в связанном списке
9. Запрос промежуточных узлов связанного списка
10. рекурсивно вывод с односменной таблицей от хвоста до головы
11. Список обратных ссылок
PS: Реализация каждого будет отличаться, поэтому некоторые мелкие детали неизбежно изменятся, и нет фиксированного способа ее написать, чтобы вы могли реализовать соответствующие функции ~
Суммировать
Вышеуказанное - все содержание этой статьи. Я надеюсь, что содержание этой статьи имеет определенную справочную ценность для каждого обучения или работы. Если у вас есть какие -либо вопросы, вы можете оставить сообщение для общения. Спасибо за поддержку Wulin.com.
Ссылки: