linked list java linked list implementation java examples
Aquest tutorial explica què és una estructura de dades de llista enllaçada a Java i com crear, inicialitzar, implementar, recórrer, invertir i ordenar una llista enllaçada de Java:
A Java, una LinkedList és una estructura de dades que emmagatzema elements en una ubicació no contigua. És una estructura de dades lineal.
Cada element de dades s’anomena ‘node’ i cada node té una part de dades i una part d’adreça. La part de l'adreça emmagatzema l'enllaç al següent node a la Llista enllaçada.
=> Visiteu aquí per veure la sèrie d'entrenaments de Java per a tothom.
Què aprendreu:
- LinkedList a Java
- Classe Java LinkedList
- Com es crea una llista enllaçada a Java
- Implementació de llistes enllaçades a Java
- Recorre / imprimeix la llista enllaçada a Java
- Mètodes LinkedList
- Llista enllaçada inversa a Java
- Ordeneu una llista enllaçada a Java
- Elimina els duplicats
- Llista circular enllaçada a Java
- Llista enllaçada de Java 8
- Preguntes freqüents
- Conclusió
LinkedList a Java
A continuació es mostra el disseny general de LinkedList:
Com es mostra a la representació anterior de LinkedList, cada element de LinkedList és el 'Node'. Cada node té dues parts, la primera part emmagatzema les dades i la segona part té una referència o un punter o adreça del següent node a la Llista enllaçada.
millor programari per restaurar fitxers suprimits
Aquesta disposició és necessària ja que les dades de LinkedList s’emmagatzemen en ubicacions no contigües, a diferència de les matrius.
El 'cap' de LinkedList és un punter que conté l'adreça del primer element de LinkedList. L’últim node de la Llista enllaçada és la cua. Com es mostra a la figura anterior, la part d’adreça de l’últim node de la Llista enllaçada s’estableix a ‘Nul’ que indica el final de la Llista enllaçada.
El diagrama anterior representa un “ Llista enllaçada individualment ”Que emmagatzema l'adreça del següent node següent a la Llista enllaçada.
Hi ha una altra versió coneguda com ' Llista doblement enllaçada ”Cada node té tres parts:
- Adreça o referència o punter a l'element anterior de la Llista enllaçada.
- Part de dades
- Adreça o referència o punter al següent element de la Llista enllaçada.
L'adreça anterior del primer element de la Llista enllaçada s'establirà a Null, mentre que el següent punter de l'últim element de la Llista enllaçada s'estableix a Null.
Representació de la llista doblement enllaçada:
Com es mostra a la representació anterior, cada node de la llista doblement enllaçada té indicacions cap al seu node anterior i següent (representat així sense fletxes). El punter anterior del primer node apunta a nul mentre que el següent punter del darrer node apunta a nul.
En aquest tutorial de LinkedList, tractarem principalment de la llista enllaçada individualment. Analitzarem la llista doblement enllaçada al nostre proper tutorial.
Classe Java LinkedList
A Java, la llista enllaçada s’implementa mitjançant el “ Llista enllaçada ”Classe. Aquesta classe pertany a la java.util ”Paquet. La classe LinkedList implementa les interfícies List i Deque i hereta la classe AbstractList.
A continuació es mostra la jerarquia de classes de la classe LinkedList.
El diagrama anterior mostra la jerarquia de la classe LinkedList. Com es mostra, la classe LinkedList implementa les interfícies List i Deque.
Com ja s’ha esmentat, la classe LinkedList forma part del programa “ java.util ”Paquet. Per tant, hauríeu de poder utilitzar la classe LinkedList al vostre programa incloent una de les afirmacions següents al programa.
import java.util.*;
O bé
import java.util.LinkedList;
De manera que, segons la jerarquia anterior, una definició típica de la classe LinkedList és la següent:
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable
A continuació, es detallen algunes de les característiques de la classe LinkedList que heu de recordar:
- Aquesta classe no està sincronitzada.
- Permet valors duplicats.
- Conserva l'ordre d'inserció.
- Com que no és necessari desplaçar els elements mentre es mouen, la manipulació dels elements en ell és més ràpida.
- Aquesta classe es pot utilitzar per implementar una pila, una cua i una llista.
Com es crea una llista enllaçada a Java
Abans de passar a crear una llista enllaçada a Java, parlem primer d’un node de llista enllaçada a Java.
Com ja s'ha comentat, una llista enllaçada consta de nodes. Així, a Java, podem representar una LinkedList com una classe amb el seu Node com a classe independent. Per tant, aquesta classe tindrà una referència al tipus Node.
Això es mostra a continuació:
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 } }
Per crear un objecte de tipus LinkedList, hi ha dos constructors principals de la següent manera:
# 1) Llista enllaçada ()
La sintaxi general d'aquest constructor és:
LinkedList linkedList = new LinkedList();
La sentència anterior crea una LinkedList buida.
Per exemple,
LinkedList l_list = new LinkedList();
Això crearà una llista enllaçada buida anomenada l_list.
# 2) LinkedList (col·lecció c)
La sintaxi general és:
LinkedList linkedList = new LinkedList (Collection c);
L'afirmació anterior crea una LinkedList amb elements de la col·lecció c com a elements inicials.
Igual que altres estructures de dades de llistes que ja hem vist, la llista enllaçada també es pot inicialitzar mitjançant el mètode add, el mètode Arrays.asList () o mitjançant el constructor amb la col·lecció com a argument.
Implementació de llistes enllaçades a Java
A continuació es mostra un exemple senzill d’una estructura de dades LinkedList a Java. En aquest exemple d'implementació, utilitzarem el mètode add i el mètode asList per inicialitzar els objectes 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); } }
Sortida:
Contingut de la primera LinkedList: (10, 20, 30, 40, 50)
Contingut de la segona LinkedList: (vermell, verd, blau, cian, magenta)
El programa anterior mostra la creació i inicialització de LinkedList. En primer lloc, creem una LinkedList de tipus Integer i proporcionem una matriu d’Inters convertits a llista mitjançant el mètode asList com a valors inicials per a LinkedList.
A continuació, creem una LinkedList buida de tipus String i, a continuació, mitjançant el mètode add, afegim valors a LinkedList.
Finalment, mostrem tant els objectes LinkedList com una cadena.
Recorre / imprimeix la llista enllaçada a Java
Per imprimir el contingut o realitzar qualsevol operació sobre els elements de la Llista enllaçada, heu de recórrer-ne els elements. Ja hem vist aquests mètodes en els nostres tutorials anteriors. En aquesta secció, analitzarem els exemples de cadascun respecte a LinkedList.
Utilitzant el bucle
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 Sortida:
Elements LinkedList que utilitzen el bucle for:
Vermell Blau Verd

