Wprowadzenie do korzystania z list połączonych w Javie

Struktura danych wykorzystuje różne predefiniowane metody przechowywania, pobierania i usuwania danych, co prowadzi do tworzenia wydajnych programów. Lista połączona to popularna struktura danych, która składa się z listy połączonych (lub połączonych) węzłów.

Ale jak stworzyć połączoną listę w Javie? Spójrzmy.

Każda połączona lista zaczyna się od specjalnego węzła, który jest często określany jako „nagłówek”, który ma za zadanie zawsze wskazywać początek listy. Nagłówek jest ważny, ponieważ każdy węzeł na połączonej liście nie musi fizycznie następować po swoim następniku (co oznacza, że ​​poprzednik i następca nie muszą fizycznie przylegać do siebie).

Jak każda struktura danych, połączona lista ułatwia tworzenie, pobieranie, wstawianie i niszczenie za pomocą zestawu predefiniowanych funkcji, z których może korzystać każdy programista.

Program w języku Java zaprojektowany do tworzenia i manipulowania listami połączonymi będzie miał trzy odrębne sekcje; klasa węzła, połączona klasa listy i sterownik. Chociaż te trzy sekcje można łączyć w jednym pliku, w informatyce istnieje zasada projektowania znana jako „separacja obaw”, którą powinien znać każdy programista.

Zasada separacji obaw nakazuje, aby każda sekcja kodu, która odnosi się do konkretnego problemu, była oddzielona. Ta zasada pomoże Ci stworzyć czystszy (bardziej czytelny) kod i jest idealna do tworzenia struktur danych.

Pierwszym krokiem w tworzeniu połączonej listy w Javie jest utworzenie klasy węzła. Klasa węzła powinna mieć dwa atrybuty; jeden z atrybutów będzie reprezentował część danych węzła, podczas gdy drugi atrybut będzie reprezentował połączoną część. Klasa węzła powinna również mieć konstruktor, gettery i settery.

Związane z: Dowiedz się, jak tworzyć klasy w Javie

Gettery i settery pozwolą innym klasom (takim jak klasa połączonej listy) na dostęp do różnych węzłów w połączonej liście.

Przykład klasy węzła

Poniżej znajduje się przykład klasy węzła, aby zorientować się, co mamy na myśli:

klasa publiczna Węzeł {
prywatne int Dane;
Węzeł prywatny NextNode;
//constructor
Węzeł publiczny() {
Dane = 0;
Następny węzeł = null;
}
//gettery i setery
public int getData() {
zwróć dane;
}
public void setData (dane int) {
Dane = dane;
}
Węzeł publiczny getNextNode() {
zwróć następny węzeł;
}
public void setNextNode (Node nextNode) {
Następny węzeł = następny węzeł;
}
}

W tym przykładzie atrybut danych będzie przechowywać wartości całkowite. Teraz, gdy masz klasę węzłów, nadszedł czas, aby przejść do połączonej listy.

Poniżej znajduje się przykład połączonej listy w Javie.

public class LinkedList {
prywatna głowa węzła;
//constructor
publiczna lista połączona() {
Głowa = null;
}
}

Powyższy kod utworzy połączoną klasę listy, jednak bez jej różnych operacji, klasa może być postrzegana jako odpowiednik pustej powłoki. Połączona struktura danych listy zawiera kilka operacji, których można użyć do jej wypełnienia:

• Wstawka z przodu.
• Wstawiamy na środku.
• Wstawka z tyłu.

Związane z: Jak budować struktury danych za pomocą klas JavaScript ES6

Połączona lista metod wstawiania jest jednym z powodów, dla których programista może zdecydować się na użycie tych danych strukturę nad inną strukturą danych, taką jak stosy (która umożliwia wstawianie i usuwanie tylko od góry).

Korzystanie z metody Insert z przodu

Metoda wstawiania z przodu, jak sama nazwa wskazuje, wstawia nowe dane (lub nowe węzły) na początku połączonej listy.

Wstaw z przodu Przykład metody

Poniżej znajduje się przykład wstawienia nowych danych na początku listy.

 //wstaw węzeł na początku metody
