Связанные списки - структура данных #Часть 2/3

RedDeveloper
19.02.2023 13:25
Связанные списки - структура данных #Часть 2/3

Реализация в коде Java

В части 1/3 мы рассказали о концепциях, которые необходимо иметь в виду при разговоре о связанных списках, о двух основных типах и некоторых примерах из реального мира, а теперь в следующих разделах мы реализуем их в коде Java, чтобы увидеть, как это выглядит на самом деле.

Операции:

  • Вставка узла; Когда мы вставляем новый узел в связный список, мы можем вставить его в определенную позицию, в начало или в конец списка.
Пример вставки нового узла в конец списка - Односвязный список
Пример вставки нового узла в конец списка - Односвязный список
  • Поиск узла; Мы передаем данные, а метод возвращает позицию.
    Удаление узла "воздушный шар" - Односвязный список

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

Мы будем следовать следующей структуре для Односвязного списка:

Структура класса

Односвязные списки

  • Вставить новый узел; Для вставки нового узла, как уже упоминалось, у нас есть две возможности. Вставить узел в определенную позицию или в последнюю позицию связанного списка. В данном случае мы рассмотрим только вставку в последнюю позицию.

→ Вставка узла в последнюю позицию связанного списка:

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

У нас есть класс "SinglyLinkedListNode", в котором мы будем выполнять основные операции, и класс, в котором будет храниться связанный список.

public class SinglyLinkedListNode { 
    private Node head;              /* The head of the list */
    private int nNodes;             /* Number of Nodes, we have in the actual list */
    
    public SinglyLinkedListNode() {   /* Constructor method */
      this.head= null;      /* Save the variable that I pass to constructor into data variable of this Node */
      this.nNodes= 0;      /* Don't point to nothing */
    }

    public void insertNodeLast(String data) {
        /*  1--> Allocate the Node
            2--> Put in the data
            3--> Set next as null */
        Node newNode= new Node(data);
        if (this.head!= null) { /* 4.1--> This new node is going to be the last node, so make next of it as null */
            Node auxNode= this.head;

            while (auxNode.getNext()!= null) {
                auxNode= last.getNext();
            }

            /* 5--> Change the next of last node */
            auxNode.setNext(newNode);
            
            this.nNodes++;
        } else { /* 4.2--> If the Linked List is empty, then make the new node as head */
            this.head= newNode;
            this.nNodes++;
        }
    }
}

Во-вторых, у нас есть класс Node, который содержит и объявляет каждый узел из предыдущего класса "SinglyLinkedListNode".

public class Node {
    private String data;                 /* Save my data/info */
    private Node next;              /* Point to next Node */
    
    public Node(String data) {   /* Constructor method */
      this.data= data;      /* Save the variable that I pass to constructor into data variable of this Node */
      this.next= null;      /* Don't point to nothing */
    }

    public String getData() {
        return this.data;
    }
    public void setData(String data) {
        this.data= data;
    }
    public Node getNext() {
        return this.next;
    }
    public void setNext(Node next) {
        this.next= next;
    }
}
  • Поиск узла; Чтобы найти узел в связанном списке, передав строковый параметр методу "searchNode", мы можем выполнить следующие действия:
  1. Начнем с начального узла связанного списка.
  2. Мы сравниваем значение, хранящееся в узле, со строкой, переданной в качестве параметра в метод "searchNode". Если они одинаковы, мы нашли искомый узел и возвращаем его.
  3. Если значения не равны, мы переходим к следующему узлу в связанном списке, используя указатель текущего узла.
  4. Мы повторяем шаги 2 и 3 для каждого узла в списке, пока не найдем узел, содержащий искомое значение, или не достигнем конца списка.
  5. Если мы достигаем конца списка и не находим искомый узел, мы возвращаем нулевое значение или сообщение о том, что узел не найден.
public class SinglyLinkedListNode { 
    private Node head;              /* The head of the list */
    private int nNodes;             /* Number of Nodes, we have in the actual list */
    
    public SinglyLinkedListNode() {   /* Constructor method */
      this.head= null;      /* Save the variable that I pass to constructor into data variable of this Node */
      this.nNodes= 0;      /* Don't point to nothing */
    }

    public Node searchNode(String data) {
		boolean result= false, exit= false;
		Node node_aux= this.head;
        Node node_return= null;
		
		if (node_aux != null) { /* In case the current Node is not null */
			if (node_aux.getData().equalsIngoreCase(data)) { /* Check, if the data of the current Node is equal to the data */
                node_return= node_aux;
			} else {
				while (node_aux != null & !exit) {/* We go through the linked list until we find the data, or reach the end */
					if (node_aux.numEnter.equalsIngoreCase(data)) {
                        node_return= node_aux;
						exit= true;
					} else {
						node_aux= node_aux.getNext();
					}
				}
			}
		}

		return node_return;
	}
}
  • Удалить узел; Чтобы удалить узел из списка, мы должны сначала найти этот узел, а затем указать узел, который указывает на него, на следующий узел, и все!

Пример:

(Список)-> 1 -> 2 -> 4 -> 5 -> null
(Удалить узел) -> 4
(После удаления узла)-> 1 -> 2 -> 5 -> null
Пример GIF
Пример GIF
public class SinglyLinkedListNode { 
    private Node head;              /* The head of the list */
    private int nNodes;             /* Number of Nodes, we have in the actual list */
    
    public SinglyLinkedListNode() {   /* Constructor method */
      this.head= null;      /* Save the variable that I pass to constructor into data variable of this Node */
      this.nNodes= 0;      /* Don't point to nothing */
    }

    public boolean removeNode(Sting data) {
		boolean removeNode= false;

		if (this.head== null) {
			removeNode= false;
		} else {
			Node auxNode= this.head;
			Node auxPreviousNode= null;

			if (auxNode.getData().equalsIgnoreCase(data)) {
				this.head= auxNode.getNext();
				removeNode= true;
			} else {
				while (auxNode!= null & !removeNode) {
					if (auxNode.getData().equalsIgnoreCase(data)) {
						auxPreviousNode.setNext(auxNode.getNext());
						removeNode= true;
					} else {
						auxPreviousNode= auxNode;
						auxNode= auxNode.getNext();
					}
				}
			}
		}

		return removeNode;
	}
}

Мы уже видели примеры этих операций, но их гораздо больше.

В части 3/3 я расскажу о стоимости каждой операции.

Спасибо за ваше время, и если у вас есть какие-либо исправления, пожалуйста, не стесняйтесь писать мне! В заключение

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

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?

20.08.2023 18:21

Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в 2023-2024 годах? Или это полная лажа?".

Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией

20.08.2023 17:46

В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.

Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox

19.08.2023 18:39

Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в частности, магию поплавков и гибкость flexbox.

Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest

19.08.2023 17:22

В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для чтения благодаря своей простоте. Кроме того, мы всегда хотим проверить самые последние возможности в наших проектах!

Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️

18.08.2023 20:33

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

Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL

14.08.2023 14:49

Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип предназначен для представления неделимого значения.