Связанные списки - структура данных #Часть 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", мы можем выполнить следующие действия:

Начнем с начального узла связанного списка.
Мы сравниваем значение, хранящееся в узле, со строкой, переданной в качестве параметра в метод "searchNode". Если они одинаковы, мы нашли искомый узел и возвращаем его.
Если значения не равны, мы переходим к следующему узлу в связанном списке, используя указатель текущего узла.
Мы повторяем шаги 2 и 3 для каждого узла в списке, пока не найдем узел, содержащий искомое значение, или не достигнем конца списка.
Если мы достигаем конца списка и не находим искомый узел, мы возвращаем нулевое значение или сообщение о том, что узел не найден.

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

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;
	}
}