public void insertAtFront (klucz int) {
//utwórz nowy węzeł za pomocą klasy węzła
Temp węzła = nowy węzeł();
//sprawdź, czy węzeł Temp został pomyślnie utworzony
//przypisz do niej dane, które podał użytkownik
if (Temp != null) {
Temp.setData (klucz);
Temp.setNextNode (null);
//sprawdź, czy nagłówek połączonej listy jest pusty
//przypisz właśnie utworzony węzeł do pozycji głowy
jeśli (głowa == null) {
Głowa = Temp;
}
//jeśli węzeł jest już w pozycji głowy
//dodaj do niego nowy węzeł i ustaw go jako nagłówek
w przeciwnym razie {
Temp.setNextNode (głowica);
Głowa = Temp;
}
}
}

ten wstaw z przodu Metoda w powyższym przykładzie pozwala użytkownikowi dodawać nowe węzły do ​​danej połączonej listy.

Stosowanie wkładki z przodu Przykład

Poniżej znajduje się przykład zastosowania wkładki z przodu.

Klasa publiczna Kierowca {
//wykona program
public static void main (String[] args) {
//utwórz nową połączoną listę o nazwie Lista
LinkedList List = nowa LinkedList();
//dodaj każdą wartość na początku połączonej listy jako nowy węzeł
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

ten Kierowca class (jest to nazwa, która jest często przypisywana do klasy wykonywalnej w Javie), wykorzystuje klasę LinkedList do utworzenia połączonej listy pięciu liczb parzystych. Patrząc na powyższy kod, powinno być łatwo zauważyć, że cyfra „2” znajduje się na czele połączonej listy. Ale jak możesz to potwierdzić?

Korzystanie z metody wyświetlania wszystkich węzłów

Metoda wyświetlania wszystkich węzłów jest podstawową metodą listy połączonej. Bez tego programista nie będzie mógł zobaczyć węzłów na połączonej liście. Przechodzi przez połączoną listę (zaczynając od nagłówka) drukując dane przechowywane w każdym węźle, który tworzy listę.

Przykład metody wyświetlania wszystkich węzłów

Poniżej znajduje się przykład użycia metody wyświetlania wszystkich notatek w Javie.

//wyświetl wszystkie węzły metoda
public void displayAllNodes() {
//utwórz nowe wywołanie węzła Temp i przypisz je do nagłówka połączonej listy
//jeśli nagłówek ma wartość null, to połączona lista jest pusta
Temp węzła = Głowica;
jeśli (głowa == null){
System.out.println("Lista jest pusta.");
powrót;
}
System.out.println("Lista:");
while (Temp != null) {
//wydrukuj dane w każdym węźle do konsoli (zaczynając od nagłówka)
System.out.print (Temp.getData() + " ");
Temp = Temp.getNextNode();
} 
}

Teraz, gdy wyświetl wszystkie węzły metoda została dodana do Połączona lista class możesz wyświetlić połączoną listę, dodając pojedynczy wiersz kodu do klasy sterownika.

Korzystanie z przykładowej metody wyświetlania wszystkich węzłów

Poniżej zobaczysz, jak możesz użyć metody wyświetlania wszystkich węzłów.

//wydrukuj węzły w połączonej liście
List.displayAllNodes(); 

Wykonanie powyższego wiersza kodu da w konsoli następujące dane wyjściowe:

Lista:

2 4 6 8 10

Korzystanie z metody Znajdź węzeł

Będą sytuacje, w których użytkownik będzie chciał znaleźć określony węzeł na połączonej liście.

Na przykład nie byłoby praktyczne, aby bank, który ma miliony klientów, drukował wszystkie dane klientów w swojej bazie danych, gdy muszą zobaczyć tylko dane konkretnego klienta.

Dlatego zamiast używać wyświetl wszystkie węzły metody, bardziej wydajną metodą jest znalezienie pojedynczego węzła zawierającego wymagane dane. Z tego powodu poszukiwanie metody pojedynczego węzła jest ważne w strukturze danych połączonych list.

Znajdź przykład metody węzła

Poniżej znajduje się przykład użycia metody find node.

//wyszukaj pojedynczy węzeł za pomocą klawisza
public boolean findNode (klucz int) {
//utwórz nowy węzeł i umieść go na początku połączonej listy
Temp węzła = Głowica;
//gdy bieżący węzeł nie jest pusty
//sprawdź, czy jego dane pasują do klucza podanego przez użytkownika
while (Temp != null) {
if (Temp.getData() == klucz) {
System.out.println("Węzeł znajduje się na liście"); 
zwróć prawdę;
}
//przejdź do następnego węzła
Temp = Temp.getNextNode();
}
//jeśli klucz nie został znaleziony na połączonej liście
System.out.println("Węzeł nie znajduje się na liście"); 
zwróć fałsz;
}

Z wyświetl wszystkie węzły metody, potwierdziłeś, że Połączona lista zawiera 5 liczb parzystych od 2 do 10. ten findNode Powyższy przykład może potwierdzić, czy jedna z tych parzystych liczb jest cyfrą 4, po prostu wywołując metodę w klasie sterownika i podając liczbę jako parametr.

Korzystanie z przykładu metody Znajdź węzeł

Poniżej znajduje się przykład praktycznego zastosowania metody znajdowania węzłów.

//sprawdź, czy węzeł znajduje się na połączonej liście
List.findNode (4);

Powyższy kod wygeneruje w konsoli następujące dane wyjściowe:

Węzeł znajduje się na liście

Korzystanie z metody usuwania węzła

Korzystając z tego samego przykładu banku z powyższego, klient w bazie banku może chcieć zamknąć swoje konto. Tutaj przyda się metoda usuwania węzła. Jest to najbardziej złożona metoda listy połączonej.

Metoda Delete a Node wyszukuje dany węzeł, usuwa ten węzeł i łączy poprzedni węzeł z tym, który następuje po węźle, który został usunięty.

Przykład metody usuwania węzła

Poniżej znajduje się przykład metody usuwania węzła.

public void findAndDelete (klucz int) { 
Temp węzła = Głowica; 
Węzeł poprzedni = null; 
//sprawdź, czy główny węzeł przechowuje dane 
//i usuń go 
if (Temp != null && Temp.getData() == klucz) { 
Head = Temp.getNextNode(); 
powrót; 
} 
//przeszukaj inne węzły na liście 
//i usuń go 
while (Temp != null) { 
if (Temp.getNextNode().getData() == klucz ) { 
poprzedni = Temp.pobierzNastępnyWęzeł().PobierzNastępnyWęzeł(); 
Temp.setNextNode (poprzedni); 
powrót; 
} 
Temp = Temp.getNextNode(); 
} 
} 

Korzystanie z przykładu metody usuwania węzła

Poniżej znajduje się przykład praktycznego zastosowania metody usuwania węzła.

//usuń węzeł, który przechowuje dane 4
List.findAndDelete (4);
//wydrukuj wszystkie węzły z połączonej listy
List.displayAllNodes();

Użycie dwóch powyższych wierszy kodu we wcześniej istniejącej klasie Driver spowoduje wyświetlenie w konsoli następujących danych wyjściowych:

Lista:
2 6 8 10

Jeśli dotarłeś do końca tego samouczka, dowiesz się:

• Jak stworzyć klasę węzła.
• Jak utworzyć połączoną klasę listy.
• Jak wypełnić klasę połączonej listy jej predefiniowanymi metodami.
• Jak utworzyć klasę sterownika i użyć różnych metod list połączonych, aby osiągnąć pożądany rezultat.

Połączona lista to tylko jedna z wielu struktur danych, których można używać do przechowywania, pobierania i usuwania danych. Skoro masz wszystko, czego potrzebujesz, aby zacząć, dlaczego nie wypróbować tych przykładów w Javie?

Jak tworzyć i wykonywać operacje na tablicach w Javie

Uczysz się Javy? Pozwól, aby tablice z łatwością obsłużyły Twoje dane.

Czytaj dalej

O autorze