Что такое LinkedList?
Связанный список — это линейная структура данных, состоящая из последовательности элементов, называемых "узлами", где каждый узел указывает на следующий узел в последовательность. Он называется "связанным" списком, потому что элементы связаны друг с другом с помощью указателей или ссылок.
Представление связанного списка.
Каждый узел в связанном списке обычно содержит два компонента:
Данные. Значение или полезные данные узла, представляющие фактическую элемент, хранящийся в списке.
Следующий указатель/ссылка: ссылка на следующий узел в последовательности.
Последний узел в списке обычно указывает на NULL, указывая на конец списка.
Типы связанных списков
Существует несколько типов связанных списков, в том числе:
Односвязный список: Каждый узел имеет элемент данных и ссылку /указатель на следующий узел.
Двусвязный список: каждый узел имеет элемент данных, ссылку/указатель на следующий узел и ссылку/указатель на предыдущий узел.
Круговой связанный список. Аналогично односвязному или двусвязному списку, но последний узел указывает на первый узел, образуя круг.
Основные операции с односвязным списком и их сложность:
Для односвязного списка основные операции включают:
Вставка в начало: O(1) — постоянная временная сложность.
Вставка в конце: O(n) — линейная временная сложность. (O(1), если вы поддерживаете дополнительный указатель на хвост)
Вставка после заданного узла: O(1) — постоянное время, если у вас есть ссылка на узел, в противном случае O (n).
Удаление узла: O(n) — линейная временная сложность, так как вам может потребоваться пройтись по списку, чтобы найти удаляемый узел.
Поиск узла: O(n) — Линейная временная сложность в худшем случае, поскольку вам может потребоваться пройти весь список.
Обход: O(n) — Линейная временная сложность для однократного посещения всех узлов.
Вот базовая реализация односвязного списка в Java:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
private Node head;
public LinkedList() {
this.head = null;
}
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
public void deleteNode(int data) {
if (head == null) {
return;
}
if (head.data == data) {
head = head.next;
return;
}
Node current = head;
while (current.next != null) {
if (current.next.data == data) {
current.next = current.next.next;
return;
}
current = current.next;
}
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
}
public class Main {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.insertAtEnd(10);
linkedList.insertAtEnd(20);
linkedList.insertAtBeginning(5);
linkedList.insertAtEnd(30);
linkedList.display();
linkedList.deleteNode(20);
linkedList.display();
}
}
Случаи использования связанного списка в реальной разработке программного обеспечения.
Связанные списки имеют несколько вариантов использования в различных сценариях разработки программного обеспечения, в том числе:
Динамические структуры данных. Связанные списки обеспечивают эффективный способ управления коллекциями элементов, которые могут динамически увеличиваться или уменьшаться без необходимости изменения размера, как массивы.
Управление памятью: Операционные системы используют связанные списки для управления блоками памяти и отслеживания свободных областей памяти.
Списки воспроизведения музыки и видео. Связанные списки можно использовать для представления списков воспроизведения в медиаплеерах, где каждая песня или видео узел, а указатель «следующий» указывает на следующую песню или видео в плейлисте.
История просмотров: веб-браузеры используют связанные списки для управления историей просмотров, при этом каждая посещенная страница представляет собой узел в списке.
Функции отмены/возврата. Связанные списки можно использовать для реализации функций отмены и повтора в приложениях, где каждое действие хранится в виде узла, а «следующее» и «предыдущее» ” указатели позволяют перемещаться по действиям.
Таблица символов в компиляторах. Связанные списки можно использовать для реализации таблиц символов в компиляторах для хранения переменных, функций и других символов во время синтаксического анализа и генерации кода.
Выбор структуры данных зависит от конкретных требований и варианта использования приложения. Связанные списки особенно полезны, когда требуются частые вставки и удаления, а размер данных может динамически изменяться.
