Edellytys: Kuten taulukot, linkitetty lista on lineaarinen tietorakenne. Toisin kuin taulukot, linkitettyjä luetteloelementtejä ei tallenneta vierekkäiseen sijaintiin, vaan elementit linkitetään osoittimilla alla olevan kuvan mukaisesti.
Javassa LinkedList voidaan esittää luokkana ja Node erillisenä luokkana. LinkedList-luokka sisältää viittauksen Node-luokkatyyppiin.
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; }> >}> }> |
>
>
Luominen ja lisääminen:
Tässä artikkelissa lisäys luetteloon tehdään lopussa, eli uusi solmu lisätään annetun linkitetyn listan viimeisen solmun jälkeen. Jos esimerkiksi annettu linkitetty lista on 5->10->15->20->25 ja 30 on lisättävä, linkitetystä listasta tulee 5->10->15->20->25->30 .
Koska linkitettyä listaa edustaa tyypillisesti sen pääosoitin, se on kuljetettava luettelossa viimeiseen solmuun ja sitten vaihdettava seuraavaksi viimeinen solmu uudeksi solmuksi.
Toteutus:
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);> >}> }> |
>
>Lähtö
LinkedList: 1 2 3 4 5 6 7 8>
Läpikulku: Kuljetusta varten alla on yleiskäyttöinen funktio printList(), joka tulostaa minkä tahansa listan kulkemalla listan pääsolmusta viimeiseen.
Toteutus:
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);> >}> }> |
>
>Lähtö
LinkedList: 1 2 3 4 5 6 7 8>
Poisto avaimella:
Poistoprosessi voidaan ymmärtää seuraavasti:
Tullakseen tehdyksi:
Jos annetaan 'avain', poista tämän avaimen ensimmäinen esiintymä linkitetystä luettelosta .
Kuinka tehdä se:
Jos haluat poistaa solmun linkitetystä luettelosta, toimi seuraavasti.
- Etsi avaimesta sen ensimmäinen esiintyminen luettelossa
- Nyt mikä tahansa kolmesta ehdosta voi olla olemassa:
- Tapaus 1: Avain löytyy osoitteesta pää
- Vaihda tässä tapauksessa solmun pää nykyisen pään seuraavaan solmuun.
- Vapauta vaihdetun pääsolmun muisti.
- Tapaus 2: Avain löytyy keskeltä tai viimeisestä, paitsi kohdasta pää
- Tässä tapauksessa Etsi poistettavan solmun edellinen solmu.
- Muuta seuraava edellinen solmu nykyisen solmun seuraavaksi solmuksi.
- Vapauta korvatun solmun muisti.
- Tapaus 3: Avainta ei löydy luettelosta
- Tässä tapauksessa toimenpidettä ei tarvitse tehdä.
Toteutus:
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);> >}> }> |
>
>Lähtö
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>
Poisto sijainnista:
Tämä poistoprosessi voidaan ymmärtää seuraavasti:
Tullakseen tehdyksi:
Koska a 'asema' , poista tämän sijainnin solmu linkitetystä luettelosta .
Kuinka tehdä se:
Toimi seuraavasti:
- Selaa luetteloa laskemalla solmujen indeksit
- Yhdistä kunkin indeksin indeksi siten, että se on sama kuin sijainti
- Nyt mikä tahansa kolmesta ehdosta voi olla olemassa:
- Tapaus 1: Asento on 0, eli pää on poistettava
- Vaihda tässä tapauksessa solmun pää nykyisen pään seuraavaan solmuun.
- Vapauta vaihdetun pääsolmun muisti.
- Tapaus 2: Sijainti on suurempi kuin 0, mutta pienempi kuin luettelon koko, eli keskellä tai viimeisenä, paitsi kärjessä
- Tässä tapauksessa Etsi poistettavan solmun edellinen solmu.
- Muuta edellisen solmun seuraava nykyisen solmun seuraavaksi.
- Vapauta korvatun solmun muisti.
- Tapaus 3: Sijainti on suurempi kuin listan koko, eli paikkaa ei löydy luettelosta
- Tässä tapauksessa toimenpidettä ei tarvitse tehdä.
Toteutus:
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);> >}> }> |
>
>Lähtö
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>
Kaikki toiminnot:
Alla on täydellinen ohjelma, joka soveltaa jokaista toimintoa yhdessä:
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);> >}> }> |
>
python on numeerinen
>Lähtö
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>