Utilitzant per a cada bucle
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 + ' '); } } }
Sortida:
Elements LinkedList que utilitzen bucle forEach:
Vermell Blau Verd

Utilitzant 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() + ' '); } } }
Sortida:
El contingut de la llista enllaçada:
Vermell Verd Blau Groc
què és stringstream a c ++

Mètodes LinkedList
La classe LinkedList proporciona API que admet diversos mètodes per manipular la llista enllaçada. A continuació, hem tabulat els mètodes de l'API LinkedList.
Analitzarem les principals operacions / mètodes a la secció següent.
Mètode Prototip Descripció Clar void clear () Suprimeix tots els elements de la llista. Afegeix addició booleana (E e) Afegiu un element especificat a LinkedList void add (índex int, element E) Afegiu un element a l'índex donat a LinkedList Afegeix-ho tot add boolean add (Col·lecció c) Afegeix els elements de la col·lecció donada c al final de la Llista enllaçada. addAll booleà (índex int, col·lecció c) Afegeix els elements de la col·lecció donada c a l'índex especificat a la Llista enllaçada addFirst void addFirst (E e) Afegiu l'element donat com a primer element a la Llista enllaçada. afegirDarrer void addLast (E e) Afegiu l'element donat al final de la llista. Clonar Clon d'objectes () Fa una còpia superficial de LinkedList Conté Booleà conté (objecte o) Comprova si la llista conté elements especificats; si sí, es torna cert. descendingIterator Iterador descendent Iterador () Retorna un iterador ordenat inversament per a LinkedList. Element Element E () Retorna l'element al capdavant de la llista. Aconseguir E get (índex int) Obté l'element a l'índex especificat. getFirst E getFirst () Recupera el primer element de la Llista enllaçada. getLast E getLast () Recupera l'últim element de la Llista enllaçada. índex de Int indexOf (objecte o) Cerqueu l'índex de la primera aparició dels elements donats a la llista i torneu-lo. -1 si no s'ha trobat l'element. lastIndexOf Int lastIndexOf (objecte o) Retorna la posició de l'última aparició de l'element donat a la Llista enllaçada; -1 si l'element donat no és present listIterator ListIterator listIterator (int index) Retorna el listIterator de l'índex especificat a la llista enllaçada. Oferta oferta booleana (E e) Afegeix l'element donat com a últim element (cua) a la Llista enllaçada. ofertaPrimer Oferta booleana Primera (E e) Afegeix l'element donat com a primer element a la Llista enllaçada. ofertaDarrer Oferta booleana Darrer (E e) Afegiu l’element donat e al final de la Llista enllaçada. Ullada E peek () Retorna el cap de llista sense eliminar-lo. peekFirst E peekFirst () Retorna el primer element de la llista. torna nul si la llista està buida. peekLast E peekLast () Retorna l'últim element o nul si la llista està buida. No elimina l'element. Enquesta Enquesta E () Retorna el cap de LinkedList i també l'elimina. pollFirst E pollFirst () Retorna i suprimeix el primer element de la llista; torna nul si la llista està buida. pollLast E pollLast () Retorna i suprimeix l'últim element de la llista; torna nul si la llista està buida. pop E pop () Apaga l'element de la representació de pila de LinkedList. Premeu Empenta buida (E e) Insereix o insereix un element a la representació de pila de LinkedList. Elimina Eliminar () Elimina i retorna el cap de la Llista enllaçada. Elimina E (índex int) Suprimeix l'element de l'índex donat de la Llista enllaçada. eliminar booleà (objecte o) Suprimeix la primera aparició de l'element donat de la Llista enllaçada. removeFirst E removeFirst () Retorna i suprimeix el primer element de la llista. removeFirstOccurence booleà removeFirstOccurrence (objecte o) Suprimeix la primera ocurrència de l'element donat de la llista quan es recorre la llista del cap a la cua. eliminar Darrer E removeLast () Retorna l'últim element de la Llista enllaçada i també el suprimeix. removeLastOccurence booleà removeLastOccurrence (objecte o) Elimina l'última aparició de l'element donat de la Llista enllaçada quan es travessa de cap a cua Conjunt Conjunt E (índex int, element E) Estableix l'element donat a l'índex donat. Substitueix l'element actual per nou. Mida Mida int () Retorna la mida o el nombre d'elements de la Llista enllaçada toArray Objecte () toArray () Converteix el LinkedList en una matriu que conté tots els elements de la llista en la seqüència adequada T () toArray (T () a) Converteix LinkedList en una matriu amb el tipus d'execució igual que l'argument a.
El programa Java següent mostra els diversos mètodes que hem detallat anteriorment.
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)); } }
Sortida:
Llista enllaçada: (A, B, C, D, G, E, F)
Llista enllaçada després d'afegir contingut ArrayList: (A, B, C, D, G, E, F, H, I)
Llista enllaçada després de la supressió: (C, D, E, F, H)
La llista no conté l'element 'G'
Mida de la llista enllaçada = 5
Element retornat per get (): F
Llista enllaçada després del canvi: (C, D, E, J, H)
Matriu obtinguda de la llista enllaçada: (C, D, E, J, H)

