Введение
В последнее время при рассмотрении структур данных и алгоритмов в некоторых алгоритмических задачах используется идея стеков, когда речь идет о стеках, приходится говорить о связных списках. И массивы, и связанные списки являются основой линейных структур хранения, а стеки и очереди — приложениями линейных структур хранения.
В этой статье в основном объясняетсяОсновы односвязного списка, сделайте простое введение ~ пожалуйста, поправьте меня, если я ошибаюсь
2. Ретроспектива и знание
Говоря о связанных списках, давайте сначала поговорим о массивах.Если вы сравните их с массивами, вы поймете структуру хранения связанных списков.
2.1 Просмотр массивов
Массивы, будь то C или Java, мы изучим:
- массив представляет собойнепрерывное хранениеЛинейная структура с элементами одного типа и одинакового размера
Преимущества массивов:
- Быстрый доступ
Недостатки массивов:
- Длина массива должна быть известна заранее
- Вставка и удаление элементов происходит медленно
- пространство обычно ограничено
- Требует больших смежных блоков памяти
- Вставка и удаление элементов неэффективны
2.2 Описание связанного списка
Прочитав массив,Вернуться в наш список:
- связанный списокдискретное хранилищеЛинейная структура
N узлов выделяются дискретно и соединяются друг с другом с помощью указателей.Каждый узел имеет только один узел-предшественник, и каждый узел имеет только один узел-последователь.У первого узла нет узла-предшественника, а у хвостового узла нет узла-последователя.
Преимущества связанного списка:
- пространство не ограничено
- Вставка и удаление элементов выполняется быстро
Недостатки связанного списка:
- доступ медленный
Вводится терминология, связанная со связанным списком, позвольте мне объяснить ее с помощью рисунка выше:
Чтобы определить связанный список, нам нужен только указатель головы, весь связанный список можно вывести через указатель на голову~
Связанный список разделен на несколько категорий:
- Односвязный список
- Один узел указывает на следующий узел
- Двусвязный список
- Узел имеет два поля указателя
- Круговой связанный список
- Он может найти все остальные узлы через любой узел и указать последний узел двух (двусторонних/односторонних) связанных списков на первый узел для реализации цикла.
О чем следует помнить при работе со связанными списками:
- Поле указателя в узле указывает на узел!
3. Java реализует связанный список
алгоритм:
- траверс
- найти
- пустой
- разрушать
- найти длину
- Сортировать
- удалить узел
- вставить узел
ps: я определяю головной узел в переменной-члене:
private static Node head = new Node();
Во-первых, мы определяем класс как узел
- поле данных
- поле указателя
Для удобства работы я прямо определяю его как общедоступный.
public class Node {
//数据域
public Integer data;
//指针域，指向下一个节点
public Node next;
public Node() {
}
public Node(int data) {
this.data = data;
}
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
3.1 Создание связанного списка (добавление узлов)
Вставить данные в связанный список:
- Найдите хвостовой узел для вставки
- Даже если заголовок node.next равен нулю, головной узел подключается к новому узлу без прохождения цикла while (Я инициализировал головной узел, поэтому нет необходимости судить, является ли головной узел нулевым)~
/**
* 向链表添加数据
*
* @param value 要添加的数据
*/
public static void addData(int value) {
//初始化要加入的节点
Node newNode = new Node(value);
//临时节点
Node temp = head;
// 找到尾节点
while (temp.next != null) {
temp = temp.next;
}
// 已经包括了头节点.next为null的情况了～
temp.next = newNode;
}
3.2 Обход связанного списка
Мы написали метод увеличения выше, теперь пройдемся по нему, чтобы убедиться, что он правильный~~
Начиная с первого узла, продолжайте смотреть назад, пока следующие узлы не будут иметь данных:
/**
* 遍历链表
*
* @param head 头节点
*/
public static void traverse(Node head) {
//临时节点，从首节点开始
Node temp = head.next;
while (temp != null) {
if (temp.data != null) {
System.out.println("关注公众号Java3y：" + temp.data);
}
//继续下一个
temp = temp.next;
}
}
результат:
3.3 Вставить узел
- Чтобы вставить узел в связанный список, вы должны сначала определить, является ли позиция допустимой, прежде чем вставлять~
- Просто найдите предыдущий узел, куда вы хотите его вставить.~
/**
* 插入节点
*
* @param head 头指针
* @param index 要插入的位置
* @param value 要插入的值
*/
public static void insertNode(Node head, int index, int value) {
//首先需要判断指定位置是否合法，
if (index < 1 || index > linkListLength(head) + 1) {
System.out.println("插入位置不合法。");
return;
}
//临时节点，从头节点开始
Node temp = head;
//记录遍历的当前位置
int currentPos = 0;
//初始化要插入的节点
Node insertNode = new Node(value);
while (temp.next != null) {
//找到上一个节点的位置了
if ((index - 1) == currentPos) {
//temp表示的是上一个节点
//将原本由上一个节点的指向交由插入的节点来指向
insertNode.next = temp.next;
//将上一个节点的指针域指向要插入的节点
temp.next = insertNode;
return;
}
currentPos++;
temp = temp.next;
}
}
3.4 Получить длину связанного списка
Очень просто получить длину связанного списка, пройти по нему и каждый раз, когда вы получаете узел +1~
/**
* 获取链表的长度
* @param head 头指针
*/
public static int linkListLength(Node head) {
int length = 0;
//临时节点，从首节点开始
Node temp = head.next;
// 找到尾节点
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}
3.5 Удалить узел
Удаление узла в определенной позиции на самом деле очень похоже на вставку узла и также требует поиска предыдущего узла.Измените поле указателя предыдущего узла, и вы можете удалить его~
/**
* 根据位置删除节点
*
* @param head 头指针
* @param index 要删除的位置
*/
public static void deleteNode(Node head, int index) {
//首先需要判断指定位置是否合法，
if (index < 1 || index > linkListLength(head) + 1) {
System.out.println("删除位置不合法。");
return;
}
//临时节点，从头节点开始
Node temp = head;
//记录遍历的当前位置
int currentPos = 0;
while (temp.next != null) {
//找到上一个节点的位置了
if ((index - 1) == currentPos) {
//temp表示的是上一个节点
//temp.next表示的是想要删除的节点
//将想要删除的节点存储一下
Node deleteNode = temp.next;
//想要删除节点的下一个节点交由上一个节点来控制
temp.next = deleteNode.next;
//Java会回收它，设置不设置为null应该没多大意义了(个人觉得,如果不对请指出哦～)
deleteNode = null;
return;
}
currentPos++;
temp = temp.next;
}
}
3.6 Сортировка связанного списка
8 алгоритмов сортировки были упомянуты ранее.Краткое изложение восьми алгоритмов сортировки], на этот раз выберите простую пузырьковую сортировку (на самом деле я хочу написать быструю сортировку, и мне кажется, что это немного сложно...)
/**
* 对链表进行排序
*
* @param head
*
*/
public static void sortLinkList(Node head) {
Node currentNode;
Node 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 temp = nextNode.data;
nextNode.data = nextNode.next.data;
nextNode.next.data = temp;
}
}
}
}
3.7 Найти k-й последний узел в связанном списке
Этот алгоритм довольно интересен: установить два указателя p1, p2,Пусть p2 будет k узлами быстрее, чем p1, и заодно пройдёте назад, когда p2 пусто, тогда p1 будет k-м узлом снизу
/**
* 找到链表中倒数第k个节点(设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点
*
* @param head
* @param k 倒数第k个节点
*/
public static Node findKNode(Node head, int k) {
if (k < 1 || k > linkListLength(head))
return null;
Node p1 = head;
Node p2 = head;
// p2比怕p1快k个节点
for (int i = 0; i < k - 1; i++)
p2 = p2.next;
// 只要p2为null，那么p1就是倒数第k个节点了
while (p2.next != null) {
p2 = p2.next;
p1 = p1.next;
}
return p1;
}
3.8 Удалить повторяющиеся данные в связанном списке
Если у вас есть какие-либо вопросы, прежде чем здесь, вы можете перейти к:blog.CSDN.net/Я слежу за японским VE…
сделать ссылку
3.9 Запрос промежуточного узла связанного списка
Этот алгоритм тоже весьма интересен:Один делает один шаг за раз, другой делает два шага за раз, после обхода двух шагов, а затем указатель на один шаг, то есть промежуточный узел
/**
* 查询单链表的中间节点
*/
public static Node searchMid(Node head) {
Node p1 = head;
Node p2 = head;
// 一个走一步，一个走两步，直到为null，走一步的到达的就是中间节点
while (p2 != null && p2.next != null && p2.next.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
return p1;
}
3.10 Вывод односвязного списка от конца к началу с помощью рекурсии
/**
* 通过递归从尾到头输出单链表
*
* @param head 头节点
*/
public static void printListReversely(Node head) {
if (head != null) {
printListReversely(head.next);
if (head.data != null) {
System.out.println(head.data);
}
}
}
3.11 Обратно связанный список
/**
* 实现链表的反转
*
* @param head 链表的头节点
*/
public static Node reverseList(Node head) {
Node pre = null;
Node cur = head;
while (cur != null) {
Node next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
// 翻转完，使用下面的代码进行遍历吧：
public static void traverse4Reverse(Node head) {
//临时节点，从首节点开始
Node temp = head;
while (temp != null) {
if (temp.data != null) {
System.out.println("关注公众号Java3y：" + temp.data);
}
//继续下一个
temp = temp.next;
}
}
Ссылка на обратный связанный список из:
Четвертый, последний
Нетрудно понять сам связанный список, но выполнять связанные операции — головная боль.
head.next next next next ....(Я пока слаб в плане алгоритмов.. Мозгов не хватает...) Я такое написал через два дня...
Для управления связанным списком требуется толькоВы можете выполнить любую операцию, зная указатель на ее головку.
- Добавить данные в связанный список
- Перейдите, чтобы найти хвостовой узел и вставьте его (пока
while(temp.next != null), при выходе из цикла будет найден хвостовой узел)
- Перейдите, чтобы найти хвостовой узел и вставьте его (пока
- просмотреть связанный список
- Начиная с первого узла (допустимого узла), если он не равен нулю, вывод
- Вставить узел в связанный список в заданной позиции
- Сначала определите, действительна ли позиция (в пределах длины связанного списка)
-
Найдите предыдущий узел, куда вы хотите вставить
- Перенести точку из предыдущего узла во вставленный узел, чтобы указать на
- Поле указателя предыдущего узла указывает на узел, который вы хотите вставить
- Получить длину связанного списка
- Каждый раз при посещении узла может выполняться операция переменной ++.
- удалить узел в заданной позиции
- Сначала определите, действительна ли позиция (в пределах длины связанного списка)
-
Найдите предыдущий узел, куда вы хотите вставить
- Укажите узел первоначально от предыдущего узла к следующему узлу
- Сортировка связанного списка
- Отсортируйте его с помощью пузырькового алгоритма
- Найти k-й последний узел в связанном списке
- Установите два указателя p1, p2, пусть p2, чем p1к быстроузлов, двигаясь назад,Когда p2 пуст, то p1 — это k-й узел снизу.
- Удалить повторяющиеся данные связанного списка
- Операция похожа на пузырьковую сортировку.Пока он равен, его можно удалить~
- Промежуточный узел таблицы цепочки запросов
- Этот алгоритм тоже весьма интересен: человек делает один шаг за раз, он делает два шага за раз,После двух шагов обхода, а затем указатель одного шага, то есть промежуточный узел
- Рекурсивно выводить односвязный список от конца к началу
- Пока внизу еще есть данные, то смотрим вниз,Рекурсия переворачивается с конца вперед.
- обратно связанный список
- Есть два способа, рекурсивный и нерекурсивный, что я считаю довольно сложным. Вы можете проверить это по ссылке, которую я дал ~
PS:Реализация у всех будет разная, поэтому некоторые мелкие детали неизбежно будут меняться, и нет фиксированного способа написания, просто можно достичь соответствующих функций ~
Использованная литература:
- Блог Woohoo.cn на.com/Я очень эмоционален/боюсь/6589…
- Блог Wooooooo.cn на.com/Не думайте, что Аллан CE/…
Если в статье есть какие-либо ошибки, пожалуйста, поправьте меня, и мы сможем общаться друг с другом. Учащиеся, привыкшие читать технические статьи в WeChat и желающие получить больше ресурсов по Java, могутОбратите внимание на публичный аккаунт WeChat: Java3y