Předpoklad: Stejně jako pole je i Linked List lineární datová struktura. Na rozdíl od polí nejsou prvky propojeného seznamu uloženy na souvislém místě, prvky jsou propojeny pomocí ukazatelů, jak je znázorněno níže.

Stejně jako pole je i Linked List lineární datová struktura. Na rozdíl od polí nejsou prvky propojeného seznamu uloženy na souvislém místě, prvky jsou propojeny pomocí ukazatelů, jak je uvedeno níže.

V Javě může být LinkedList reprezentován jako třída a Node jako samostatná třída. Třída LinkedList obsahuje odkaz na typ třídy Node.

Jáva

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; }> > }> }>

Vytvoření a vložení:

V tomto článku se vkládání do seznamu provádí na konci, to znamená, že nový uzel je přidán za poslední uzel daného Propojeného seznamu. Pokud je například daný propojený seznam 5->10->15->20->25 a má se vložit 30, pak bude propojený seznam 5->10->15->20->25->30 .
Vzhledem k tomu, že propojený seznam je obvykle reprezentován jeho hlavním ukazatelem, je nutné procházet seznamem až k poslednímu uzlu a poté změnit předposlední uzel na nový uzel.

Implementace:

Jáva

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);> > }> }>

Výstup

LinkedList: 1 2 3 4 5 6 7 8 

Průjezd: Pro procházení je níže uvedena obecná funkce printList(), která vytiskne libovolný daný seznam procházením seznamu od hlavního uzlu k poslednímu.

Implementace:

Jáva

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);> > }> }>

Výstup

LinkedList: 1 2 3 4 5 6 7 8 

Smazání pomocí KEY:

Proces mazání lze chápat takto:

Je třeba udělat:

Je-li uveden „klíč“, odstraňte první výskyt tohoto klíče v propojeném seznamu .

Jak to udělat:

Chcete-li odstranit uzel z propojeného seznamu, proveďte následující kroky.

1. Vyhledejte klíč pro jeho první výskyt v seznamu
2. Nyní může existovat kterákoli ze 3 podmínek:
   • Případ 1: Klíč se nachází na hlava
     1. V tomto případě změňte hlavičku uzlu na další uzel aktuální hlavičky.
        
     2. Uvolněte paměť nahrazeného hlavního uzlu.
   • Případ 2: Klíč se nachází uprostřed nebo na posledním místě, kromě u hlava
     1. V tomto případě vyhledejte předchozí uzel uzlu, který chcete odstranit.
     2. Změňte další předchozí uzel na další uzel aktuálního uzlu.
     3. Uvolněte paměť nahrazeného uzlu.
   • Případ 3: Klíč nebyl v seznamu nalezen
     1. V tomto případě není třeba provádět žádnou operaci.

Implementace:

Jáva

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);> > }> }>

Výstup

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 

Smazání na pozici:

Tento proces mazání lze chápat takto:

Je třeba udělat:
Vzhledem k a 'pozice' , odstraňte uzel na této pozici z propojeného seznamu .
Jak to udělat:

Kroky k tomu jsou následující:

1. Procházejte seznam počítáním indexu uzlů
2. U každého indexu přiřaďte index tak, aby byl stejný jako pozice
3. Nyní může existovat kterákoli ze 3 podmínek:
   • Případ 1: Pozice je 0, tj. hlava má být vymazána
     1. V tomto případě změňte hlavičku uzlu na další uzel aktuální hlavičky.
        
     2. Uvolněte paměť nahrazeného hlavního uzlu.
   • Případ 2: Pozice je větší než 0, ale menší než velikost seznamu, tj. uprostřed nebo na konci, s výjimkou hlavy
     1. V tomto případě Najít předchozí uzel uzlu, který má být odstraněn.
        
     2. Změňte další z předchozího uzlu na další uzel aktuálního uzlu.
     3. Uvolněte paměť nahrazeného uzlu.
   • Případ 3: Pozice je větší než velikost seznamu, tj. pozice, která nebyla v seznamu nalezena
     1. V tomto případě není třeba provádět žádnou operaci.

Implementace:

Jáva

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);> > }> }>

Výstup

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 

Všechny operace:

Níže je kompletní program, který aplikuje každou operaci dohromady:

Jáva

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);> > }> }>

Výstup

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