El programa anterior mostra diversos mètodes de la classe LinkedList. En primer lloc, declarem una LinkedList de tipus String. A continuació, fem servir diverses versions del mètode add, com ara add, andFirst, addLast, addAll, etc., per omplir la llista enllaçada de valors.
Aquí podem afegir l'element directament al final de la llista o afegir l'element en una posició especificada de la llista.
També fem servir el mètode addFirst per afegir un element al principi de la llista i addLast per afegir un element al final de la llista. A continuació, realitzem operacions d’eliminació a la Llista enllaçada, com ara remove, removeFirst, removeLast, etc.
Per al mètode d'eliminació, podem especificar l'element que s'ha d'eliminar o bé especificar l'índex o la posició a la Llista enllaçada en què s'ha d'eliminar l'element. Els mètodes removeFirst i removeLast eliminen el primer i l’últim element de la llista respectivament.
A continuació, cerquem a la llista un element concret mitjançant el mètode conté. A continuació, fem servir el mètode size () per recuperar la mida o la longitud de LinkedList. A continuació, fem servir mètodes get / set per recuperar el valor d’un índex concret de la llista i, a continuació, substituïm un valor en una posició especificada de la llista.
Finalment, convertim la LinkedList a una matriu mitjançant el mètode toArray.
Llista enllaçada inversa a Java
Per invertir una llista enllaçada a Java, fem servir el mètode 'descendingIterator ()' que retorna un iterador invers per a la llista. A continuació, podem utilitzar aquest iterador per recórrer la llista i mostrar els elements.
El programa següent inverteix la llista enllaçada mitjançant el mètode 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() + ' '); } } }
Sortida:
Llista enllaçada: (Pune, Bombai, Nagpur)
Llista enllaçada en ordre invers:
Nagpur Mumbai Pune

