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

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

Но как создать связанный список в 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);  
 }  
}

В Водитель class (это имя, которое часто присваивается исполняемому классу в 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 class, вы можете просмотреть связанный список, добавив одну строку кода в класс драйвера.

Использование примера метода 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();  
}  
}

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

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

мои USB-порты не работают

//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?

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

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

Читать далее Похожие темы

Программирование
Джава
Программирование
Советы по кодированию

Об авторе Кадейша Кин(Опубликовано 21 статья)

Кадейша Кин (Kadeisha Kean) - разработчик программного обеспечения полного стека и автор статей по техническим / технологическим вопросам. У нее отличная способность упрощать некоторые из самых сложных технологических концепций; производить материал, понятный любому новичку в технологии. Она увлечена писательством, разработкой интересного программного обеспечения и путешествиями по миру (с помощью документальных фильмов).

Ещё от Kadeisha Kean

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

Подпишитесь на нашу рассылку, чтобы получать технические советы, обзоры, бесплатные электронные книги и эксклюзивные предложения!

Нажмите здесь, чтобы подписаться