Связанный список и массив — два важных и часто используемых базовых типа данных в типах данных.Массив — это структура данных, которая постоянно хранится в памяти, поэтому его преимущество в том, что он может быстро найти расположение элементов через индексы, а его недостаток — в том, что При вставке и удалении элементов это приведет к принудительному перемещению большого количества элементов.Чтобы решить и сбалансировать эту проблему, существует тип данных связанного списка.
Связанные списки и массивы могут эффективно дополнять друг друга, поэтому мы можем выбирать соответствующий тип данных в соответствии с различными бизнес-сценариями. Итак, в этой статье мы сосредоточимся на изучении связанного списка, во-первых, потому что это очень важно, а во-вторых, потому что это необходимо для интервью.Давайте сначала посмотрим на план этой статьи:
Посмотрев некоторые антияпонские драмы, мы все знаем, что для того, чтобы члены организации не оказались «в гнезде», некоторые секретные организации обычно используют единую линию связи между начальством и подчиненными для защиты других членов, и это» поведение" представляет собой связанный список основных функций.
Эта статья была включена в серию Github «Алгоритм обучения Xiaobai»:GitHub.com/VIP камень/Али…
Введение
Связанный список — это общая базовая структура данных, это линейный список, но он хранит данные не в линейном порядке, а хранит указатель (Pointer) на следующий узел в каждом узле.
Связанный список состоит из двух частей: поля данных и поля указателя., его состав следующий:
Анализ сложности
Поскольку связанный список не нужно хранить по порядку, связанный список может достигать сложности O(1) при вставке, что намного быстрее, чем последовательный список, но требуется O(n) времени, чтобы найти узел или получить доступ к элементу. определенное количество узлов, а временная сложность последовательной вставки таблицы и запроса составляет O (log n) и O (1) соответственно.
Анализ преимуществ и недостатков
Использование структуры связанного списка позволяет преодолеть недостаток, заключающийся в том, что размер данных массива связанного списка должен быть известен заранее Структура связанного списка позволяет полностью использовать пространство памяти компьютера и реализовать гибкое управление динамической памятью. Однако связанный список теряет преимущества случайного чтения массива, и в то же время накладные расходы связанного списка относительно велики из-за увеличения поля указателя узла.
Классификация
Связанные списки обычно делятся на следующие три категории:
- Односвязный список
- Двусвязный список
- Круговой связанный список
- односвязный список
- Двойной круговой связанный список
1. Односвязный список
Самый простой тип связанного списка — это односвязный список или односвязный список, который содержит два поля, поле данных и поле указателя, поле указателя используется для указания на следующий узел, а последний узел указывает на нуль. значение, как показано ниже:Направление обхода односвязного списка одно, и его можно пройти только от начала цепочки до конца цепочки. Его недостаток в том, что когда вы хотите запросить предыдущий узел узла, вы можете снова пройти запрос только с самого начала, поэтому эффективность относительно низкая, а появление двусвязного списка как раз решает эту проблему.
Далее мы используем код для реализации узлов односвязного списка:
private static class Node<E> {
E item;
Node<E> next;
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}
2. Двусвязный список
Двусвязный список также называют двусторонним связным списком.Каждый узел в нем состоит из трех частей: указатель prev указывает на предыдущий узел, а указатель data и next этого узла указывают на задний узел, как показано на рис. следующий рисунок:
Далее мы используем код для реализации узлов двусвязного списка:
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
3. Круговой связанный список
Циклический связанный список далее делится на одинарный циклический связанный список и двойной циклический связанный список, то есть головной и хвостовой узлы односвязного списка или двусвязного списка соединяются, таким образом реализуя одиночный циклический связанный список или двойной круговой связанный список, как показано на следующем рисунке:
Связанный список в Java
Изучив основы связанных списков,Давайте подумаем над вопросом: каким типом связанного списка является LinkedList в Java? Односвязный список или двусвязный список?
Чтобы ответить на этот вопрос, сначала мы должны посмотреть исходный код в JDK следующим образом:
package java.util;
import java.util.function.Consumer;
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
// 链表大小
transient int size = 0;
// 链表头部
transient Node<E> first;
// 链表尾部
transient Node<E> last;
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
// 获取头部元素
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
// 获取尾部元素
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
// 删除头部元素
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// 删除尾部元素
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
// 添加头部元素
public void addFirst(E e) {
linkFirst(e);
}
// 添加头部元素的具体执行方法
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
// 添加尾部元素
public void addLast(E e) {
linkLast(e);
}
// 添加尾部元素的具体方法
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
// 查询链表个数
public int size() {
return size;
}
// 清空链表
public void clear() {
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
// 根据下标获取元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
// 忽略其他方法......
}
из вышеуказанного узлаNodeОпределение можно рассматривать как:LinkedListНа самом деле это двусвязный список, потому что он определяет два указателяnext иprevиспользуются для указания на их следующий и предыдущий узлы соответственно.
Общие методы связного списка
LinkedListДизайн по-прежнему очень изобретателен.После понимания его кода реализации, давайте посмотрим, как он используется? Или каковы общие методы этого.
1. Увеличение
Далее давайте продемонстрируем использование метода add:
public class LinkedListTest {
public static void main(String[] a) {
LinkedList list = new LinkedList();
list.add("Java");
list.add("中文");
list.add("社群");
list.addFirst("头部添加"); // 添加元素到头部
list.addLast("尾部添加"); // 添加元素到最后
System.out.println(list);
}
}
Результат выполнения приведенного выше кода:
[Добавлено в начало, Java, китайский язык, сообщество, добавлено в конец]
В дополнение к вышеупомянутым трем методам увеличения,LinkedListТакже включены другие методы добавления, а именно:
- add(int index, E element): вставить элемент в указанную позицию;
- offer(E e): добавить элемент в конец связанного списка и вернуть результат, если он успешен;
- offerFirst(E e): вставьте элемент в заголовок и верните его, если он успешен;
- offerLast(E e): вставьте элемент в конец и верните значение, если оно выполнено успешно.
Разница между добавлением и предложением
Их различия в основном отражаются в следующих двух моментах:
- Метод предложения принадлежит интерфейсу Deque, а метод добавления — интерфейсу Collection;
- При сбое добавления в очередь будет сообщено об ошибке, если используется метод добавления, а метод предложения вернет false.
2. Удалить
Демонстрационный код для функции удаления выглядит следующим образом:
import java.util.LinkedList;
public class LinkedListTest {
public static void main(String[] a) {
LinkedList list = new LinkedList();
list.offer("头部");
list.offer("中间");
list.offer("尾部");
list.removeFirst(); // 删除头部元素
list.removeLast(); // 删除尾部元素
System.out.println(list);
}
}
Результат выполнения приведенного выше кода:
[середина]
В дополнение к вышеперечисленным методам удаления есть еще следующие методы удаления:
- clear(): очистить связанный список;
- removeFirst(): удалить и вернуть первый элемент;
- removeLast(): удалить и вернуть последний элемент;
- remove(Object o): удалить элемент и вернуться, если он успешен;
- remove(int index): удалить элемент в указанной позиции;
- poll(): удалить и вернуть первый элемент;
- remove(): удаляет и возвращает первый элемент.
3. Изменить
Демонстрационный код модифицированного метода выглядит следующим образом:
import java.util.LinkedList;
public class LinkedListTest {
public static void main(String[] a) {
LinkedList list = new LinkedList();
list.offer("Java");
list.offer("MySQL");
list.offer("DB");
// 修改
list.set(2, "Oracle");
System.out.println(list);
}
}
Результат выполнения приведенного выше кода:
[Java, MySQL, Oracle]
4. Запрос
Демонстрационный код метода запроса выглядит следующим образом:
import java.util.LinkedList;
public class LinkedListTest {
public static void main(String[] a) {
LinkedList list = new LinkedList();
list.offer("Java");
list.offer("MySQL");
list.offer("DB");
// --- getXXX() 获取 ---
// 获取最后一个
System.out.println(list.getLast());
// 获取首个
System.out.println(list.getFirst());
// 根据下标获取
System.out.println(list.get(1));
// peekXXX() 获取
System.out.println("--- peek() ---");
// 获取最后一个
System.out.println(list.peekLast());
// 获取首个
System.out.println(list.peekFirst());
// 根据首个
System.out.println(list.peek());
}
}
Результат выполнения приведенного выше кода:
DB
Java
MySQL
--- peek() ---
DB
Java
Java
5. Траверс
LinkedListМетоды обхода включают следующие три.
Способ обхода первый:
for (int size = linkedList.size(), i = 0; i < size; i++) {
System.out.println(linkedList.get(i));
}
Способ обхода второй:
for (String str: linkedList) {
System.out.println(str);
}
Способ обхода третий:
Iterator iter = linkedList.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
Приложение связанного списка: очередь и стек
1. Реализовать стек со связанным списком
Затем мы используем связанный список для реализации «очереди в порядке поступления». Код реализации выглядит следующим образом:
LinkedList list = new LinkedList();
// 元素入列
list.add("Java");
list.add("中文");
list.add("社群");
while (!list.isEmpty()) {
// 打印并移除队头元素
System.out.println(list.poll());
}
Результат выполнения вышеуказанной программы выглядит следующим образом:
Java
китайский язык
сообщество
2. Реализуйте очередь со связанным списком
Затем мы используем связанный список для реализации «стека» LIFO, код реализации выглядит следующим образом:
LinkedList list = new LinkedList();
// 元素入栈
list.add("Java");
list.add("中文");
list.add("社群");
while (!list.isEmpty()) {
// 打印并移除栈顶元素
System.out.println(list.pollLast());
}
Результат выполнения вышеуказанной программы выглядит следующим образом:
сообщество
китайский язык
Java
Сценарии использования связанных списков
В качестве базовой физической структуры связанный список часто используется для создания многих других логических структур, таких как стек и очередь, которые могут быть реализованы на основе связанного списка.
Так называемая физическая структура означает, что данные могут храниться в физическом пространстве, например, массивы и связанные списки относятся к физическим структурам данных, а логическая структура используется для описания логической связи между данными, которые могут состоять из различных различных физических структур Реализации, такие как очереди и стеки, являются логическими структурами.
Список общих письменных тестовых вопросов
Самый распространенный письменный тестовый вопрос для связанных списков — это инверсия связанных списков.Предыдущая статья"Две реализации реверсирования связанных списков, последняя побеждает 100% пользователей! 》Мы предоставляем 2 метода обращения связанного списка, и в этой статье мы расширим его и предоставим 3 метода обращения связанного списка.
Метод реализации 1: стек
Давайте сначала продемонстрируем конкретный процесс использования стека для реализации инверсии связанного списка, как показано на следующем рисунке.
Все в стеке:Поскольку стек представляет собой структуру данных «первым пришел — последним вышел», процесс его выполнения показан на следующем рисунке:
Окончательный результат выполнения показан на следующем рисунке:
Код реализации выглядит следующим образом:
public ListNode reverseList(ListNode head) {
if (head == null) return null;
Stack<ListNode> stack = new Stack<>();
stack.push(head); // 存入第一个节点
while (head.next != null) {
stack.push(head.next); // 存入其他节点
head = head.next; // 指针移动的下一位
}
// 反转链表
ListNode listNode = stack.pop(); // 反转第一个元素
ListNode lastNode = listNode; // 临时节点，在下面的 while 中记录上一个节点
while (!stack.isEmpty()) {
ListNode item = stack.pop(); // 当前节点
lastNode.next = item;
lastNode = item;
}
lastNode.next = null; // 最后一个节点赋为null（不然会造成死循环）
return listNode;
}
Результат проверки LeetCode показан на следующем рисунке:Можно видеть, что использование метода стека для реализации обратного выполнения связанного списка относительно неэффективно.
Реализация 2: Рекурсия
Точно так же давайте сначала продемонстрируем конкретный процесс этого метода графически, как показано на следующем рисунке.
Код реализации выглядит следующим образом:
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
// 从下一个节点开始递归
ListNode reverse = reverseList(head.next);
head.next.next = head; // 设置下一个节点的 next 为当前节点
head.next = null; // 把当前节点的 next 赋值为 null，避免循环引用
return reverse;
}
Результат проверки LeetCode показан на следующем рисунке:Видно, что этот метод реализации удовлетворил наши потребности с точки зрения эффективности выполнения, и производительность по-прежнему очень высока.
Реализация 3: Цикл
Мы также можем реализовать инверсию связанного списка с помощью цикла, но этому методу не нужно повторно вызывать свой собственный метод, и для этого нужен только цикл Код реализации выглядит следующим образом:
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return null;
// 最终排序的倒序链表
ListNode prev = null;
while (head != null) {
// 循环的下个节点
ListNode next = head.next;
// 反转节点操作
head.next = prev;
// 存储下个节点的上个节点
prev = head;
// 移动指针到下一个循环
head = next;
}
return prev;
}
}
Результат проверки LeetCode показан на следующем рисунке:Как видно из приведенных выше изображений, использование этого метода является текущим оптимальным решением с точки зрения временной и пространственной сложности, которое является более идеальным, чем предыдущие два метода.
Суммировать
В этой статье мы говорили об определении связанного списка, который состоит из двух частей: поля данных и поля указателя. Связанный список можно разделить на: односвязный список, двусвязный список и циклический связанный список, среди которых циклический связанный список может быть дополнительно разделен на одинарный круговой связанный список и двойной круговой связанный список. Из исходного кода JDK видно, что в JavaLinkedListПо сути, это двусвязный список. Мы можем использовать его для реализации очередей или стеков. Наконец, мы рассказали о 3 методах реализации реверсивно связанных списков. Надеюсь, содержание этой статьи будет вам полезно.
Благосостояние в конце статьи: Поиск общедоступной учетной записи «Китайское сообщество Java», чтобы отправить «интервью», чтобы получить последние материалы интервью.