linked list java linked list implementation java examples
W tym samouczku wyjaśniono, czym jest struktura danych listy połączonej w języku Java oraz jak tworzyć, inicjować, implementować, przeglądać, odwracać i sortować listę połączoną z językiem Java:
W Javie LinkedList to struktura danych przechowująca elementy w nieciągłej lokalizacji. Jest to liniowa struktura danych.
Każdy element danych nazywany jest „węzłem”, a każdy węzeł ma część danych i część adresową. Część adresowa przechowuje łącze do następnego węzła w LinkedList.
=> Odwiedź tutaj, aby zobaczyć serię szkoleń Java dla wszystkich.
Czego się nauczysz:
- LinkedList w Javie
- Klasa LinkedList w języku Java
- Jak utworzyć połączoną listę w Javie
- Implementacja listy połączonej w Javie
- Przeglądanie / drukowanie listy połączonej w Javie
- Metody LinkedList
- Odwróć połączoną listę w Javie
- Sortuj połączoną listę w Javie
- Usuń duplikaty
- Lista połączona cyklicznie w języku Java
- Java 8 LinkedList
- Często Zadawane Pytania
- Wniosek
LinkedList w Javie
Poniżej podano ogólny układ LinkedList:
Jak pokazano na powyższej reprezentacji LinkedList, każdy element w LinkedList to „Węzeł”. Każdy węzeł ma dwie części, pierwsza część przechowuje dane, a druga część zawiera odniesienie, wskaźnik lub adres następnego węzła w LinkedList.
jak napisać dobry przypadek testowy
To ustawienie jest konieczne, ponieważ dane w LinkedList są przechowywane w nieciągłych lokalizacjach, w przeciwieństwie do Arrays.
„Head” obiektu LinkedList to wskaźnik zawierający adres pierwszego elementu w LinkedList. Ostatnim węzłem w LinkedList jest ogon. Jak pokazano na powyższym rysunku, część adresu ostatniego węzła w LinkedList jest ustawiona na „Null”, co oznacza koniec LinkedList.
Powyższy diagram przedstawia „ Lista połączona pojedynczo ”, Który przechowuje adres tylko następnego węzła w LinkedList.
Istnieje inna wersja znana jako „ Lista podwójnie połączona ”Którego każdy węzeł składa się z trzech części:
- Adres, odniesienie lub wskaźnik do poprzedniego elementu w LinkedList.
- Część danych
- Adres, odniesienie lub wskaźnik do następnego elementu w LinkedList.
Poprzedni adres pierwszego elementu w LinkedList zostanie ustawiony na Null, podczas gdy następny wskaźnik ostatniego elementu w LinkedList zostanie ustawiony na Null.
Reprezentacja listy podwójnie połączonej:
Jak pokazano na powyższej ilustracji, każdy węzeł w podwójnie połączonej liście ma wskaźniki do poprzedniego i następnego węzła (w ten sposób przedstawione bez strzałek). Poprzedni wskaźnik pierwszego węzła wskazuje na wartość null, podczas gdy następny wskaźnik ostatniego węzła wskazuje na wartość null.
W tym samouczku LinkedList zajmiemy się głównie listą pojedynczo połączoną. W następnym samouczku omówimy listę podwójnie połączoną.
Klasa LinkedList w języku Java
W Javie połączona lista jest implementowana przez „ Połączona lista ' klasa. Ta klasa należy do „ java.util ”Pakiet. Klasa LinkedList implementuje interfejsy List i Deque oraz dziedziczy klasę AbstractList.
Poniżej podano hierarchię klas klasy LinkedList.
Powyższy diagram przedstawia hierarchię klasy LinkedList. Jak pokazano, klasa LinkedList implementuje interfejsy List i Deque.
Jak już wspomniano, klasa LinkedList jest częścią „ java.util ”Pakiet. Dlatego powinieneś móc używać klasy LinkedList w swoim programie, włączając do programu jedną z poniższych instrukcji.
import java.util.*;
Lub
import java.util.LinkedList;
Bazując na powyższej hierarchii, typowa definicja klasy LinkedList wygląda następująco:
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable
Poniżej wymieniono niektóre cechy klasy LinkedList, o których należy pamiętać:
- Ta klasa nie jest zsynchronizowana.
- Pozwala na zduplikowane wartości.
- Zachowuje zamówienie reklamowe.
- Ponieważ elementy nie muszą być przesuwane podczas przesuwania, manipulacja elementami w nim jest szybsza.
- Ta klasa może służyć do implementowania stosu, kolejki i listy.
Jak utworzyć połączoną listę w Javie
Zanim przejdziemy do tworzenia listy połączonej w Javie, omówmy najpierw węzeł połączonej listy w Javie.
Jak już wspomniano, połączona lista składa się z węzłów. Tak więc w Javie możemy reprezentować LinkedList jako klasę z jej Węzłem jako oddzielną klasą. Stąd ta klasa będzie miała odniesienie do typu Node.
Jest to pokazane poniżej:
class LinkedList { Node head; // list head //node - linkedlist class Node { int data; Node next; Node(int d) { data = d; } //constructor to create a new node } }
Aby utworzyć obiekt typu LinkedList, istnieją dwa główne konstruktory w następujący sposób:
# 1) LinkedList ()
Ogólna składnia tego konstruktora to:
LinkedList linkedList = new LinkedList();
Powyższa instrukcja tworzy pustą LinkedList.
Na przykład,
LinkedList l_list = new LinkedList();
Spowoduje to utworzenie pustej połączonej listy o nazwie l_list.
# 2) LinkedList (Kolekcja c)
Ogólna składnia to:
LinkedList linkedList = new LinkedList (Collection c);
Powyższa instrukcja tworzy LinkedList z elementami z kolekcji c jako elementami początkowymi.
Podobnie jak inne struktury danych list, które już widzieliśmy, połączoną listę można również zainicjować za pomocą metody add, metody Arrays.asList () lub używając konstruktora z kolekcją jako argumentem.
Implementacja listy połączonej w Javie
Poniżej podano prosty przykład struktury danych LinkedList w Javie. W tym przykładzie implementacji użyjemy metody add i asList do zainicjowania obiektów LinkedList.
import java.util.*; public class Main{ public static void main(String[] args) { //create a LinkedList object and initialize it with Array elements converted to list LinkedList intList = new LinkedList<>(Arrays.asList(10,20,30,40,50)); //print the LinkedList just created System.out.println('Contents of first LinkedList: ' + intList); //create an empty list LinkedList colorsList = new LinkedList<>(); //add elements to the linkedList using add method. colorsList.add('Red'); colorsList.add('Green'); colorsList.add('Blue'); colorsList.add('Cyan'); colorsList.add('Magenta'); // print the LinkedList System.out.println('
Contents of second LinkedList: ' + colorsList); } }
Wynik:
Zawartość pierwszego LinkedList: [10, 20, 30, 40, 50]
Zawartość drugiej listy LinkedList: [czerwony, zielony, niebieski, cyjan, magenta]
Powyższy program przedstawia tworzenie i inicjalizację LinkedList. Najpierw tworzymy LinkedList typu Integer i udostępniamy tablicę liczb całkowitych przekonwertowanych na listę przy użyciu metody asList jako wartości początkowe dla LinkedList.
Następnie tworzymy pustą LinkedList typu String, a następnie za pomocą metody add dodajemy wartości do LinkedList.
Na koniec wyświetlamy oba obiekty LinkedList jako ciąg.
Przeglądanie / drukowanie listy połączonej w Javie
Aby wydrukować zawartość lub przeprowadzić jakiekolwiek operacje na elementach LinkedList, musisz przejść przez jej elementy. Widzieliśmy już te metody w naszych poprzednich samouczkach. W tej sekcji omówimy przykłady każdego z nich w odniesieniu do LinkedList.
Korzystanie z pętli for
import java.util.LinkedList; class Main { public static void main(String[] args) { // Create a LinkedList and initialize it LinkedList colorList = new LinkedList<>(); colorList.add('Red'); colorList.add('Green'); colorList.add('Blue'); // Using for loop,print the contents of the LinkedList System.out.println('LinkedList elements using for loop:'); for(int i=0; i Wynik:
Elementy LinkedList używające pętli for:
Czerwony Zielony Niebieski
Korzystanie z pętli forEach
import java.util.LinkedList; class Main { public static void main(String[] args) { // Create a LinkedList and initialize it LinkedList colorList = new LinkedList<>(); colorList.add('Red'); colorList.add('Green'); colorList.add('Blue'); // Using forEach loop,print the contents of the LinkedList System.out.println('LinkedList elements using forEach loop:'); for(String color:colorList) { System.out.print(color + ' '); } } }
Wynik:
Elementy LinkedList używające pętli forEach:
Czerwony Zielony Niebieski
Korzystanie z Iteratora
import java.util.*; public class Main{ public static void main(String args[]){ //declare a LinkedList object LinkedList l_list=new LinkedList(); //Add elements to LinkedList l_list.add('Red'); l_list.add('Green'); l_list.add('Blue'); l_list.add('Yellow'); //declare an iterator for the LinkedList Iterator itr=l_list.iterator(); System.out.println('The contents of Linked List:'); //Iterate through the LinkedList using Iterator and print its elements while(itr.hasNext()){ System.out.print(itr.next() + ' '); } } }
Wynik:
Zawartość listy połączonej:
Czerwony Zielony Niebieski Żółty
urządzenie wirtualne modułu równoważenia obciążenia typu open source
Metody LinkedList
Klasa LinkedList udostępnia interfejs API obsługujący różne metody manipulowania listą LinkedList. Poniżej zestawiliśmy tabelarycznie metody w interfejsie API LinkedList.
Omówimy główne operacje / metody w następnej sekcji.
metoda Prototyp Opis Jasny void clear () Usuwa wszystkie elementy z listy. Dodaj add boolean (E e) Dodaj określony element do LinkedList void add (int index, E element) Dodaj element pod podanym indeksem w LinkedList Dodać wszystko boolean addAll (kolekcja c) Dodaje elementy danej kolekcji c na końcu LinkedList. boolean addAll (indeks int, kolekcja c) Dodaje elementy danej kolekcji c pod określonym indeksem w LinkedList addFirst void addFirst (E e) Dodaj podany element jako pierwszy element do LinkedList. addLast void addLast (E e) Dołącz dany element na końcu listy. Klonuj Klon obiektu () Tworzy płytką kopię LinkedList Zawiera Boolean zawiera (obiekt o) Sprawdza, czy lista zawiera określone elementy; jeśli tak, zwraca prawdę. descendingIterator Iterator malejącoIterator () Zwraca iterator w odwrotnej kolejności dla LinkedList. Element Element E () Zwraca element na początku listy. Otrzymać E get (indeks int) Pobiera element o określonym indeksie. getFirst E getFirst () Pobiera pierwszy element z LinkedList. getLast E getLast () Pobiera ostatni element z LinkedList. indeks Int indexOf (Object o) Znajdź indeks pierwszego wystąpienia podanych elementów na liście i zwróć indeks. -1, jeśli nie znaleziono elementu. lastIndexOf Int lastIndexOf (obiekt o) Zwraca pozycję ostatniego wystąpienia danego elementu w LinkedList; -1, jeśli dany element nie jest obecny listIterator ListIterator listIterator (indeks int) Zwraca listIterator z określonego indeksu w linkedlist. Oferta oferta logiczna (E e) Dodaje podany element jako ostatni element (koniec) w LinkedList. offerFirst Oferta logiczna First (E e) Dodaje podany element jako pierwszy element w LinkedList. offerLast Oferta logicznaOstatni (E e) Dodaj dany element e na końcu LinkedList. Zerkać E peek () Zwraca nagłówek listy bez jej usuwania. peekFirst E peekFirst () Zwraca pierwszy element z listy. zwraca wartość null, jeśli lista jest pusta. peekLast E peekLast () Zwraca ostatni element lub wartość null, jeśli lista jest pusta. Nie usuwa elementu. Głosowanie E ankieta () Zwraca nagłówek LinkedList, a także usuwa go. pollFirst E pollFirst () Zwraca i usuwa pierwszy element z listy; zwraca wartość null, jeśli lista jest pusta. ankietaLast E ankietaLast () Zwraca i usuwa ostatni element z listy; zwraca wartość null, jeśli lista jest pusta. Muzyka pop E pop () Zdejmuje element z reprezentacji stosu LinkedList. Pchać Pchnięcie Pustki (E e) Wypycha lub wstawia element do reprezentacji stosu LinkedList. Usunąć E usuń () Usuwa i zwraca nagłówek LinkedList. E usuń (indeks int) Usuwa element o podanym indeksie z LinkedList. boolean remove (Object o) Usuwa pierwsze wystąpienie danego elementu z LinkedList. removeFirst E usuńFirst () Zwraca i usuwa pierwszy element z listy. removeFirstOccurence boolean removeFirstOccurrence (Object o) Usuwa pierwsze wystąpienie danego elementu z listy podczas przechodzenia przez listę od początku do końca. usuńLast E usuńOstatni () Zwraca ostatni element w LinkedList, a także usuwa go. removeLastOccurence boolean removeLastOccurrence (Object o) Usuwa ostatnie wystąpienie danego elementu z LinkedList podczas przechodzenia od początku do końca Zestaw Zbiór E (indeks int, element E) Ustawia dany element pod podanym indeksem. Zastępuje bieżący element nowym. Rozmiar Rozmiar int () Zwraca rozmiar lub liczbę elementów w LinkedList toArray Obiekt [] toArray () Konwertuje LinkedList na tablicę zawierającą wszystkie elementy listy w odpowiedniej kolejności T [] toArray (T [] a) Konwertuje LinkedList na tablicę z typem środowiska uruchomieniowego takim samym jak argument a.
Poniższy program Java demonstruje różne metody, które wymieniliśmy powyżej.
import java.util.*; public class Main { public static void main(String args[]) { //create a linked list LinkedList l_list = new LinkedList(); // Add elements to linkedList using various add methods l_list.add('B'); l_list.add('C'); l_list.addLast('G'); l_list.addFirst('A'); l_list.add(3, 'D'); l_list.add('E'); l_list.add('F'); //print the linkedList System.out.println('Linked list : ' + l_list); //Create and initialize an ArrayList ArrayList aList = new ArrayList<>(); aList.add('H'); aList.add('I'); //add the ArrayList to linkedList using addAll method l_list.addAll(aList); //print the linkedList System.out.println('Linked list after adding ArrayList contents: ' + l_list); // use various remove methods to remove elements from linkedList l_list.remove('B'); l_list.remove(3); l_list.removeFirst(); l_list.removeLast(); //print the altered list System.out.println('Linked list after deletion: ' + l_list); // use contains method to check for an element in the linkedList boolean ret_value = l_list.contains('G'); //print the results of contains method if(ret_value) System.out.println('List contains the element 'G' '); else System.out.println('List doesn't contain the element 'G''); // use size methods to return Number of elements in the linked list int size = l_list.size(); System.out.println('Size of linked list = ' + size); // Get and set elements from linked list Object element = l_list.get(3); System.out.println('Element returned by get() : ' + element); l_list.set(3, 'J'); System.out.println('Linked list after change : ' + l_list); //convert linkedList to Array using toArray methods String [] list_array = l_list.toArray(new String[l_list.size()]); System.out.println('Array obtained from linked List:' + Arrays.toString(list_array)); } }
Wynik:
Lista połączona: [A, B, C, D, G, E, F]
Powiązana lista po dodaniu zawartości ArrayList: [A, B, C, D, G, E, F, H, I]
Powiązana lista po usunięciu: [C, D, E, F, H]
Lista nie zawiera elementu „G”
Rozmiar połączonej listy = 5
Element zwracany przez get (): F
Lista połączona po zmianie: [C, D, E, J, H]
Tablica uzyskana z połączonej listy: [C, D, E, J, H]
Powyższy program demonstruje różne metody klasy LinkedList. Najpierw deklarujemy LinkedList typu String. Następnie używamy różnych wersji metody add, takich jak add, andFirst, addLast, addAll itp., Aby wypełnić LinkedList wartościami.
Tutaj możemy dodać element bezpośrednio na końcu listy lub dodać element na określonej pozycji na liście.
Używamy również metody addFirst, aby dodać element na początku listy i addLast, aby dodać element na końcu listy. Następnie wykonujemy operacje usuwania na LinkedList, takie jak remove, removeFirst, removeLast itp.
W przypadku metody remove możemy określić element do usunięcia lub określić indeks lub pozycję w LinkedList, w której element ma zostać usunięty. Metody removeFirst i removeLast usuwają odpowiednio pierwszy i ostatni element z listy.
Następnie przeszukujemy listę pod kątem konkretnego elementu za pomocą metody zawiera. Następnie używamy metody size (), aby pobrać rozmiar lub długość LinkedList. Następnie używamy metod get / set, aby pobrać wartość z określonego indeksu na liście, a następnie zastąpić wartość na określonej pozycji na liście.
Na koniec konwertujemy LinkedList na Array przy użyciu metody toArray.
Odwróć połączoną listę w Javie
Aby odwrócić połączoną listę w Javie, używamy metody „descendingIterator ()”, która zwraca odwrotny iterator dla listy. Następnie możemy użyć tego iteratora do przechodzenia przez listę i elementy wyświetlania.
Poniższy program odwraca połączoną listę za pomocą metody descendingIterator ().
import java.util.*; public class Main{ public static void main(String args[]){ //create a LinkedList object LinkedList l_list=new LinkedList(); l_list.add('Pune'); l_list.add('Mumbai'); l_list.add('Nagpur'); System.out.println('Linked List : ' + l_list); System.out.println('Linked List in reverse order:'); //use descendingIterator method to get a reverse iterator Iterator iter=l_list.descendingIterator(); //traverse the list using iterator and print the elements. while(iter.hasNext()) { System.out.print(iter.next() + ' '); } } }
Wynik:
Powiązana lista: [Pune, Mumbai, Nagpur]
Lista połączona w odwrotnej kolejności:
Nagpur Mumbai Pune
W powyższym programie deklarujemy połączoną listę, a następnie ją drukujemy. Następnie otrzymujemy odwrotny iterator, a następnie przechodzimy przez listę używając go i wyświetlamy każdy element. Dane wyjściowe pokazują połączoną zawartość listy, najpierw w kolejności dodawania elementów, a następnie dane wyjściowe pokazują zawartość w odwrotnej kolejności.
Sortuj połączoną listę w Javie
Obiekty klasy LinkedList można sortować za pomocą metody Collections.sort (). Ta metoda zapewnia dwie wersje z lub bez użycia komparatora. Gdy metoda Collections.sort () jest wywoływana bez komparatora, zbiór jest sortowany w kolejności naturalnej.
Kiedy komparator jest używany z tą metodą, możemy zdefiniować własne kryteria sortowania, zastępując metodę compareTo.
Poniższy program Java sortuje LinkedList za pomocą Collections.sort (). Tutaj sortujemy tablice przy użyciu naturalnego porządku, a także za pomocą komparatora.
import java.util.*; public class Main{ public static void main(String args[]) { // create and initialize the LinkedList object LinkedList l_list = new LinkedList<>(); l_list.add('Jan'); l_list.add('Feb'); l_list.add('Mar'); l_list.add('Apr'); l_list.add('May'); l_list.add('Jun'); //print original unsorted linkedlist System.out.println('Original LinkedList (unsorted): ' + l_list); // sort LinkedList with Collecitons.sort() method in natural order Collections.sort(l_list); System.out.println('
LinkedList (sorted in natural order): ' + l_list); // sort LinkedList using Collection.sort() and Comparator in Java Collections.sort(l_list, new Comparator() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } } ); System.out.println('LinkedList (sorted using Comparator): ' + l_list); } }
Wynik:
Oryginalna lista LinkedList (nieposortowana): [sty, lut, mar, kwi, maj, cze]
LinkedList (posortowane w kolejności naturalnej): [Kwi, Lut, Sty, Cze, Mar, Maj]
LinkedList (posortowane przy użyciu komparatora): [kwiecień, luty, styczeń, czerwiec, marzec, maj]
Usuń duplikaty
Aby usunąć duplikaty, musisz przejść przez każdy węzeł i porównać go z następnym. Jeśli oba węzły są takie same, pomijamy jeden węzeł i przechodzimy do następnego.
W ten sposób, po przejściu przez każdy węzeł i pozbyciu się zduplikowanych węzłów, otrzymamy wynikową listę bez żadnych zduplikowanych elementów.
Poniżej podano program w języku Java do usuwania duplikatów.
class LinkedList_Duplicate { //A class to represent node in linkedlist class Node{ int data; Node next; public Node(int data) { this.data = data; this.next = null; } } //Initially the head and tail of the linked list set to null public Node head = null; public Node tail = null; //add a new node to the linkedlist public void addNode(int data) { //Create new node Node newNode = new Node(data); //If list is empty set head and tail to new node if(head == null) { head = newNode; tail = newNode; } else { // add newNode after the tail tail.next = newNode; //newNode is now the tail or last element tail = newNode; } } //scans the linkedlist and removes duplicate nodes public void removeDuplicateNodes() { //Head is the current node Node current = head, index = null, temp = null; //head = null means list is empty if(head == null) { return; } //traverse through the list else { while(current != null){ //temp node points to previous node to index. temp = current; //Index will point to node next to current index = current.next; while(index != null) { //Check if current node's data is equal to index node's data if(current.data == index.data) { //since node is duplicate skip index and point to next node temp.next = index.next; } else { //Temp will point to previous node of index. temp = index; } index = index.next; } current = current.next; } } } //print the linked list public void print() { //Node current will point to head Node current = head; if(head == null) { System.out.println('List is empty'); return; } while(current != null) { //Print each node by incrementing pointer System.out.print(current.data + ' '); current = current.next; } System.out.println(); } }class Main{ public static void main(String[] args) { LinkedList_Duplicate l_List = new LinkedList_Duplicate(); //Add data to the list l_List.addNode(1); l_List.addNode(1); l_List.addNode(2); l_List.addNode(3); l_List.addNode(5); l_List.addNode(2); l_List.addNode(1); l_List.addNode(1); //print the original list System.out.println('Original Linkedlist: '); l_List.print(); //Removes duplicate nodes l_List.removeDuplicateNodes(); //print the altered list without duplicates System.out.println('LinkedList after removing duplicates: '); l_List.print(); } }
Wynik:
Oryginalna lista połączona:
1 1 2 3 5 2 1 1
LinkedList po usunięciu duplikatów:
1 2 3 5
W powyższym programie mamy połączoną klasę listy utworzoną w celu usunięcia duplikatów. Mamy również klasę definiującą każdy węzeł. Innymi słowy, węzły na liście są obiektami tego węzła klasy. Mamy metodę dodawania węzła do połączonej listy.
Następnie w metodzie removeDuplicate przechodzimy przez każdy węzeł na połączonej liście zaczynając od nagłówka i porównujemy każdy kolejny węzeł pod kątem duplikatu. Jeśli zostanie znaleziony duplikat, pomijamy ten węzeł i przechodzimy do następnego.
W ten sposób ist jest budowany przez pomijanie zduplikowanych węzłów, a zmieniona lista jest drukowana za pomocą metody print ().
Lista połączona cyklicznie w języku Java
Okrągła lista połączona to lista, której koniec lub ostatni węzeł jest połączony z powrotem z węzłem głównym lub pierwszym.
Poniższy diagram przedstawia listę połączoną cyklicznie w języku Java.
Jak pokazano na powyższym diagramie, część adresowa ostatniego węzła lub końca połączonej listy nie jest ustawiona na zero. Zamiast tego wskazuje z powrotem na pierwszy węzeł lub początek listy, tworząc w ten sposób okrągłą listę połączoną.
Poniższy program implementuje cyklicznie połączoną listę, w której musimy manipulować poszczególnymi węzłami połączonej listy.
class CircularLinkedList { //Node definition for circular linked list public class Node{ int data; Node next; public Node(int data) { this.data = data; } } //Initially head and tail pointers point to null public Node head = null; public Node tail = null; //add new node to the circular linked list public void add(int data){ //Create new node Node newNode = new Node(data); //check if list is empty if(head == null) { //head and tail point to same node if list is empty head = newNode; tail = newNode; newNode.next = head; } else { //tail points to new node if list is not empty tail.next = newNode; //New node becomes new tail. tail = newNode; //tail points back to head tail.next = head; } } //Display the nodes in circular linked list public void displayList() { Node current = head; if(head == null) { System.out.println('The List is empty'); } else { System.out.println('Circular linked list nodes: '); do{ //Print each node of the linked list System.out.print(current.data + ' '); current = current.next; }while(current != head); System.out.println(); } } } class Main{ public static void main(String[] args) { //create a CircularLinkedList object CircularLinkedList c_list = new CircularLinkedList(); //Add data to the list c_list.add(10); c_list.add(20); c_list.add(30); c_list.add(40); //Display the nodes in circular linked list c_list.displayList(); } }
Wynik:
Węzły listy połączone kołowo:
10 20 30 40
najlepsze darmowe oprogramowanie bazy danych dla systemu Windows
Java 8 LinkedList
Chociaż nie ma więcej funkcji dodanych specjalnie do klasy LinkedList w Javie 8, nadal wprowadzono strumienie do manipulowania danymi.
Poniższy program pokazuje użycie strumienia Java 8 do wyświetlania LinkedList.
import java.util.LinkedList; import java.util.List; public class Main { public static void main(String[] args) { //create a LinkedList and initialize it to values List colorsList = new LinkedList<>(); colorsList.add('Red'); colorsList.add('Green'); colorsList.add('Blue'); colorsList.add('Cyan'); colorsList.add('Magenta'); //convert List to stream & print it System.out.println('The contents of LinkedList:'); colorsList.stream().forEach(System.out::println); } }
Wynik:
Zawartość LinkedList:
Netto
Zielony
niebieski
Cyjan
Magenta
Często Zadawane Pytania
P # 1) Kiedy lista połączona jest używana w Javie?
Odpowiedź: Ponieważ jest szybszy niż zbiory, takie jak ArrayList, w operacjach modyfikacji, powinien być używany w aplikacjach, które wymagają częstych operacji dodawania / usuwania. W przypadku aplikacji, które mają głównie dane tylko do odczytu, można użyć kolekcji ArrayList lub podobnych.
Pytanie nr 2) Co to jest ListNode?
Odpowiedź: ListNode to podstawowa klasa skojarzona z połączoną listą w języku Java i reprezentuje informacje skojarzone z pojedynczym elementem lub węzłem. Każdy ListNode składa się z danych i wskaźnika lub odwołania do następnego elementu.
Pytanie nr 3) Czy lista połączona dopuszcza wartości null?
Odpowiedź: Tak, połączona lista zezwala na dowolną liczbę wartości null.
Pytanie 4) Jakie są zalety listy połączonej?
Odpowiedź: Oto niektóre z zalet:
- Operacje manipulacyjne, takie jak dodawanie, usuwanie, są w nim szybsze.
- Nie ma potrzeby wstępnego przydzielania pamięci dla połączonej listy, co skutkuje wydajnym wykorzystaniem pamięci.
- Zapewnia szybszy czas dostępu i bez dodatkowego obciążenia pamięci i może być rozszerzany w stałym czasie.
- Jest to dynamiczna struktura danych
- Rośnie i kurczy się w czasie wykonywania w zależności od dodanych lub usuniętych wartości.
Pytanie nr 5) Jakie jest zastosowanie listy połączonej?
Odpowiedź: Jest używany głównie w następujących aplikacjach:
- Aby zaimplementować funkcję „cofnij” w oprogramowaniu takim jak MS-Word, Photoshop itp.
- Aby zaimplementować struktury danych, takie jak stos i kolejka.
- Możemy również implementować wykresy za pomocą połączonej listy.
- W przypadku mieszania zasobników każdy zasobnik można zaimplementować jako połączoną listę.
Pytanie 6) Jakie są ograniczenia listy połączonej?
Odpowiedź: Niektóre z ograniczeń to:
- Z dodatkowym wskaźnikiem do przechowywania odwołania do następnego elementu w każdym węźle, wykorzystywana pamięć to znacznie więcej niż tablice.
- Jest to struktura danych, do której dostęp jest ściśle sekwencyjny, dlatego węzły połączonej listy muszą być zawsze odczytywane od początku.
- Trudno jest przejść wstecz, zwłaszcza w przypadku list połączonych pojedynczo.
- Ponieważ węzły są przechowywane w nieciągłych lokalizacjach, czas wymagany do uzyskania dostępu może być długi.
Wniosek
W tym samouczku poznaliśmy podstawową strukturę danych listy połączonej. Następnie przenieśliśmy się na klasę java.util.LinkedList udostępnioną w Javie. Omówiliśmy szczegółowo tę klasę, w tym jej konstruktory, metody itp.
Omówiliśmy również niektóre specjalne operacje związane z listami połączonymi, takie jak sortowanie, odwracanie listy, usuwanie duplikatów, cykliczna lista połączona itp.
W następnym samouczku omówimy określone funkcje podwójnie połączonej listy.
=> Zapoznaj się z pełnym przewodnikiem szkoleniowym języka Java tutaj.
rekomendowane lektury
- Lista podwójnie połączona w Javie - przykłady implementacji i kodu
- Lista Java - jak tworzyć, inicjować i używać listy w Javie
- Metody listy Java - Sortuj listę, Zawiera, Dodaj listę, Usuń listę
- Algorytm wyszukiwania binarnego w Javie - implementacja i przykłady
- Sortowanie przez wstawianie w Javie - Algorytm sortowania przez wstawianie i przykłady
- Interfejs Java i samouczek klasy abstrakcyjnej z przykładami
- Struktura danych listy połączonej w C ++ z ilustracją
- Ukryta lista tablic i innych kolekcji w Javie