Al programa anterior, declarem una llista enllaçada i després la imprimim. A continuació, obtenim un iterador invers i, a continuació, passem per la llista amb ella i mostrem cada element. La sortida mostra el contingut de la llista enllaçada, primer en l’ordre en què s’afegeixen els elements i després la sortida mostra el contingut en ordre invers.
Ordeneu una llista enllaçada a Java
Els objectes de classe LinkedList es poden ordenar mitjançant el mètode Collections.sort (). Aquest mètode proporciona dues versions amb o sense un comparador. Quan es crida el mètode Collections.sort () sense un comparador, la col·lecció s’ordena en l’ordre natural.
Quan el comparador s’utilitza amb aquest mètode, podem definir els nostres propis criteris d’ordenació substituint el mètode compareTo.
El programa Java següent ordena una LinkedList mitjançant Collections.sort (). Aquí classifiquem matrius mitjançant ordenacions naturals i també mitjançant un comparador.
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); } }
Sortida:
Llista enllaçada original (sense classificar): (gener, febrer, març, abril, maig, juny)
Llista enllaçada (ordenada per ordre natural): (abril, febrer, gener, juny, mar, maig)
LinkedList (ordenada mitjançant Comparator): (abr, febrer, gener, juny, març, maig)

llista d'adjacència de gràfics ponderats c ++
Elimina els duplicats
Per eliminar duplicats, heu de recórrer cada node i comparar-lo amb el següent. Si els dos nodes són iguals, saltem un node i passem al següent.
D’aquesta manera, després de recórrer tots els nodes i desfer-nos dels nodes duplicats, obtindrem la llista resultant que no té cap element duplicat.
A continuació es mostra un programa Java per eliminar duplicats.
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(); } }
Sortida:
Llista enllaçada original:
1 1 2 3 5 2 1 1
LinkedList després d'eliminar els duplicats:
1 2 3 5

Al programa anterior, tenim una classe de llista enllaçada creada per eliminar els duplicats. També tenim una classe per definir cada node. En altres paraules, els nodes de la llista són els objectes d’aquest node de classe. Tenim un mètode per afegir el node a una llista enllaçada.
A continuació, al mètode removeDuplicate, recorrem cada node de la llista enllaçada a partir del cap i comparem cada node posterior per al duplicat. Si es troba un duplicat, saltem aquest node i passem al següent node.
D'aquesta manera, l'ist es crea saltant els nodes duplicats i la llista modificada s'imprimeix mitjançant el mètode print ().
Llista circular enllaçada a Java
Una llista enllaçada circular és una llista que té la cua o l'últim node connectat de nou al cap o al primer node.
El diagrama següent mostra la llista circular enllaçada a Java.

