A&DS на Java (серия из 3 частей)
Связанные списки – действительно важные структуры данных, они позволяют нам хранить значения в разных частях памяти и находить их по адресам. Сегодня в этой статье я расскажу о том, как реализовать единый связанный список в java.
давайте создадим наш первый java-файл давайте создадим наш первый java-файл
Внутри давайте начнем с создания класса, который будет представлять узел
package singlyLinkedList;
class Node {
//thats the value(data) that is inside the Node
public int data;
//Thats the pointer inside the Node, every Node
//has a pointer that store the address of the next node
//Here we call this pointers "next"
public Node next;
public void displayNodeData() {
System.out.print( data + " -> ");
}
}
Этот класс будет представлять узел, каждый узел в связанном списке хранит значение, представленное нашими общедоступными данными int в коде, и указатель на следующий узел, который будет представлен нашим общедоступным узлом next в нашем коде. Внутри этого класса мы создали метод, который просто распечатает данные, чтобы в конце мы могли увидеть наши результаты.
Хорошо, теперь внутри нашего класса Односвязный список мы начнем с определения узла, представляющего начало нашего списка, узла head .
public class SinglyLinkedList {
//Its private because we only need to reference head
//inside this class
private Node head; //here head == null
ВАЖНО: глава даже если мы не пишем это явно, java делает это за нас.
Мы будем использовать head в наших методах для ссылки на начало нашего списка (он же наш первый узел), и для итераций мы увидим это сейчас.
Нашим первым методом будет простая вставка, мы будем использовать этот метод для вставки значения в начало списка
public void insertFirst(int data) {
Node newNode = new Node();
newNode.data = data;
newNode.next = head;
head = newNode;
}
Здесь мы сначала создаем новый узел под названием узел Узел узла(); затем мы устанавливаем данные этого узла в параметр данные , который мы передадим в качестве аргумента позже, когда мы его вызовем. В конце мы заставляем новый узел указывать на заголовок (который равен нулю), а затем делаем так, чтобы заголовок указывал на новый узел итак, теперь глава держит адрес этого Новый узел и новый узел указывает на null, который является концом списка.
ВАЖНО: Просто чтобы прояснить ситуацию, если мы вставим первый два раза (как мы собираемся сделать позже), второй новый узел начнет указывать на head, который является адресом первого нового узла |/| а затем head укажет на второй новый узел
head ↓ newNode -> null
быть этим:
head ↓ newNode2 -> newNode -> null
Теперь давайте сделаем наш Удалить первым метод
public void deleteFirst() {
//shifts the first node (head) to be where
//it was pointing (second node)
head = head.next;
}
Этот более простой и по существу, голова указывает на то, что находится рядом с головой. В основном смещает head, чтобы быть вторым узлом, делая его первым узлом.
Прежде чем мы продолжим построение или другие методы, давайте создадим метод Printlink , чтобы вы могли видеть результаты и лучше визуализировать, что делает код.
Вот наш Printlink-список метод
public void printLinkedList() {
Node current = head;
while (current != null) {
current.displayNodeData();
current = current.next;
}
System.out.print("NULL");
}
Мы просто создаем узел с именем текущий , который начинается с заголовка, что означает, что текущий узел начинает указывать на адрес первого узла. Затем мы зацикливаем текущий узел, чтобы в каждом цикле отображались данные нашего узла (с помощью отображения данных узла () , которые мы сделали в нашем классе узлов), и перемещаем текущий узел на следующий узел, проходя через все узлы в связанном списке, пока мы не найдем null (что является концом), после цикла мы просто печатаем “NULL”, чтобы указать конец списка и сделать более четкое представление с печатью.
Теперь давайте создадим еще один java-файл под названием LinkedListMain.java . Это файл, который мы будем выполнять.
package singlyLinkedList;
public class LinkedListMain {
public static void main(String args[]) {
SinglyLinkedList linkedList = new SinglyLinkedList();
linkedList.insertFirst(1);
linkedList.insertFirst(8);
linkedList.insertFirst(5);
linkedList.insertFirst(3);
linkedList.deleteFirst();
//its gonna be 5 -> 8 -> 1 -> NULL
linkedList.printLinkedList();
}
}
Здесь мы собираемся вызвать наши методы, когда вы запустите их, вывод должен быть быть 5 -> 8 -> 1 -> НУЛЕВЫМ
Теперь вы можете протестировать методы так, как вам хочется! Давайте вернемся к созданию наших других методов.
Мы создали методы для вставки в первую очередь и удаления в первую очередь, но если мы хотим поместить что-то на последнее место? Что ж, давайте создадим для этого методы, начиная с Вставка последняя
public void insertLast(int data) {
Node current = head; //start from the first node
//loop until current == null because you are looping
//all the nodes until you find the end (null)
while(current.next != null) {
current = current.next;
}
//insert the newNode next to current
//which now is the final node
Node newNode = new Node();
newNode.data = data;
current.next = newNode;
}
Хорошо, здесь мы начнем с того, что сделаем что-то очень похожее на то, что мы сделали в методе Printlink , мы начинаем с заголовка и цикла, но здесь мы зацикливаемся до тех пор, пока ток не будет указывать на null, а не равен нулю. Потому что при этом мы будем иметь текущий в качестве последнего узла, потому что последний узел – это тот, который указывает на null. Затем мы создаем новый узел и делаем так, чтобы текущий указывал на новый узел так что теперь это последний узел, потому что порядок изменился с
текущий -> ноль
к
текущий -> Новый узел -> нулевой .
После этого мы можем создать наш метод deletelist
public void deleteLast() {
Node current = head;
Node temp = head;
while (current.next != null) {
temp = current;
current = current.next;
}
current = temp;
current.next = null;
}
Здесь мы создаем метод insertLast и создаем точно такой же цикл, но у нас есть что-то другое. Это узел temp , так что мы можем переместить ток в последнюю позицию с помощью нашего цикла, но мы также перемещаем темп рядом, чтобы в конце у нас был ток в последней позиции ток -> ноль но до этого у нас была температура температура -> текущая -> нулевая . Затем мы делаем текущий сдвиг во временную позицию и делаем текущую точку равной нулю.
Ладно, это здорово и все такое, но… что, если мы хотим, например, поместить что-то посередине? Или удалить его? Ну, мы можем создать метод для размещения узла в любом месте ПОСЛЕ другого узла.
Давайте начнем с вставки после `
public void insertAfter(Node after,int data) {
Node current = head;
Node temp = head;
while (temp.data != after.data ) {
temp = current;
current = current.next;
}
Node newNode = new Node();
newNode.data = data;
temp.next = newNode;
newNode.next = current;
}
В вставке После мы снова используем temp и мы делаем похожий цикл, но условие другое. Теперь мы хотим сопоставить временные данные , которые мы зацикливаем, с after.data это узел, который мы собираемся передать нашему методу. Когда цикл заканчивается, у нас есть temp на месте нашего после узла, что означает, что мы собираемся вставить наш новый узел после временного узла, где находится наш текущий узел. После цикла мы создаем новый узел и мы указываем на новый узел и сделайте новый узел указывающим на текущий ` узел.
Теперь у нас есть наш последний метод, метод удаления После
`
public void deleteAfter(Node after) {
Node current = head;
while (current.data != after.data) {
current = current.next;
}
current.next = current.next.next;
}
`
Здесь мы проверяем, является ли current.data | | после.data таким образом, мы можем иметь положение узла после (так же, как мы сделали с temp в последнем). Затем мы просто указываем текущую точку на то, на что она указывала раньше. Пример:
текущий -> узел 1 -> узел 2
После текущего.следующего.следующего.следующего :
текущий -> узел 2
И это все наши методы, реализованные и объясненные. Теперь мы можем проверить их все
package singlyLinkedList;
public class LinkedListMain {
public static void main(String args[]) {
SinglyLinkedList linkedList = new SinglyLinkedList();
linkedList.insertFirst(1);
linkedList.insertFirst(8);
linkedList.insertFirst(5);
//its gonna be 5 -> 8 -> 1 -> NULL
linkedList.insertLast(3);
//now its gonna be 5 -> 8 -> 1 -> 3 -> NULL
Node node = new Node();
node.data = 1;
linkedList.insertAfter(node, 10);
// now its gonna be 5 -> 8 -> 1 -> 10 -> 3 -> NULL
Node node2 = new Node();
node2.data = 8;
linkedList.deleteAfter(node2);
// now its gonna be 5 -> 8 -> 10 -> 3 -> NULL
linkedList.deleteFirst();
//now its gonna be 8 -> 10 -> 3 -> NULL
linkedList.insertFirst(14);
//now its gonna be 14 -> 8 -> 10 -> 3 -> NULL
linkedList.insertLast(40);
// now its gonna be 14 -> 8 -> 10 -> 3 -> 40 -> NULL
linkedList.deleteFirst();
//now its gonna be 8 -> 10 -> 3 -> 40 -> NULL
linkedList.insertLast(56);
//now its gonna be 8 -> 10 -> 3 -> 40 -> 56 -> NULL
linkedList.deleteLast();
// now its gonna be 8 -> 10 -> 3 -> 40 -> NULL
linkedList.printLinkedList();
}
}
Я надеюсь, что вы поняли или, по крайней мере, я мог бы немного помочь вам в обучении. Это моя первая статья, поэтому я, возможно, объяснил или написал не совсем правильно но я постараюсь совершенствоваться по мере того, как буду писать больше! Если вам нужен исходный код, вы можете проверить мой репозиторий в Github там, где я пытаюсь составить список структур данных и алгоритмов, реализованных на java (и, возможно, позже на C), со всем современным или приведенным ниже источником, который является точно таким же кодом, как и выше, я дам некоторые ссылки, которые вы можете проверить подробнее о связанных списках, и все. Хорошей учебы и удачи!
Хорошей учебы и удачи!
package singlyLinkedList;
class Node {
//thats the value(data) that is inside the Node
public int data;
//Thats the pointer inside the Node, every Node
//has a pointer that store the address of the next node
//Here we call this pointers "next"
public Node next;
public void displayNodeData() {
System.out.print( data + " -> ");
}
}
public class SinglyLinkedList {
//Its private because we only need to reference head
//inside this class
private Node head; //here head == null
public void insertFirst(int data) {
Node newNode = new Node();
newNode.data = data;
newNode.next = head;
head = newNode;
}
public void deleteFirst() {
//shifts the first node (head) to be where
//it was pointing (second node)
head = head.next;
}
public void insertLast(int data) {
Node current = head; //start from the first node
//loop until current == null because you are looping
//all the nodes until you find the end (null)
while(current.next != null) {
current = current.next;
}
//insert the newNode next to current
//which now is the final node
Node newNode = new Node();
newNode.data = data;
current.next = newNode;
}
public void deleteLast() {
Node current = head;
Node temp = head;
while (current.next != null) {
temp = current;
current = current.next;
}
current = temp;
current.next = null;
}
public void insertAfter(Node after,int data) {
Node current = head;
Node temp = head;
while (temp.data != after.data ) {
temp = current;
current = current.next;
}
Node newNode = new Node();
newNode.data = data;
temp.next = newNode;
newNode.next = current;
}
public void deleteAfter(Node after) {
Node current = head;
while (current.data != after.data) {
current = current.next;
}
current.next = current.next.next;
}
public void printLinkedList() {
Node current = head;
while (current != null) {
current.displayNodeData();
current = current.next;
}
System.out.print("NULL");
}
}
Хорошей учебы и удачи!
package singlyLinkedList;
public class LinkedListMain {
public static void main(String args[]) {
SinglyLinkedList linkedList = new SinglyLinkedList();
linkedList.insertFirst(1);
linkedList.insertFirst(8);
linkedList.insertFirst(5);
//its gonna be 5 -> 8 -> 1 -> NULL
linkedList.insertLast(3);
//now its gonna be 5 -> 8 -> 1 -> 3 -> NULL
Node node = new Node();
node.data = 1;
linkedList.insertAfter(node, 10);
// now its gonna be 5 -> 8 -> 1 -> 10 -> 3 -> NULL
Node node2 = new Node();
node2.data = 8;
linkedList.deleteAfter(node2);
// now its gonna be 5 -> 8 -> 10 -> 3 -> NULL
linkedList.deleteFirst();
//now its gonna be 8 -> 10 -> 3 -> NULL
linkedList.insertFirst(14);
//now its gonna be 14 -> 8 -> 10 -> 3 -> NULL
linkedList.insertLast(40);
// now its gonna be 14 -> 8 -> 10 -> 3 -> 40 -> NULL
linkedList.deleteFirst();
//now its gonna be 8 -> 10 -> 3 -> 40 -> NULL
linkedList.insertLast(56);
//now its gonna be 8 -> 10 -> 3 -> 40 -> 56 -> NULL
linkedList.deleteLast();
// now its gonna be 8 -> 10 -> 3 -> 40 -> NULL
linkedList.printLinkedList();
}
}
Некоторые ссылки, которые могут вас заинтересовать
A&DS на Java (серия из 3 частей)
Оригинал: “https://dev.to/gmkonan/implementing-singly-linked-lists-in-java-gbh”