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

16 августа, 2021 Дядя Влад

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

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

Как работает связанный список?

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

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

Создание связанного списка в Java

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

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

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

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

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

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

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

 
public class Node {
 private int Data;
 private Node NextNode;
 //constructor
 public Node() {
 Data = 0;
 NextNode = null;
 }
 //getters and setters
 public int getData() {
 return Data;
 }
 public void setData(int data) {
 Data = data;
 }
 public Node getNextNode() {
 return NextNode;
 }
 public void setNextNode(Node nextNode) {
 NextNode = nextNode;
 }
 }

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

Пример связанного списка

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

 public class LinkedList {
 private Node Head;
 //constructor
 public LinkedList() {
 Head = null;
 }
 }

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

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

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

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

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

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

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

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

 //insert node at front method
 public void insertAtFront(int key) {
 //create a new node using the node class
 Node Temp = new Node();
 //check if the Temp node was successfully created
 //assign the data that was provides by the user to it
 if(Temp != null) {
 Temp.setData(key);
 Temp.setNextNode(null);

 //check if the head of the linked list is empty
 //assign the node that was just created to the head position
 if(Head == null) {
 Head = Temp;
 }
 //if a node is already at the head position
 //add the new node to it and set it as the head
 else {
 Temp.setNextNode(Head);
 Head = Temp;
 }
 }
 }

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

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

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

 public class Driver {
 //executes the program
 public static void main(String[] args) {
 //create a new linked list called List
 LinkedList List = new LinkedList();
 //add each value to the front of the linked list as a new node
 List.insertAtFront(10);
 List.insertAtFront(8);
 List.insertAtFront(6);
 List.insertAtFront(4);
 List.insertAtFront(2);
 }
 }

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

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

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

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

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

 //display all nodes method
 public void displayAllNodes() {
 //create a new node call Temp and assign it to the head of the linked list
 //if the head has a null value then the linked list is empty
 Node Temp = Head;
 if (Head == null){
 System.out.println("The list is empty.");
 return;
 }
 System.out.println("The List:");

 while(Temp != null) {
 //print the data in each node to the console(starting from the head)
 System.out.print(Temp.getData() + " ");
 Temp = Temp.getNextNode();
 }
 }

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

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

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

 //print the nodes in a linked list
 List.displayAllNodes();

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

Список:

 2 4 6 8 10

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

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

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

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

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

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

 //search for a single node using a key
 public boolean findNode(int key) {
 //create a new node and place it at the head of the linked list
 Node Temp = Head;
 //while the current node is not empty
 //check if its data matches the key provided by the user
 while (Temp != null) {
 if (Temp.getData() == key) {
 System.out.println("The node is in the list");
 return true;
 }
 //move to the next node
 Temp = Temp.getNextNode();
 }
 //if the key was not found in the linked list
 System.out.println("The node is not in the list");
 return false;
 }

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

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

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

 //check if a node is in the linked list
 List.findNode(4);

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

 The node is in the list

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

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

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

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

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

 public void findAndDelete(int key) {
 Node Temp = Head;
 Node prev = null;
 //check if the head node holds the data
 //and delete it
 if (Temp != null && Temp.getData() == key) {
 Head = Temp.getNextNode();
 return;
 }
 //search the other nodes in the list
 //and delete it
 while (Temp != null) {
 if (Temp.getNextNode().getData() == key ) {
 prev = Temp.getNextNode().getNextNode();
 Temp.setNextNode(prev);
 return;
 }
 Temp = Temp.getNextNode();
 }
 }

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

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

 //delete the node that holds the data 4
 List.findAndDelete(4);
 //print all nodes in the linked list
 List.displayAllNodes();

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

 The List:
 2 6 8 10

Теперь вы можете создавать связанные списки на Java

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

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

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