Būtina sąlyga: Kaip ir masyvai, susietasis sąrašas yra linijinė duomenų struktūra. Skirtingai nuo masyvų, susieti sąrašo elementai nėra saugomi gretimoje vietoje, elementai susiejami naudojant rodykles, kaip parodyta toliau.

Kaip ir masyvai, susietasis sąrašas yra linijinė duomenų struktūra. Skirtingai nuo masyvų, susieti sąrašo elementai nėra saugomi gretimoje vietoje, elementai susiejami naudojant rodykles, kaip parodyta toliau.

Java programoje LinkedList gali būti vaizduojamas kaip klasė, o mazgas - kaip atskira klasė. „LinkedList“ klasėje yra „Node“ klasės tipo nuoroda.

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

Sukūrimas ir įterpimas:

Šiame straipsnyje įterpimas į sąrašą atliekamas pabaigoje, ty naujas mazgas pridedamas po paskutinio nurodyto susietojo sąrašo mazgo. Pavyzdžiui, jei nurodytas susietas sąrašas yra 5->10->15->20->25 ir turi būti įterptas 30, susietas sąrašas tampa 5->10->15->20->25->30 .
Kadangi susietą sąrašą paprastai vaizduoja jo pagrindinė žymeklis, reikia pereiti sąrašą iki paskutinio mazgo, o tada pakeisti kitą mazgą į naują mazgą.

Įgyvendinimas:

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

Išvestis

LinkedList: 1 2 3 4 5 6 7 8 

Perėjimas: Norėdami pereiti, žemiau yra bendrosios paskirties funkcija printList(), kuri spausdina bet kurį nurodytą sąrašą perkeldama sąrašą nuo pagrindinio mazgo iki paskutinio.

Įgyvendinimas:

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

Išvestis

LinkedList: 1 2 3 4 5 6 7 8 

Ištrynimas pagal KEY:

Ištrynimo procesą galima suprasti taip:

Pabaigti:

Gavus „raktą“, ištrinkite pirmąjį šio rakto atvejį susietame sąraše .

Kaip tai padaryti:

Norėdami ištrinti mazgą iš susieto sąrašo, atlikite šiuos veiksmus.

1. Ieškokite rakto, ar jis pirmą kartą pasitaiko sąraše
2. Dabar gali būti bet kuri iš 3 sąlygų:
   • 1 atvejis: raktas yra adresu galva
     1. Tokiu atveju pakeiskite mazgo galvutę į kitą dabartinės galvutės mazgą.
        
     2. Atlaisvinkite pakeisto galvos mazgo atmintį.
   • 2 atvejis: raktas yra viduryje arba paskutinis, išskyrus ties galva
     1. Tokiu atveju Raskite ankstesnį mazgo, kurį norite ištrinti, mazgą.
     2. Pakeiskite kitą ankstesnį mazgą į kitą dabartinio mazgo mazgą.
     3. Atlaisvinkite pakeisto mazgo atmintį.
   • 3 atvejis: raktas nerastas sąraše
     1. Tokiu atveju operacijos atlikti nereikia.

Įgyvendinimas:

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

Išvestis

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 

Ištrynimas vietoje:

Šį ištrynimo procesą galima suprasti taip:

Pabaigti:
Atsižvelgiant į a 'pozicija' , ištrinkite šioje pozicijoje esantį mazgą iš susieto sąrašo .
Kaip tai padaryti:

Veiksmai, kaip tai padaryti, yra tokie:

1. Pereikite sąrašą skaičiuodami mazgų indeksą
2. Kiekvienam indeksui suderinkite indeksą, kad jis atitiktų poziciją
3. Dabar gali būti bet kuri iš 3 sąlygų:
   • 1 atvejis: padėtis yra 0, ty galva turi būti ištrinta
     1. Tokiu atveju pakeiskite mazgo galvutę į kitą dabartinės galvos mazgą.
        
     2. Atlaisvinkite pakeisto galvos mazgo atmintį.
   • 2 atvejis: padėtis yra didesnė nei 0, bet mažesnė už sąrašo dydį, t. y. viduryje arba paskutinė, išskyrus priekyje
     1. Tokiu atveju Rasti ankstesnį mazgo, kurį reikia ištrinti, mazgą.
        
     2. Pakeiskite kitą ankstesnio mazgo į kitą dabartinio mazgo mazgą.
     3. Atlaisvinkite pakeisto mazgo atmintį.
   • 3 atvejis: pozicija yra didesnė už sąrašo dydį, t. y. pozicijos sąraše nerasta
     1. Tokiu atveju operacijos atlikti nereikia.

Įgyvendinimas:

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

Išvestis

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 

Visos operacijos:

Žemiau yra visa programa, kuri atlieka kiekvieną operaciją kartu:

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

Išvestis

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