Wprowadzenie do korzystania z list połączonych w Javie

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 węzłów, które są połączone (lub połączone).





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



Jak działa lista połączona?

Każda połączona lista zaczyna się od specjalnego węzła, który często nazywa się „nagłówkiem”, 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.

Tworzenie połączonej listy w Javie

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ą każdy programista powinien znać.



Zasada separacji obaw nakazuje, aby każda sekcja kodu, która odnosi się do konkretnego problemu, była rozdzielona. 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:


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

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.

Przykład połączonej listy

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

public class LinkedList {
private Node Head;
//constructor
public LinkedList() {
Head = 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 kolekcja metod wstawiania jest jednym z powodów, dla których programista może zdecydować się na użycie tej struktury danych zamiast innej struktury danych, takiej jak stosy (która umożliwia wstawianie i usuwanie tylko od góry).

Korzystanie z metody Insert z przodu

Metoda wstawiania na początku, 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, jak wstawić nowe dane na początku listy.

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

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.

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

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ć?

co to za telefon?

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.

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

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.

//print the nodes in a linked list
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.

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

Z wyświetl wszystkie węzły metody, potwierdziłeś, że Połączona lista zawiera 5 liczb parzystych od 2 do 10. The 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.

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

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

The node is in the list

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

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

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

dlaczego bluetooth nie jest dostępny na Macu?
//delete the node that holds the data 4
List.findAndDelete(4);
//print all nodes in the linked list
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:

The List:
2 6 8 10

Teraz możesz tworzyć połączone listy w Javie

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?

Udział Udział Ćwierkać E-mail 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 Powiązane tematy
  • Programowanie
  • Jawa
  • Programowanie
  • Wskazówki dotyczące kodowania
O autorze Kadeisha Kean(21 opublikowanych artykułów)

Kadeisha Kean jest programistą zajmującym się pełnymi stosami oprogramowania i pisarzem technicznym/technologicznym. Ma wyraźną umiejętność upraszczania niektórych z najbardziej złożonych koncepcji technologicznych; produkcja materiału, który może być łatwo zrozumiały dla każdego nowicjusza w dziedzinie technologii. Pasjonuje się pisaniem, tworzeniem ciekawego oprogramowania i podróżowaniem po świecie (poprzez filmy dokumentalne).

Więcej od Kadeishy Kean

Zapisz się do naszego newslettera

Dołącz do naszego newslettera, aby otrzymywać porady techniczne, recenzje, bezpłatne e-booki i ekskluzywne oferty!

Kliknij tutaj, aby zasubskrybować