Въведение в използването на свързани списъци в 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;
}
}

В този пример атрибутът data ще съхранява цели числа. Сега, когато имате клас възел, е време да преминете към свързания списък.

Пример за свързан списък

По -долу е даден пример за свързан списък в Java.

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


Горният код ще създаде свързан клас списък, но без различните му операции, класът може да се разглежда като еквивалент на празна черупка. Свързаната структура от данни от списък има няколко операции, които могат да се използват за попълването й:

• Поставете отпред.
• Поставете в средата.
• Поставете отзад.

Свързани: Как да изграждаме структури от данни с JavaScript ES6 класове

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

Използване на метода Insert at the Front

Методът вмъкване отпред, както подсказва името, вмъква нови данни (или нови възли) в предната част на свързания списък.

Вмъкване отпред Пример за метод

По -долу е даден пример за това как бихте вмъкнали нови данни в предната част на списъка си.

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


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


The Шофьор class (което е името, което често се присвоява на изпълнимия клас в Java), използва класа LinkedList за създаване на свързан списък от пет четни числа. Гледайки кода по -горе, би трябвало лесно да се види, че числото „2“ е на челната позиция в свързания списък. Но как можете да потвърдите това?

windows media player как да завъртате видео

Използване на метода Показване на всички възли

Методът за показване на всички възли е основен метод за свързан списък. Без него разработчикът няма да може да вижда възлите в свързан списък. Той пътува през свързания списък (започвайки от главата), отпечатвайки данните, съхранявани във всеки възел, който формира списъка.

Пример за показване на всички възли

По -долу е даден пример за използване на метода за показване на всички бележки в 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 можете да видите свързания списък, като добавите един ред код към класа на драйвера.

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

По -долу ще видите как бихте използвали метода за показване на всички възли.

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

Изпълнението на горния ред на кода ще произведе следния изход в конзолата:

Списъкът:

2 4 6 8 10

Използване на метода Find Node

Ще има случаи, когато потребителят иска да намери конкретен възел в свързан списък.

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

Следователно, вместо да използвате displayAllNodes метод, по -ефективен метод е да се намери един възел, съдържащ необходимите данни. Ето защо търсенето на метод с единичен възел е важно в структурата на данните на свързания списък.

Пример за метод на намиране на възел

По -долу е даден пример за използване на метода find node.

//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, като просто извикате метода в класа на драйвера и предоставите номера като параметър.

Пример за метода Find Node

По -долу е даден пример за това как бихте използвали метода find node на практика.

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


Горният код ще произведе следния изход в конзолата:

The node is in the list

Използване на метода Delete a Node

Използвайки същия банков пример отгоре, клиент в базата данни на банката може да пожелае да закрие сметката си. Тук методът за изтриване на възел ще бъде полезен. Това е най -сложният метод за свързан списък.

Методът 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();
}
}

Използване на примера за изтриване на възел

По -долу е даден пример за използване на метода за изтриване на възел на практика.

как да пренаредите страници в word 2016

//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? Позволете на масивите лесно да обработват вашите данни.

Прочетете Напред Свързани теми

• Програмиране
• Java
• Програмиране
• Съвети за кодиране

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

Кадейша Кийн е разработчик на софтуер с пълен стек и технически/технологичен писател. Тя има отличителната способност да опростява някои от най -сложните технологични концепции; производство на материал, който може лесно да бъде разбран от всеки начинаещ в технологиите. Тя е запалена по писането, разработването на интересен софтуер и пътуването по света (чрез документални филми).

Още от Kadeisha Kean

Абонирайте се за нашия бюлетин

Присъединете се към нашия бюлетин за технически съвети, рецензии, безплатни електронни книги и изключителни оферти!

Щракнете тук, за да се абонирате