Введение в использование связанных списков в Java

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

Но как создать связанный список в Java? Давайте взглянем.

Каждый связанный список начинается со специального узла, который часто называют «головой», который всегда должен указывать на начало списка. Заголовок важен, потому что каждый узел в связанном списке не должен физически следовать за своим преемником (это означает, что предшественник и последователь не должны быть физически смежными).

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

Программа на Java, предназначенная для создания связанных списков и управления ими, будет иметь три отдельных раздела; класс узла, класс связанного списка и драйвер. Хотя эти три раздела можно объединить в один файл, в информатике существует принцип проектирования, известный как «разделение задач», который должен знать каждый разработчик.

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

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

Связанный: Узнайте, как создавать классы на Java

Геттеры и сеттеры позволят другим классам (например, классу связанного списка) получить доступ к различным узлам в связанном списке.

Пример класса узла

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

public class Node {
частные данные int;
частный узел NextNode;
//constructor
public Node () {
Данные = 0;
NextNode = null;
}
// геттеры и сеттеры
public int getData () {
вернуть данные;
}
public void setData (int data) {
Данные = данные;
}
public Node getNextNode () {
return NextNode;
}
public void setNextNode (Node nextNode) {
NextNode = nextNode;
}
}

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

Ниже приведен пример связанного списка на Java.

public class LinkedList {
частный Node Head;
//constructor
public LinkedList () {
Head = null;
}
}

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

• Вставка спереди.
• Вставить посередине.
• Вставка сзади.

Связанный: Как создавать структуры данных с помощью классов JavaScript ES6

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

Использование вставки спереди

Метод вставки в начале, как следует из названия, вставляет новые данные (или новые узлы) в начало связанного списка.

Вставить на переднем плане Пример метода

Ниже приведен пример того, как вы вставляете новые данные в начало списка.

 // вставляем узел в передний метод
public void insertAtFront (int key) {
// создаем новый узел, используя класс узла
Node Temp = новый узел ();
// проверяем, успешно ли создан узел Temp
// присваиваем ему данные, предоставленные пользователем
if (Temp! = null) {
Temp.setData (ключ);
Temp.setNextNode (ноль);
// проверяем, пуст ли заголовок связанного списка
// назначаем только что созданный узел позиции головы
if (Head == null) {
Напор = Температура;
}
// если узел уже находится в позиции головы
// добавляем к нему новый узел и устанавливаем его как голову
еще {
Temp.setNextNode (Голова);
Напор = Температура;
}
}
}

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

Пример применения вставки спереди

Ниже приведен пример того, как вы примените вставку спереди.

public class Driver {
// выполняет программу
public static void main (String [] args) {
// создаем новый связанный список под названием List
LinkedList List = новый LinkedList ();
// добавляем каждое значение в начало связанного списка как новый узел
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

В Водитель class (это имя, которое часто присваивается исполняемому классу в Java), использует класс LinkedList для создания связанного списка из пяти четных чисел. Глядя на приведенный выше код, должно быть легко увидеть, что цифра «2» находится в начале связанного списка. Но как это подтвердить?

Использование метода отображения всех узлов

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

Пример метода отображения всех узлов

Ниже приведен пример использования метода отображения всех заметок в Java.

// отображение всех узлов метод
public void displayAllNodes () {
// создаем новый узел, вызываем Temp и назначаем его в начало связанного списка
// если заголовок имеет нулевое значение, то связанный список пуст
Температура узла = Напор;
if (Head == null) {
System.out.println («Список пуст.»);
возвращение;
}
System.out.println ("Список:");
while (Temp! = null) {
// выводим данные из каждого узла в консоль (начиная с головы)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

Теперь, когда displayAllNodes добавлен метод LinkedList class, вы можете просмотреть связанный список, добавив одну строку кода в класс драйвера.

Использование примера метода Display All Nodes

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

// выводим узлы в связанный список
List.displayAllNodes (); 

Выполнение приведенной выше строки кода приведет к следующему выводу в консоли:

Список:

2 4 6 8 10

Использование метода поиска узла

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

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

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

Пример метода поиска узла

Ниже приведен пример использования метода поиска узла.

// ищем единственный узел с помощью ключа
public boolean findNode (int key) {
// создаем новый узел и помещаем его в начало связанного списка
Температура узла = Напор;
// пока текущий узел не пуст
// проверяем, соответствуют ли его данные ключу, предоставленному пользователем
while (Temp! = null) {
if (Temp.getData () == key) {
System.out.println («Узел в списке»); 
вернуть истину;
}
// переход к следующему узлу
Temp = Temp.getNextNode ();
}
// если ключ не найден в связанном списке
System.out.println («Узел нет в списке»); 
вернуть ложь;
}

С displayAllNodes метод, вы подтвердили, что LinkedList содержит 5 четных чисел от 2 до 10. В findNode В приведенном выше примере можно подтвердить, является ли одно из этих четных чисел числом 4, просто вызвав метод в классе драйвера и указав это число в качестве параметра.

Использование примера метода поиска узла

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

// проверяем, находится ли узел в связанном списке
List.findNode (4);

Приведенный выше код выдаст в консоли следующий вывод:

Узел находится в списке

Использование метода удаления узла

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

Метод Delete a Node выполняет поиск заданного узла, удаляет этот узел и связывает предыдущий узел с тем, который следует за удаленным узлом.

Пример удаления метода узла

Ниже приведен пример метода удаления узла.

public void findAndDelete (int key) { 
Температура узла = Напор; 
Node prev = null; 
// проверяем, хранит ли головной узел данные 
// и удалим 
if (Temp! = null && Temp.getData () == key) { 
Head = Temp.getNextNode (); 
возвращение; 
} 
// ищем другие узлы в списке 
// и удалим 
while (Temp! = null) { 
if (Temp.getNextNode (). getData () == key) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (предыдущий); 
возвращение; 
} 
Temp = Temp.getNextNode (); 
} 
} 

Использование примера метода удаления узла

Ниже приведен пример использования метода удаления узла на практике.

// удаляем узел, содержащий данные 4
List.findAndDelete (4);
// выводим все узлы связанного списка
List.displayAllNodes ();

Использование двух строк кода выше в уже существующем классе Driver приведет к следующему выводу в консоли:

Список:
2 6 8 10

Если вы дочитали до конца этой обучающей статьи, вы узнаете:

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

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

Как создавать и выполнять операции с массивами в Java

Изучаете Java? Позвольте массивам с легкостью обрабатывать ваши данные.

Читать далее

Об авторе