Com es mostra al diagrama anterior, la part de l'adreça de l'últim node o cua de la llista enllaçada no s'estableix en nul·la. En lloc d'això, apunta cap al primer node o cap de la llista formant així una llista enllaçada circular.
El programa següent implementa una llista enllaçada circular on hem de manipular nodes individuals de la llista enllaçada.
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(); } }
Sortida:
Nodes de llista enllaçats circulars:
10 20 30 40

Llista enllaçada de Java 8
Tot i que no hi ha més funcions afegides específicament a la classe LinkedList a Java 8, encara va introduir corrents per manipular dades.
El programa següent mostra l'ús del flux Java 8 per mostrar 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); } }
Sortida:
El contingut de LinkedList:
xarxa
Verd
Blau
Cian
magenta

Preguntes freqüents
P # 1) Quan s'utilitza la llista enllaçada a Java?
Resposta: Com que és més ràpid que les col·leccions com ArrayList en operacions de modificació, s'hauria d'utilitzar en aplicacions que requereixen operacions freqüents d'addició / supressió. Per a aplicacions que contenen principalment dades de només lectura, es poden utilitzar ArrayList o col·leccions similars.
Q # 2) Què és ListNode?
Resposta: Un ListNode és una classe bàsica associada a una llista enllaçada a Java i representa informació associada a un sol element o a un node. Cada ListNode consta de dades i un punter o referència al següent element.
Q # 3) La llista enllaçada permet valors nuls?
Resposta: Sí, la llista enllaçada permet qualsevol nombre de valors nuls.
Q # 4) Quins avantatges té una llista enllaçada?
Resposta: Alguns dels avantatges són:
- Les operacions de manipulació com l’addició i la supressió són més ràpides.
- No cal pre-assignar memòria per a una llista enllaçada i, per tant, es tradueix en una utilització eficient de la memòria.
- Proporciona un temps d'accés més ràpid i sense despeses addicionals de memòria, i es pot ampliar en temps constant.
- És una estructura de dades dinàmica
- Creix i es redueix en temps d'execució en funció dels valors afegits o suprimits.
Q # 5) Quina és l'aplicació de la llista enllaçada?
Resposta: s'utilitza principalment en les aplicacions següents:
- Per implementar la funcionalitat de 'desfer' en programes com MS-Word, Photoshop, etc.
- Per implementar estructures de dades com pila i cua.
- També podem implementar gràfics mitjançant una llista enllaçada.
- Per al resum de dipòsit, cada dipòsit es pot implementar com a llista enllaçada.
Q # 6) Quines són les limitacions d'una llista enllaçada?
Resposta: algunes de les limitacions són:
- Amb un punter addicional per contenir la referència de l'element següent de cada node, la memòria utilitzada és molt més que matrius.
- Es tracta d’una estructura de dades estrictament accedida de manera seqüencial, de manera que els nodes de la llista enllaçada sempre s’han de llegir des del principi.
- És difícil recórrer-lo cap enrere, especialment les llistes lligades individualment.
- Com que els nodes s’emmagatzemen en ubicacions no contigües, el temps necessari per accedir-hi pot ser elevat.
Conclusió
En aquest tutorial, hem après l’estructura bàsica de dades de la llista enllaçada. Després vam passar a la classe java.util.LinkedList proporcionada a Java. Vam discutir en detall aquesta classe, inclosos els seus constructors, mètodes, etc.
També hem debatut sobre algunes operacions especials relacionades amb les llistes enllaçades, com ara ordenar, invertir una llista, eliminar duplicats, llista enllaçada circular, etc.
Al nostre següent tutorial, analitzarem les característiques específiques de la llista doblement enllaçada.
=> Consulteu aquí la guia de formació completa de Java.
Lectura recomanada
- Llista doblement enllaçada a Java: implementació i exemples de codi
- Llista Java: Com crear, inicialitzar i utilitzar una llista a Java
- Mètodes de llista de Java: ordena llista, conté, afegeix llista, elimina llista
- Algorisme de cerca binària a Java: implementació i exemples
- Classificació per inserció a Java: algorisme i exemples d'ordenació per inserció
- Interfície Java i tutoria de classes abstractes amb exemples
- Estructura de dades de la llista enllaçada en C ++ amb il·lustració
- Llista encoberta de matrius i altres col·leccions de Java