Requisit previ: Igual que les matrius, la llista enllaçada és una estructura de dades lineal. A diferència de les matrius, els elements de la llista enllaçada no s'emmagatzemen a la ubicació contigua, els elements s'enllaçen mitjançant punters com es mostra a continuació.
Igual que les matrius, la llista enllaçada és una estructura de dades lineal. A diferència de les matrius, els elements de la llista enllaçada no s'emmagatzemen a la ubicació contigua, els elements s'enllaçen mitjançant punters com es mostra a continuació.
A Java, LinkedList es pot representar com una classe i un Node com una classe separada. La classe LinkedList conté una referència del tipus de classe Node.
Java
class> LinkedList {> >Node head;>// head of list> >/* Linked list Node*/> >static> class> Node {> >int> data;> >Node next;> >// Constructor to create a new node> >// Next is by default initialized> >// as null> >Node(>int> d) { data = d; }> >}> }> |
>
>
Creació i inserció:
En aquest article, la inserció a la llista es fa al final, és a dir, el nou node s'afegeix després de l'últim node de la llista enllaçada donada. Per exemple, si la llista enllaçada donada és 5->10->15->20->25 i s'ha d'inserir 30, aleshores la llista enllaçada passa a ser 5->10->15->20->25->30 .
Com que una llista enllaçada normalment es representa amb el punter principal d'aquesta, cal recórrer la llista fins a l'últim node i després canviar el penúltim node al nou node.
Implementació:
Java
import> java.io.*;> > // Java program to implement> // a Singly Linked List> public> class> LinkedList {> > >Node head;>// head of list> > >// Linked list Node.> >// This inner class is made static> >// so that main() can access it> >static> class> Node {> > >int> data;> >Node next;> > >// Constructor> >Node(>int> d)> >{> >data = d;> >next =>null>;> >}> >}> > >// Method to insert a new node> >public> static> LinkedList insert(LinkedList list,>int> data)> >{> >// Create a new node with given data> >Node new_node =>new> Node(data);> > > >// If the Linked List is empty,> >// then make the new node as head> >if> (list.head ==>null>) {> >list.head = new_node;> >}> >else> {> >// Else traverse till the last node> >// and insert the new_node there> >Node last = list.head;> >while> (last.next !=>null>) {> >last = last.next;> >}> > >// Insert the new_node at last node> >last.next = new_node;> >}> > >// Return the list by head> >return> list;> >}> > >// Method to print the LinkedList.> >public> static> void> printList(LinkedList list)> >{> >Node currNode = list.head;> > >System.out.print(>'LinkedList: '>);> > >// Traverse through the LinkedList> >while> (currNode !=>null>) {> >// Print the data at current node> >System.out.print(currNode.data +>' '>);> > >// Go to next node> >currNode = currNode.next;> >}> >}> > >// Driver code> >public> static> void> main(String[] args)> >{> >/* Start with the empty list. */> >LinkedList list =>new> LinkedList();> > >//> >// ******INSERTION******> >//> > >// Insert the values> >list = insert(list,>1>);> >list = insert(list,>2>);> >list = insert(list,>3>);> >list = insert(list,>4>);> >list = insert(list,>5>);> >list = insert(list,>6>);> >list = insert(list,>7>);> >list = insert(list,>8>);> > >// Print the LinkedList> >printList(list);> >}> }> |
>
>Sortida
LinkedList: 1 2 3 4 5 6 7 8>
Travessia: Per a la travessa, a continuació hi ha una funció de propòsit general printList() que imprimeix qualsevol llista donada travessant la llista des del node principal fins a l'últim.
Implementació:
Java
import> java.io.*;> // Java program to implement> // a Singly Linked List> public> class> LinkedList {> >Node head;>// head of list> >// Linked list Node.> >// Node is a static nested class> >// so main() can access it> >static> class> Node {> >int> data;> >Node next;> >// Constructor> >Node(>int> d)> >{> >data = d;> >next =>null>;> >}> >}> >// Method to insert a new node> >public> static> LinkedList insert(LinkedList list,> >int> data)> >{> >// Create a new node with given data> >Node new_node =>new> Node(data);> >new_node.next =>null>;> >// If the Linked List is empty,> >// then make the new node as head> >if> (list.head ==>null>) {> >list.head = new_node;> >}> >else> {> >// Else traverse till the last node> >// and insert the new_node there> >Node last = list.head;> >while> (last.next !=>null>) {> >last = last.next;> >}> >// Insert the new_node at last node> >last.next = new_node;> >}> >// Return the list by head> >return> list;> >}> >// Method to print the LinkedList.> >public> static> void> printList(LinkedList list)> >{> >Node currNode = list.head;> >System.out.print(>'LinkedList: '>);> >// Traverse through the LinkedList> >while> (currNode !=>null>) {> >// Print the data at current node> >System.out.print(currNode.data +>' '>);> >// Go to next node> >currNode = currNode.next;> >}> >}> >// **************MAIN METHOD**************> >// method to create a Singly linked list with n nodes> >public> static> void> main(String[] args)> >{> >/* Start with the empty list. */> >LinkedList list =>new> LinkedList();> >//> >// ******INSERTION******> >//> >// Insert the values> >list = insert(list,>1>);> >list = insert(list,>2>);> >list = insert(list,>3>);> >list = insert(list,>4>);> >list = insert(list,>5>);> >list = insert(list,>6>);> >list = insert(list,>7>);> >list = insert(list,>8>);> >// Print the LinkedList> >printList(list);> >}> }> |
>
>Sortida
LinkedList: 1 2 3 4 5 6 7 8>
Eliminació per CLAU:
El procés d'eliminació es pot entendre de la següent manera:
Per fer:
Donada una 'clau', suprimiu la primera ocurrència d'aquesta clau a la llista enllaçada .
Com fer-ho:
Per suprimir un node de la llista enllaçada, seguiu els passos següents.
- Cerqueu la clau per la seva primera aparició a la llista
- Ara, qualsevol de les 3 condicions pot ser-hi:
- Cas 1: la clau es troba a cap
- En aquest cas, canvieu el capçal del node al següent node del capçal actual.
- Allibera la memòria del node principal substituït.
- Cas 2: La clau es troba al mig o l'últim, excepte a la cap
- En aquest cas, cerqueu el node anterior del node que voleu suprimir.
- Canvieu el següent node anterior al següent node del node actual.
- Allibera la memòria del node substituït.
- Cas 3: la clau no es troba a la llista
- En aquest cas, no cal fer cap operació.
Implementació:
Java
import> java.io.*;> // Java program to implement> // a Singly Linked List> public> class> LinkedList {> >Node head;>// head of list> >// Linked list Node.> >// Node is a static nested class> >// so main() can access it> >static> class> Node {> >int> data;> >Node next;> >// Constructor> >Node(>int> d)> >{> >data = d;> >next =>null>;> >}> >}> >// Method to insert a new node> >public> static> LinkedList insert(LinkedList list,> >int> data)> >{> >// Create a new node with given data> >Node new_node =>new> Node(data);> >new_node.next =>null>;> >// If the Linked List is empty,> >// then make the new node as head> >if> (list.head ==>null>) {> >list.head = new_node;> >}> >else> {> >// Else traverse till the last node> >// and insert the new_node there> >Node last = list.head;> >while> (last.next !=>null>) {> >last = last.next;> >}> >// Insert the new_node at last node> >last.next = new_node;> >}> >// Return the list by head> >return> list;> >}> >// Method to print the LinkedList.> >public> static> void> printList(LinkedList list)> >{> >Node currNode = list.head;> >System.out.print(>'LinkedList: '>);> >// Traverse through the LinkedList> >while> (currNode !=>null>) {> >// Print the data at current node> >System.out.print(currNode.data +>' '>);> >// Go to next node> >currNode = currNode.next;> >}> >System.out.println();> >}> >// **************DELETION BY KEY**************> >// Method to delete a node in the LinkedList by KEY> >public> static> LinkedList deleteByKey(LinkedList list,> >int> key)> >{> >// Store head node> >Node currNode = list.head, prev =>null>;> >//> >// CASE 1:> >// If head node itself holds the key to be deleted> >if> (currNode !=>null> && currNode.data == key) {> >list.head = currNode.next;>// Changed head> >// Display the message> >System.out.println(key +>' found and deleted'>);> >// Return the updated List> >return> list;> >}> >//> >// CASE 2:> >// If the key is somewhere other than at head> >//> >// Search for the key to be deleted,> >// keep track of the previous node> >// as it is needed to change currNode.next> >while> (currNode !=>null> && currNode.data != key) {> >// If currNode does not hold key> >// continue to next node> >prev = currNode;> >currNode = currNode.next;> >}> >// If the key was present, it should be at currNode> >// Therefore the currNode shall not be null> >if> (currNode !=>null>) {> >// Since the key is at currNode> >// Unlink currNode from linked list> >prev.next = currNode.next;> >// Display the message> >System.out.println(key +>' found and deleted'>);> >}> >//> >// CASE 3: The key is not present> >//> >// If key was not present in linked list> >// currNode should be null> >if> (currNode ==>null>) {> >// Display the message> >System.out.println(key +>' not found'>);> >}> >// return the List> >return> list;> >}> >// **************MAIN METHOD**************> >// method to create a Singly linked list with n nodes> >public> static> void> main(String[] args)> >{> >/* Start with the empty list. */> >LinkedList list =>new> LinkedList();> >//> >// ******INSERTION******> >//> >// Insert the values> >list = insert(list,>1>);> >list = insert(list,>2>);> >list = insert(list,>3>);> >list = insert(list,>4>);> >list = insert(list,>5>);> >list = insert(list,>6>);> >list = insert(list,>7>);> >list = insert(list,>8>);> >// Print the LinkedList> >printList(list);> >//> >// ******DELETION BY KEY******> >//> >// Delete node with value 1> >// In this case the key is ***at head***> >deleteByKey(list,>1>);> >// Print the LinkedList> >printList(list);> >// Delete node with value 4> >// In this case the key is present ***in the> >// middle***> >deleteByKey(list,>4>);> >// Print the LinkedList> >printList(list);> >// Delete node with value 10> >// In this case the key is ***not present***> >deleteByKey(list,>10>);> >// Print the LinkedList> >printList(list);> >}> }> |
>
>Sortida
LinkedList: 1 2 3 4 5 6 7 8 1 found and deleted LinkedList: 2 3 4 5 6 7 8 4 found and deleted LinkedList: 2 3 5 6 7 8 10 not found LinkedList: 2 3 5 6 7 8>
Supressió a la posició:
Aquest procés d'eliminació es pot entendre de la següent manera:
Per fer:
Donat a 'posició' , suprimiu el node en aquesta posició de la llista enllaçada .
Com fer-ho:
Els passos per fer-ho són els següents:
- Travessa la llista comptant l'índex dels nodes
- Per a cada índex, coincideix amb l'índex perquè sigui el mateix que la posició
- Ara, qualsevol de les 3 condicions pot ser-hi:
- Cas 1: la posició és 0, és a dir, s'ha de suprimir el cap
- En aquest cas, canvieu el capçal del node al següent node del capçal actual.
- Allibera la memòria del node principal substituït.
- Cas 2: la posició és superior a 0 però inferior a la mida de la llista, és a dir, al centre o a l'últim, excepte a la capçalera
- En aquest cas, Trobeu el node anterior del node que voleu suprimir.
- Canvia el següent del node anterior al següent node del node actual.
- Allibera la memòria del node substituït.
- Cas 3: la posició és més gran que la mida de la llista, és a dir, la posició no es troba a la llista
- En aquest cas, no cal fer cap operació.
Implementació:
Java
import> java.io.*;> // Java program to implement> // a Singly Linked List> public> class> LinkedList {> >Node head;>// head of list> >// Linked list Node.> >// Node is a static nested class> >// so main() can access it> >static> class> Node {> >int> data;> >Node next;> >// Constructor> >Node(>int> d)> >{> >data = d;> >next =>null>;> >}> >}> >// Method to insert a new node> >public> static> LinkedList insert(LinkedList list,> >int> data)> >{> >// Create a new node with given data> >Node new_node =>new> Node(data);> >new_node.next =>null>;> >// If the Linked List is empty,> >// then make the new node as head> >if> (list.head ==>null>) {> >list.head = new_node;> >}> >else> {> >// Else traverse till the last node> >// and insert the new_node there> >Node last = list.head;> >while> (last.next !=>null>) {> >last = last.next;> >}> >// Insert the new_node at last node> >last.next = new_node;> >}> >// Return the list by head> >return> list;> >}> >// Method to print the LinkedList.> >public> static> void> printList(LinkedList list)> >{> >Node currNode = list.head;> >System.out.print(>'LinkedList: '>);> >// Traverse through the LinkedList> >while> (currNode !=>null>) {> >// Print the data at current node> >System.out.print(currNode.data +>' '>);> >// Go to next node> >currNode = currNode.next;> >}> >System.out.println();> >}> >// Method to delete a node in the LinkedList by POSITION> >public> static> LinkedList> >deleteAtPosition(LinkedList list,>int> index)> >{> >// Store head node> >Node currNode = list.head, prev =>null>;> >//> >// CASE 1:> >// If index is 0, then head node itself is to be> >// deleted> >if> (index ==>0> && currNode !=>null>) {> >list.head = currNode.next;>// Changed head> >// Display the message> >System.out.println(> >index +>' position element deleted'>);> >// Return the updated List> >return> list;> >}> >//> >// CASE 2:> >// If the index is greater than 0 but less than the> >// size of LinkedList> >//> >// The counter> >int> counter =>0>;> >// Count for the index to be deleted,> >// keep track of the previous node> >// as it is needed to change currNode.next> >while> (currNode !=>null>) {> >if> (counter == index) {> >// Since the currNode is the required> >// position Unlink currNode from linked list> >prev.next = currNode.next;> >// Display the message> >System.out.println(> >index +>' position element deleted'>);> >break>;> >}> >else> {> >// If current position is not the index> >// continue to next node> >prev = currNode;> >currNode = currNode.next;> >counter++;> >}> >}> >// If the position element was found, it should be> >// at currNode Therefore the currNode shall not be> >// null> >//> >// CASE 3: The index is greater than the size of the> >// LinkedList> >//> >// In this case, the currNode should be null> >if> (currNode ==>null>) {> >// Display the message> >System.out.println(> >index +>' position element not found'>);> >}> >// return the List> >return> list;> >}> >// **************MAIN METHOD**************> >// method to create a Singly linked list with n nodes> >public> static> void> main(String[] args)> >{> >/* Start with the empty list. */> >LinkedList list =>new> LinkedList();> >//> >// ******INSERTION******> >//> >// Insert the values> >list = insert(list,>1>);> >list = insert(list,>2>);> >list = insert(list,>3>);> >list = insert(list,>4>);> >list = insert(list,>5>);> >list = insert(list,>6>);> >list = insert(list,>7>);> >list = insert(list,>8>);> >// Print the LinkedList> >printList(list);> >//> >// ******DELETION AT POSITION******> >//> >// Delete node at position 0> >// In this case the key is ***at head***> >deleteAtPosition(list,>0>);> >// Print the LinkedList> >printList(list);> >// Delete node at position 2> >// In this case the key is present ***in the> >// middle***> >deleteAtPosition(list,>2>);> >// Print the LinkedList> >printList(list);> >// Delete node at position 10> >// In this case the key is ***not present***> >deleteAtPosition(list,>10>);> >// Print the LinkedList> >printList(list);> >}> }> |
>
>Sortida
LinkedList: 1 2 3 4 5 6 7 8 0 position element deleted LinkedList: 2 3 4 5 6 7 8 2 position element deleted LinkedList: 2 3 5 6 7 8 10 position element not found LinkedList: 2 3 5 6 7 8>
Totes les operacions:
A continuació es mostra el programa complet que aplica cada operació conjuntament:
Java
import> java.io.*;> // Java program to implement> // a Singly Linked List> public> class> LinkedList {> >Node head;>// head of list> >// Linked list Node.> >// Node is a static nested class> >// so main() can access it> >static> class> Node {> >int> data;> >Node next;> >// Constructor> >Node(>int> d)> >{> >data = d;> >next =>null>;> >}> >}> >// **************INSERTION**************> >// Method to insert a new node> >public> static> LinkedList insert(LinkedList list,> >int> data)> >{> >// Create a new node with given data> >Node new_node =>new> Node(data);> >new_node.next =>null>;> >// If the Linked List is empty,> >// then make the new node as head> >if> (list.head ==>null>) {> >list.head = new_node;> >}> >else> {> >// Else traverse till the last node> >// and insert the new_node there> >Node last = list.head;> >while> (last.next !=>null>) {> >last = last.next;> >}> >// Insert the new_node at last node> >last.next = new_node;> >}> >// Return the list by head> >return> list;> >}> >// **************TRAVERSAL**************> >// Method to print the LinkedList.> >public> static> void> printList(LinkedList list)> >{> >Node currNode = list.head;> >System.out.print(>'
LinkedList: '>);> >// Traverse through the LinkedList> >while> (currNode !=>null>) {> >// Print the data at current node> >System.out.print(currNode.data +>' '>);> >// Go to next node> >currNode = currNode.next;> >}> >System.out.println(>'
'>);> >}> >// **************DELETION BY KEY**************> >// Method to delete a node in the LinkedList by KEY> >public> static> LinkedList deleteByKey(LinkedList list,> >int> key)> >{> >// Store head node> >Node currNode = list.head, prev =>null>;> >//> >// CASE 1:> >// If head node itself holds the key to be deleted> >if> (currNode !=>null> && currNode.data == key) {> >list.head = currNode.next;>// Changed head> >// Display the message> >System.out.println(key +>' found and deleted'>);> >// Return the updated List> >return> list;> >}> >//> >// CASE 2:> >// If the key is somewhere other than at head> >//> >// Search for the key to be deleted,> >// keep track of the previous node> >// as it is needed to change currNode.next> >while> (currNode !=>null> && currNode.data != key) {> >// If currNode does not hold key> >// continue to next node> >prev = currNode;> >currNode = currNode.next;> >}> >// If the key was present, it should be at currNode> >// Therefore the currNode shall not be null> >if> (currNode !=>null>) {> >// Since the key is at currNode> >// Unlink currNode from linked list> >prev.next = currNode.next;> >// Display the message> >System.out.println(key +>' found and deleted'>);> >}> >//> >// CASE 3: The key is not present> >//> >// If key was not present in linked list> >// currNode should be null> >if> (currNode ==>null>) {> >// Display the message> >System.out.println(key +>' not found'>);> >}> >// return the List> >return> list;> >}> >// **************DELETION AT A POSITION**************> >// Method to delete a node in the LinkedList by POSITION> >public> static> LinkedList> >deleteAtPosition(LinkedList list,>int> index)> >{> >// Store head node> >Node currNode = list.head, prev =>null>;> >//> >// CASE 1:> >// If index is 0, then head node itself is to be> >// deleted> >if> (index ==>0> && currNode !=>null>) {> >list.head = currNode.next;>// Changed head> >// Display the message> >System.out.println(> >index +>' position element deleted'>);> >// Return the updated List> >return> list;> >}> >//> >// CASE 2:> >// If the index is greater than 0 but less than the> >// size of LinkedList> >//> >// The counter> >int> counter =>0>;> >// Count for the index to be deleted,> >// keep track of the previous node> >// as it is needed to change currNode.next> >while> (currNode !=>null>) {> >if> (counter == index) {> >// Since the currNode is the required> >// position Unlink currNode from linked list> >prev.next = currNode.next;> >// Display the message> >System.out.println(> >index +>' position element deleted'>);> >break>;> >}> >else> {> >// If current position is not the index> >// continue to next node> >prev = currNode;> >currNode = currNode.next;> >counter++;> >}> >}> >// If the position element was found, it should be> >// at currNode Therefore the currNode shall not be> >// null> >//> >// CASE 3: The index is greater than the size of the> >// LinkedList> >//> >// In this case, the currNode should be null> >if> (currNode ==>null>) {> >// Display the message> >System.out.println(> >index +>' position element not found'>);> >}> >// return the List> >return> list;> >}> >// **************MAIN METHOD**************> >// method to create a Singly linked list with n nodes> >public> static> void> main(String[] args)> >{> >/* Start with the empty list. */> >LinkedList list =>new> LinkedList();> >//> >// ******INSERTION******> >//> >// Insert the values> >list = insert(list,>1>);> >list = insert(list,>2>);> >list = insert(list,>3>);> >list = insert(list,>4>);> >list = insert(list,>5>);> >list = insert(list,>6>);> >list = insert(list,>7>);> >list = insert(list,>8>);> >// Print the LinkedList> >printList(list);> >//> >// ******DELETION BY KEY******> >//> >// Delete node with value 1> >// In this case the key is ***at head***> >deleteByKey(list,>1>);> >// Print the LinkedList> >printList(list);> >// Delete node with value 4> >// In this case the key is present ***in the> >// middle***> >deleteByKey(list,>4>);> >// Print the LinkedList> >printList(list);> >// Delete node with value 10> >// In this case the key is ***not present***> >deleteByKey(list,>10>);> >// Print the LinkedList> >printList(list);> >//> >// ******DELETION AT POSITION******> >//> >// Delete node at position 0> >// In this case the key is ***at head***> >deleteAtPosition(list,>0>);> >// Print the LinkedList> >printList(list);> >// Delete node at position 2> >// In this case the key is present ***in the> >// middle***> >deleteAtPosition(list,>2>);> >// Print the LinkedList> >printList(list);> >// Delete node at position 10> >// In this case the key is ***not present***> >deleteAtPosition(list,>10>);> >// Print the LinkedList> >printList(list);> >}> }> |
>
casos de prova conjunta
>Sortida
LinkedList: 1 2 3 4 5 6 7 8 1 found and deleted LinkedList: 2 3 4 5 6 7 8 4 found and deleted LinkedList: 2 3 5 6 7 8 10 not found LinkedList: 2 3 5 6 7 8 0 position element deleted LinkedList: 3 5 6 7 8 2 position element deleted LinkedList: 3 5 7 8 10 position element not found LinkedList: 3 5 7 8>