Въведение в използването на свързани списъци в Java

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

Но как да създадете свързан списък в Java? Нека да разгледаме.

Всеки свързан списък започва със специален възел, който често се нарича "глава", който носи отговорността да посочва началото на списъка по всяко време. Заглавието е важно, защото всеки възел в свързан списък не е необходимо да следва физически своя наследник (което означава, че предшественик и наследник не трябва да са физически съседни).

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

Java програма, предназначена за създаване и манипулиране на свързани списъци, ще има три отличителни раздела; клас възел, клас на свързан списък и драйвер. Въпреки че тези три раздела могат да бъдат комбинирани в един файл, в компютърните науки има принцип на проектиране, известен като „разделяне на грижите“, който всеки разработчик трябва да знае.

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

Първата стъпка при създаването на свързан списък в Java е създаването на клас възел. Класът на възел трябва да има два атрибута; един от атрибутите ще представлява частта от данни на възела, докато другият атрибут ще представлява свързаната част. Класът на възел също трябва да има конструктор, гетъри и сетери.

Свързани: Научете как да създавате класове в Java

Получателите и настройващите ще позволят на други класове (като например класа на свързания списък) да имат достъп до различните възли в свързания списък.

Пример за клас възел

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

публичен клас Node {
private int Данни;
частен възел NextNode;
//constructor
публичен възел () {
Данни = 0;
NextNode = null;
}
// получатели и сетери
public int getData () {
връщане на данни;
}
public void setData (int data) {
Данни = данни;
}
публичен възел getNextNode () {
връщане на NextNode;
}
public void setNextNode (Node nextNode) {
NextNode = nextNode;
}
}

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

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

публичен клас LinkedList {
частна глава на възел;
//constructor
публичен LinkedList () {
Head = null;
}
}

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

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

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

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

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

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

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

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

 // метод за вмъкване на възел отпред
public void insertAtFront (int ключ) {
// създаваме нов възел, използвайки класа node
Node Temp = new Node ();
// проверява дали възелът Temp е създаден успешно
// присвояваме данните, предоставени от потребителя
if (Temp! = null) {
Temp.setData (ключ);
Temp.setNextNode (null);
// проверява дали главата на свързания списък е празна
// присвоява току -що създадения възел на позицията на главата
if (Head == null) {
Head = Temp;
}
// ако възел вече е на позиция глава
// добавяме новия възел към него и го задаваме като глава
иначе {
Temp.setNextNode (Head);
Head = Temp;
}
}
}

The insertAtFront метод в горния пример позволява на потребител да добавя нови възли към даден свързан списък.

Прилагане на вмъкването отпред

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

шофьор от публичен клас {
// изпълнява програмата
публичен static void main (String [] args) {
// създаваме нов свързан списък, наречен List
Списък на LinkedList = нов LinkedList ();
// добавяме всяка стойност в предната част на свързания списък като нов възел
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

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

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

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

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

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

// показване на метода на всички възли
public void displayAllNodes () {
// създаваме нов възел за извикване на възел и го присвояваме на главата на свързания списък
// ако главата има нулева стойност, тогава свързаният списък е празен
Node Temp = Head;
if (Head == null) {
System.out.println ("Списъкът е празен.");
връщане;
}
System.out.println ("Списъкът:");
while (Temp! = null) {
// отпечатваме данните във всеки възел в конзолата (започвайки от главата)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

Сега, когато displayAllNodes методът е добавен към LinkedList class можете да видите свързания списък, като добавите един ред код в класа на драйвера.

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

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

// отпечатваме възлите в свързан списък
List.displayAllNodes (); 

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

Списъкът:

2 4 6 8 10

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

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

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

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

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

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

// търсене на един възел с помощта на ключ
обществен логически findNode (int ключ) {
// създаваме нов възел и го поставяме начело на свързания списък
Node Temp = Head;
// докато текущият възел не е празен
// проверява дали данните му съвпадат с ключа, предоставен от потребителя
while (Temp! = null) {
if (Temp.getData () == ключ) {
System.out.println ("Възелът е в списъка"); 
връщане true;
}
// преминаване към следващия възел
Temp = Temp.getNextNode ();
}
// ако ключът не е намерен в свързания списък
System.out.println ("Възелът не е в списъка"); 
return false;
}

С displayAllNodes метод, потвърдихте, че LinkedList съдържа 5 четни числа от 2 до 10. The findNode горният пример може да потвърди дали едно от тези четни числа е цифрата 4, като просто извикате метода в класа на драйвера и предоставите номера като параметър.

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

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

// проверява дали възел е в свързания списък
List.findNode (4);

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

Възелът е в списъка

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

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

Методът Delete a Node търси даден възел, изтрива този възел и свързва предишния възел с този, който следва възела, който е изтрит.

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

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

public void findAndDelete (int ключ) { 
Node Temp = Head; 
Възел prev = null; 
// проверява дали възелът head съдържа данните 
// и го изтрийте 
if (Temp! = null && Temp.getData () == ключ) { 
Head = Temp.getNextNode (); 
връщане; 
} 
// търсим в другите възли в списъка 
// и го изтрийте 
while (Temp! = null) { 
if (Temp.getNextNode (). getData () == ключ) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (предишен); 
връщане; 
} 
Temp = Temp.getNextNode (); 
} 
} 

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

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

// изтриваме възела, който съдържа данните 4
List.findAndDelete (4);
// отпечатваме всички възли в свързания списък
List.displayAllNodes ();

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

Списъкът:
2 6 8 10

Ако сте стигнали до края на тази статия, ще научите:

• Как да създадете клас възел.
• Как да създадете свързан клас списък.
• Как да попълните свързан клас списък с неговите предварително дефинирани методи.
• Как да създадете клас драйвер и да използвате различните методи на свързан списък, за да постигнете желания резултат.

Свързан списък е само една от многото структури от данни, които можете да използвате за съхраняване, извличане и изтриване на данни. Тъй като имате всичко необходимо, за да започнете, защо не опитате тези примери за себе си в Java?

Как да създавате и извършвате операции с масиви в Java

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

Прочетете Напред

За автора