linked list java linked list implementation java examples
Acest tutorial explică ce este o structură de date cu listă legată în Java și cum se creează, se inițializează, se implementează, se traversează, se inversează și se sortează o listă legată prin Java:
În Java, o LinkedList este o structură de date care stochează elemente într-o locație necontiguă. Este o structură de date liniară.
Fiecare element de date se numește „Nod” și fiecare nod are o parte de date și o parte de adresă. Partea adresă stochează linkul către următorul nod din LinkedList.
=> Vizitați aici pentru a vedea seria de antrenament Java pentru toți.
Ce veți învăța:
- LinkedList În Java
- Clasa Java LinkedList
- Cum să creați o listă legată în Java
- Implementarea listei legate în Java
- Treceți / tipăriți lista legată în Java
- Metode LinkedList
- Listă inversă legată în Java
- Sortează o listă legată în Java
- Eliminați duplicatele
- Listă circulară legată în Java
- Java 8 LinkedList
- întrebări frecvente
- Concluzie
LinkedList În Java
Mai jos este prezentat aspectul general al LinkedList:
Așa cum se arată în reprezentarea de mai sus a LinkedList, fiecare element din LinkedList este „Nodul”. Fiecare nod are două părți, prima parte stochează datele, iar a doua parte are o referință sau un indicator sau o adresă a nodului următor din LinkedList.
eșantion de document de plan de testare pentru aplicația mobilă
Acest aranjament este necesar deoarece datele din LinkedList sunt stocate în locații non-contigue, spre deosebire de matrice.
„Capul” din LinkedList este un indicator care conține adresa primului element din LinkedList. Ultimul nod din LinkedList este coada. Așa cum se arată în figura de mai sus, partea de adresă a ultimului nod din LinkedList este setată la „Null” indicând sfârșitul LinkedList.
Diagrama de mai sus reprezintă un „ Listă legată individual ”Care stochează adresa doar nodului următor în LinkedList.
Există o altă versiune cunoscută sub numele de „ Lista dublă legată ”Al cărui nod are trei părți:
- Adresa sau referința sau indicatorul către elementul anterior din LinkedList.
- Partea de date
- Adresa sau referința sau indicatorul către următorul element din LinkedList.
Adresa anterioară a primului element din LinkedList va fi setată la Null, în timp ce următorul indicator al Ultimului element din LinkedList este setat la Null.
Reprezentarea unei liste dublu legate:
Așa cum se arată în reprezentarea de mai sus, fiecare nod din lista dublu legată are indicatori către nodul său anterior și următor (reprezentat astfel fără săgeți). Indicatorul anterior al primului nod indică spre nul, în timp ce următorul indicator al ultimului nod indică spre nul.
În acest tutorial LinkedList, ne vom ocupa în principal de lista legată individual. Vom discuta lista dublu legată în următorul nostru tutorial.
Clasa Java LinkedList
În Java, lista legată este implementată de „ LinkedList ”Clasa. Această clasă aparține „ java.util ' pachet. Clasa LinkedList implementează interfețele List și Deque și moștenește clasa AbstractList.
Mai jos este ierarhia de clase a clasei LinkedList.
Diagrama de mai sus arată ierarhia clasei LinkedList. După cum se arată, clasa LinkedList implementează interfețele List și Deque.
După cum sa menționat deja, clasa LinkedList face parte din „ java.util ' pachet. Prin urmare, ar trebui să puteți utiliza clasa LinkedList în programul dvs. prin includerea uneia dintre următoarele afirmații în programul dvs.
import java.util.*;
Sau
import java.util.LinkedList;
Deci, pe baza ierarhiei de mai sus, o definiție tipică a clasei LinkedList este după cum urmează:
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable
Mai jos sunt enumerate câteva dintre caracteristicile clasei LinkedList de care ar trebui să vă amintiți:
- Această clasă nu este sincronizată.
- Permite valori duplicate.
- Păstrează ordinea de inserare.
- Deoarece nu este necesar ca elementele să fie deplasate în timpul mișcării, manipularea elementelor din acesta este mai rapidă.
- Această clasă poate fi utilizată pentru a implementa o stivă, o coadă și o listă.
Cum să creați o listă legată în Java
Înainte de a trece la crearea unei liste de linkuri în Java, să discutăm mai întâi despre un nod de listă de linkuri în Java.
După cum sa discutat deja, o listă legată este formată din noduri. Astfel, în Java, putem reprezenta o LinkedList ca o clasă cu Nodul său ca o clasă separată. Prin urmare, această clasă va avea o referință la tipul de nod.
Aceasta este prezentată după cum urmează:
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 } }
Pentru a crea un obiect de tip LinkedList, există doi constructori principali după cum urmează:
# 1) LinkedList ()
Sintaxa generală pentru acest constructor este:
LinkedList linkedList = new LinkedList();
Afirmația de mai sus creează o LinkedList goală.
De exemplu,
LinkedList l_list = new LinkedList();
Aceasta va crea o listă legată goală numită l_list.
# 2) LinkedList (Colecția c)
Sintaxa generală este:
LinkedList linkedList = new LinkedList (Collection c);
Afirmația de mai sus creează o LinkedList cu elemente din colecția c ca elemente inițiale.
La fel ca alte structuri de date de listă pe care le-am văzut deja, lista legată poate fi, de asemenea, inițializată folosind metoda add, metoda Arrays.asList () sau folosind constructorul cu colecția ca argument.
Implementarea listei legate în Java
Dat mai jos este un exemplu simplu de structură de date LinkedList în Java. În acest exemplu de implementare, vom folosi metoda add și metoda asList pentru a inițializa obiectele 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); } }
Ieșire:
Conținutul primei LinkedList: [10, 20, 30, 40, 50]
Conținutul celei de-a doua LinkedList: [Roșu, Verde, Albastru, Cyan, Magenta]
Programul de mai sus arată crearea și inițializarea LinkedList. Mai întâi, creăm o LinkedList de tip Integer și oferim o serie de Numere întregi convertite în listă folosind metoda asList ca valori inițiale pentru LinkedList.
Apoi, creăm o LinkedList goală de tip String și apoi folosind metoda add, adăugăm valori la LinkedList.
În cele din urmă, afișăm ambele obiecte LinkedList ca un șir.
Treceți / tipăriți lista legată în Java
Pentru a imprima conținutul sau a efectua orice operațiuni asupra elementelor LinkedList, trebuie să parcurgeți elementele sale. Am văzut deja aceste metode în tutorialele noastre anterioare. În această secțiune, vom discuta exemplele fiecăruia cu privire la LinkedList.
Folosind bucla
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 Ieșire:
Elementele LinkedList folosind bucla for:
Roșu Verde Albastru
Folosind pentru fiecare buclă
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 + ' '); } } }
Ieșire:
Elementele LinkedList folosind bucla forEach:
Roșu Verde Albastru
Folosind Iterator
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() + ' '); } } }
Ieșire:
Conținutul listei conectate:
Roșu Verde Albastru Galben
script shell pentru a compara două fișiere
Metode LinkedList
Clasa LinkedList oferă API care acceptă diverse metode de manipulare a listei Linked. Am tabelat metodele din LinkedList API de mai jos.
Vom discuta despre principalele operațiuni / metode în secțiunea următoare.
Metodă Prototip Descriere clar gol clar () Șterge toate elementele din listă. Adăuga add boolean (E e) Adăugați un element specificat în LinkedList adăugare nulă (index int, element E) Adăugați element la indexul dat în LinkedList Adaugă totul boolean addAll (Colecția c) Adaugă elementele unei colecții date c la sfârșitul LinkedList. addAll boolean (index int, Colecția c) Adaugă elementele unei colecții date c la indexul specificat în LinkedList addFirst void addFirst (E e) Adăugați elementul dat ca prim element în LinkedList. addLast void addLast (E e) Adăugați elementul dat la sfârșitul listei. Clonează Clonare obiect () Face o copie superficială a LinkedList Conține Boolean conține (Obiectul o) Verifică dacă lista conține elemente specificate; dacă da se întoarce adevărat. descendentIterator Iterator descendent Iterator () Returnează un iterator comandat invers pentru LinkedList. Element Element E () Returnează elementul din capul listei. obține E get (int index) Obține elementul la indexul specificat. getFirst E getFirst () Preluează primul element din LinkedList. getLast E getLast () Preluează ultimul element din LinkedList. Index de Int indexOf (Obiectul o) Găsiți indexul primei apariții a elementelor date din listă și returnați indexul. -1 dacă elementul nu a fost găsit. lastIndexOf Int lastIndexOf (Obiectul o) Returnează poziția ultimei apariții a elementului dat în LinkedList; -1 dacă elementul dat nu este prezent listIterator ListIterator listIterator (index int) Returnează listIterator din indexul specificat în lista de linkuri. Oferi ofertă booleană (E e) Adaugă elementul dat ca ultim element (coadă) în LinkedList. ofertaPrima Oferta booleană First (E e) Adaugă elementul dat ca primul element din LinkedList. oferta Ultima Oferta booleană Ultima (E e) Adăugați elementul dat e la sfârșitul LinkedList. Arunca o privire E peek () Returnează capul listei fără a-l elimina. peekFirst E peekFirst () Returnează primul element din listă. returnează nul dacă lista este goală. peekLast E peekLast () Returnează ultimul element sau nul dacă lista este goală. Nu șterge elementul. Sondaj Sondaj E () Returnează capul LinkedList-ului și îl elimină. pollFirst E pollFirst () Returnează și șterge primul element din listă; returnează nul dacă lista este goală. pollLast E pollLast () Returnează și șterge ultimul element din listă; returnează nul dacă lista este goală. Pop E pop () Scoate elementul din reprezentarea stivei a LinkedList. Apăsați Împingere vid (E e) Împinge sau introduce un element în reprezentarea stivei a LinkedList. Elimina E elimina () Elimină și returnează capul Listei Linked. Elimina E (index int) Șterge elementul de la indexul dat din LinkedList. eliminare booleană (Obiectul o) Șterge prima apariție a elementului dat din LinkedList. removeFirst E removeFirst () Returnează și șterge primul element din listă. removeFirstOccurence boolean removeFirstOccurrence (Obiectul o) Șterge prima apariție a elementului dat din listă atunci când lista este traversată de la cap la coadă. elimina Ultimul E removeLast () Returnează ultimul element din LinkedList și îl șterge. removeLastOccurence boolean removeLastOccurrence (obiect o) Elimină ultima apariție a elementului dat din LinkedList atunci când este traversat de la cap la coadă A stabilit Set E (index int, element E) Setează elementul dat la indexul dat. Înlocuiește elementul curent cu nou. mărimea Dimensiune Int () Returnează dimensiunea sau numărul de elemente din LinkedList toArray Obiect [] toArray () Convertește LinkedList într-o matrice care conține toate elementele listei în ordine corespunzătoare T [] toArray (T [] a) Convertește LinkedList într-o matrice cu tipul de execuție la fel ca argumentul a.
Programul Java de mai jos demonstrează diferitele metode pe care le-am enumerat mai sus.
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)); } }
Ieșire:
Lista conectată: [A, B, C, D, G, E, F]
Listă legată după adăugarea conținutului ArrayList: [A, B, C, D, G, E, F, H, I]
Listă legată după ștergere: [C, D, E, F, H]
Lista nu conține elementul „G”
Dimensiunea listei conectate = 5
Element returnat de get (): F
Listă legată după modificare: [C, D, E, J, H]
Matrice obținută din lista legată: [C, D, E, J, H]
Programul de mai sus demonstrează diverse metode ale clasei LinkedList. În primul rând, declarăm o LinkedList de tip String. Apoi, folosim diferite versiuni ale metodei add, cum ar fi add, andFirst, addLast, addAll, etc. pentru a completa lista LinkedList cu valori.
Aici putem adăuga elementul direct la sfârșitul listei sau putem adăuga elementul într-o poziție specificată din listă.
De asemenea, folosim metoda addFirst pentru a adăuga un element la începutul listei și addLast pentru a adăuga un element la sfârșitul listei. Apoi efectuăm operații de eliminare pe LinkedList, cum ar fi remove, removeFirst, removeLast etc.
Pentru metoda de eliminare, putem specifica fie elementul de eliminat, fie indicăm indexul sau poziția din LinkedList la care elementul urmează să fie eliminat. Metodele removeFirst și removeLast remove primul și ultimul element din listă.
Apoi căutăm în listă un anumit element folosind metoda conține. Apoi, folosim metoda size () pentru a prelua dimensiunea sau lungimea LinkedList. Apoi folosim metode get / set pentru a recupera valoarea la un anumit indice din listă și apoi înlocuim o valoare la o poziție specificată din listă.
În cele din urmă, convertim LinkedList într-un Array folosind metoda toArray.
Listă inversă legată în Java
Pentru a inversa o listă legată în Java, folosim metoda „descendingIterator ()” care returnează un iterator invers pentru listă. Putem folosi apoi acest iterator pentru a parcurge lista și afișa elementele.
Programul de mai jos inversează lista legată utilizând metoda 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() + ' '); } } }
Ieșire:
Lista legată: [Pune, Mumbai, Nagpur]
Lista conectată în ordine inversă:
Nagpur Mumbai Pune
În programul de mai sus, declarăm o listă legată și apoi o imprimăm. Apoi obținem un iterator invers și apoi parcurgem lista folosind-o și afișăm fiecare element. Ieșirea arată conținutul listei legate, mai întâi în ordinea în care sunt adăugate elementele și apoi ieșirea arată conținutul în ordine inversă.
Sortează o listă legată în Java
Obiectele clasei LinkedList pot fi sortate folosind metoda Collections.sort (). Această metodă oferă două versiuni cu sau fără utilizarea unui comparator. Când metoda Collections.sort () este apelată fără un comparator, colecția este sortată în ordinea naturală.
Cand comparator este utilizat cu această metodă, ne putem defini propriile criterii de sortare prin înlocuirea metodei compareTo.
Programul Java de mai jos sortează un LinkedList folosind Collections.sort (). Aici sortăm matricele folosind ordonarea naturală, precum și folosind un comparator.
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); } }
Ieșire:
Original LinkedList (nesortat): [ianuarie, februarie, mar, aprilie, mai, iunie]
LinkedList (sortate în ordine naturală): [apr, februarie, ianuarie, iunie, mar, mai]
LinkedList (sortat folosind Comparator): [apr, februarie, ianuarie, iunie, mar, mai]
Eliminați duplicatele
Pentru a elimina duplicatele, trebuie să parcurgeți fiecare nod și să îl comparați cu următorul nod. Dacă ambele noduri sunt aceleași, atunci omitem un nod și trecem la următorul.
În acest mod, după parcurgerea fiecărui nod și eliminarea nodurilor duplicate, vom obține lista rezultată care nu conține elemente duplicate.
Mai jos este prezentat un program Java pentru eliminarea duplicatelor.
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(); } }
Ieșire:
Linkedlist original:
1 1 2 3 5 2 1 1
LinkedList după eliminarea duplicatelor:
1 2 3 5
În programul de mai sus, avem o clasă de listă legată creată pentru a elimina duplicatele. De asemenea, avem o clasă pentru a defini fiecare nod. Cu alte cuvinte, nodurile din listă sunt obiectele acestui nod de clasă. Avem o metodă pentru a adăuga nodul la o listă legată.
Apoi, în metoda removeDuplicate, parcurgem fiecare nod din lista legată începând de la cap și comparăm fiecare nod ulterior pentru duplicat. Dacă se găsește un duplicat, omitem acel nod și trecem la următorul nod.
În acest fel, ist este construit omitând nodurile duplicate și lista modificată este tipărită folosind metoda print ().
Listă circulară legată în Java
O listă circulară legată este o listă care are coada sau ultimul nod conectat înapoi la cap sau la primul nod.
Diagrama de mai jos arată lista circulară legată în Java.
cască vr pentru xbox one s
Așa cum se arată în diagrama de mai sus, partea de adresă a ultimului nod sau coadă a listei legate nu este setată la nulă. În schimb, indică înapoi către primul nod sau capul listei formând astfel o listă circulară legată.
Programul de mai jos implementează o listă circulară legată în care trebuie să manipulăm noduri individuale din lista legată.
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(); } }
Ieșire:
Noduri de listă circulară:
10 20 30 40
Java 8 LinkedList
Deși nu mai există funcții adăugate în mod specific clasei LinkedList în Java 8, a introdus în continuare fluxuri pentru a manipula date.
Programul de mai jos arată utilizarea fluxului Java 8 pentru a afișa 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); } }
Ieșire:
Conținutul LinkedList:
Net
Verde
Albastru
Cyan
Magenta
întrebări frecvente
Q # 1) Când se utilizează Lista conectată în Java?
Răspuns: Deoarece este mai rapid decât colecțiile precum ArrayList în operațiunile de modificare, ar trebui să fie utilizat în aplicații care necesită operații frecvente de adăugare / ștergere. Pentru aplicațiile care au în principal date numai în citire, pot fi utilizate ArrayList sau colecții similare.
Q # 2) Ce este ListNode?
Răspuns: Un ListNode este o clasă de bază asociată cu o listă legată în Java și reprezintă informații asociate cu un singur element sau un nod. Fiecare ListNode este format din date și un pointer sau referință la următorul element.
Q # 3) Lista conectată permite valori nule?
Răspuns: Da, lista legată permite orice număr de valori nule.
Q # 4) Care sunt avantajele unei liste conectate?
Răspuns: Unele dintre avantaje sunt:
- Operațiunile de manipulare precum adăugarea, ștergerea sunt mai rapide în ea.
- Nu este nevoie să alocați în prealabil memoria pentru o listă legată și astfel rezultă o utilizare eficientă a memoriei.
- Oferă un timp de acces mai rapid și fără cheltuieli suplimentare pentru memorie și poate fi extins în timp constant.
- Este o structură de date dinamică
- Crește și se micșorează în timpul rulării, în funcție de valorile adăugate sau șterse.
Q # 5) Care este aplicația listei conectate?
Răspuns: Este utilizat în principal în următoarele aplicații:
- Pentru a implementa funcționalitatea „anulați” în software cum ar fi MS-Word, Photoshop etc.
- Pentru a implementa structuri de date cum ar fi stiva și coada.
- De asemenea, putem implementa grafice folosind o listă legată.
- Pentru hashingul bucket, fiecare bucket poate fi implementat ca o listă legată.
Q # 6) Care sunt limitele unei liste conectate?
Răspuns: Unele dintre limitări sunt:
- Cu un indicator suplimentar pentru a menține referința următorului element din fiecare nod, memoria utilizată este mult mai mult decât tablouri.
- Aceasta este o structură de date strict accesată secvențial, prin urmare nodurile din lista legată trebuie citite întotdeauna de la început.
- Este dificil să-l parcurgi înapoi, în special listele legate individual.
- Deoarece nodurile sunt stocate în locații non-contigue, timpul necesar pentru acces poate fi mare.
Concluzie
În acest tutorial, am învățat structura de bază a datelor listei legate. Apoi am trecut pe clasa java.util.LinkedList furnizată în Java. Am discutat în detaliu această clasă, inclusiv constructorii, metodele etc.
De asemenea, am discutat câteva operații speciale legate de listele legate, cum ar fi sortarea, inversarea unei liste, eliminarea duplicatelor, lista circulară legată etc.
În următorul nostru tutorial, vom discuta despre caracteristicile specifice ale listei dublu conectate.
=> Consultați aici Ghidul complet de instruire Java.
Lectură recomandată
- Lista dublă legată în Java - Exemple de implementare și cod
- Lista Java - Cum să creați, inițializați și utilizați lista în Java
- Metode de listă Java - Sortare listă, conține, adăugare listă, eliminare listă
- Algoritm de căutare binară în Java - Implementare și exemple
- Sortare prin inserare în Java - Algoritm de sortare și exemple
- Interfață Java și tutorial de clasă abstractă cu exemple
- Structura de date a listei legate în C ++ cu ilustrație
- Listă secretă pentru matrice și alte colecții din Java