IMPLEMENTERING AF EN LINKET LISTE I JAVA VED HJÆLP AF CLASS

Forudsætning: Ligesom arrays er Linked List en lineær datastruktur. I modsætning til arrays gemmes linkede listeelementer ikke på den sammenhængende placering, elementerne er forbundet ved hjælp af pointere som vist nedenfor.

linket liste

Ligesom arrays er Linked List en lineær datastruktur. I modsætning til arrays gemmes linkede listeelementer ikke på den sammenhængende placering, elementerne er forbundet ved hjælp af pointere som vist nedenfor.

I Java kan LinkedList repræsenteres som en klasse og en Node som en separat klasse. Klassen LinkedList indeholder en reference af Node-klassetypen.

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

Oprettelse og indsættelse:

I denne artikel sker indsættelse i listen til sidst, det vil sige, at den nye node tilføjes efter den sidste node på den givne linkede liste. For eksempel, hvis den givne linkede liste er 5->10->15->20->25 og 30 skal indsættes, så bliver den linkede liste 5->10->15->20->25->30 .
Da en sammenkædet liste typisk repræsenteres af dens hovedmarkør, er det nødvendigt at krydse listen indtil den sidste node og derefter ændre den næstsidste node til den nye node.

linkedlist_insert_last

Implementering:

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

Produktion

LinkedList: 1 2 3 4 5 6 7 8>

Gennemgang: For traversering er nedenfor en generel funktion printList(), der udskriver en given liste ved at krydse listen fra hovedknudepunktet til det sidste.

Implementering:

Java

Produktion

LinkedList: 1 2 3 4 5 6 7 8>

Sletning med KEY:

Sletningsprocessen kan forstås som følger:

Gøres:

Givet en 'nøgle', skal du slette den første forekomst af denne nøgle i den sammenkædede liste .

Hvordan gør man det:

For at slette en node fra den sammenkædede liste skal du udføre følgende trin.

Søg på nøglen efter dens første forekomst på listen

Nu kan enhver af de 3 betingelser være der:

Case 1: Nøglen findes ved hoved

I dette tilfælde skal du ændre hovedet på noden til den næste node på det nuværende hoved.

Frigør hukommelsen for den udskiftede hovedknude.

Tilfælde 2: Nøglen findes i midten eller sidst, undtagen ved hoved

I dette tilfælde skal du finde den forrige node for den node, der skal slettes.

Skift den næste den forrige node til den næste node i den aktuelle node.

Frigør hukommelsen for den erstattede node.

Tilfælde 3: Nøglen findes ikke på listen

I dette tilfælde skal der ikke foretages nogen handling.

linkedlist_deletion

Implementering:

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

Produktion

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>

Sletning ved position:

Denne sletningsproces kan forstås som følger:

Gøres:
Givet en 'position' , slet noden på denne position fra den linkede liste .
Hvordan gør man det:

Trinene til at gøre det er som følger:

Gennemse listen ved at tælle nodernes indeks

For hvert indeks skal du matche indekset for at være det samme som position

Nu kan enhver af de 3 betingelser være der:

Case 1: Positionen er 0, dvs. hovedet skal slettes

I dette tilfælde skal du ændre nodens hoved til den næste node for det nuværende hoved.

Frigør hukommelsen for den udskiftede hovedknude.

Tilfælde 2: Positionen er større end 0, men mindre end listens størrelse, dvs. i midten eller sidst, undtagen ved hovedet

I dette tilfælde, Find forrige node for den node, der skal slettes.

Skift den næste af forrige node til den næste node af den nuværende node.

Frigør hukommelsen for den udskiftede node.

Case 3: Positionen er større end listens størrelse, dvs. positionen findes ikke på listen

I dette tilfælde skal der ikke foretages nogen handling.

linkedlist_deletion

Implementering:

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

Produktion

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>

Alle operationer:

Nedenfor er det komplette program, der anvender hver operation sammen:

Java

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

overvåget maskinlæring

Produktion

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>

TechCodeview

Java

Java

Java

Java

Java

Java