Hoe maak ik een gekoppelde lijstgegevensstructuur in Java?

Wat is de beste manier om een ​​gekoppelde lijst in Java te maken?

Antwoord 1, autoriteit 100%

De voor de hand liggende oplossing voor ontwikkelaars die bekend zijn met Java is om de klasse LinkedListte gebruiken die al in java.utilstaat. Stel echter dat u om de een of andere reden uw eigen implementatie wilde maken. Hier is een snel voorbeeld van een gekoppelde lijst die een nieuwe link aan het begin van de lijst invoegt, vanaf het begin van de lijst verwijdert en door de lijst loopt om de links die erin staan ​​af te drukken. Verbeteringenaan deze implementatie omvatten het maken van een dubbel-gelinkte lijst, het toevoegen van methoden aan invoegenen verwijderenvanuit het midden of end, en door ook de methoden geten sorttoe te voegen.

Opmerking: In het voorbeeld bevat het Link-object eigenlijk geen ander Link-object – nextLinkis eigenlijk alleen een verwijzing naar een andere link.

class Link {
    public int data1;
    public double data2;
    public Link nextLink;
    //Link constructor
    public Link(int d1, double d2) {
        data1 = d1;
        data2 = d2;
    }
    //Print Link data
    public void printLink() {
        System.out.print("{" + data1 + ", " + data2 + "} ");
    }
}
class LinkList {
    private Link first;
    //LinkList constructor
    public LinkList() {
        first = null;
    }
    //Returns true if list is empty
    public boolean isEmpty() {
        return first == null;
    }
    //Inserts a new Link at the first of the list
    public void insert(int d1, double d2) {
        Link link = new Link(d1, d2);
        link.nextLink = first;
        first = link;
    }
    //Deletes the link at the first of the list
    public Link delete() {
        Link temp = first;
        if(first == null){
         return null;
         //throw new NoSuchElementException(); // this is the better way. 
        }
        first = first.nextLink;
        return temp;
    }
    //Prints list data
    public void printList() {
        Link currentLink = first;
        System.out.print("List: ");
        while(currentLink != null) {
            currentLink.printLink();
            currentLink = currentLink.nextLink;
        }
        System.out.println("");
    }
}  
class LinkListTest {
    public static void main(String[] args) {
        LinkList list = new LinkList();
        list.insert(1, 1.01);
        list.insert(2, 2.02);
        list.insert(3, 3.03);
        list.insert(4, 4.04);
        list.insert(5, 5.05);
        list.printList();
        while(!list.isEmpty()) {
            Link deletedLink = list.delete();
            System.out.print("deleted: ");
            deletedLink.printLink();
            System.out.println("");
        }
        list.printList();
    }
}

Antwoord 2, autoriteit 25%

Java heeft een LinkedListimplementatie, die u misschien wilt bekijken. Je kunt de JDK en de bijbehorende bronnen downloaden op java.sun.com.

Antwoord 3, autoriteit 10%

Gebruik java.util.LinkedList. Zoals dit:

list = new java.util.LinkedList()

Antwoord 4, autoriteit 8%

De bovenstaande gekoppelde lijst wordt in tegengestelde richting weergegeven. Ik denk dat de juiste implementatie van de invoegmethode zou moeten zijn

public void insert(int d1, double d2) { 
    Link link = new Link(d1, d2); 
    if(first==null){
        link.nextLink = null;
        first = link; 
        last=link;
    }
    else{
        last.nextLink=link;
        link.nextLink=null;
        last=link;
    }
} 

Antwoord 5, autoriteit 5%

Het is veel beter om java.util.LinkedList te gebruiken, omdat het waarschijnlijk veel beter is geoptimaliseerd dan degene die u gaat schrijven.

Antwoord 6, autoriteit 3%

//slightly improved code without using collection framework
package com.test;
public class TestClass {
    private static Link last;
    private static Link first;
    public static void main(String[] args) {
        //Inserting
        for(int i=0;i<5;i++){
            Link.insert(i+5);
        }
        Link.printList();
        //Deleting
        Link.deletefromFirst();
        Link.printList();
    }
    protected  static class Link {
        private int data;
        private Link nextlink;
        public Link(int d1) {
            this.data = d1;
        }
        public static void insert(int d1) {
            Link a = new Link(d1);
            a.nextlink = null;
            if (first != null) {
                last.nextlink = a;
                last = a;
            } else {
                first = a;
                last = a;
            }
            System.out.println("Inserted -:"+d1);
        }
        public static void deletefromFirst() {
            if(null!=first)
            {
                System.out.println("Deleting -:"+first.data);
                first = first.nextlink;
            }
            else{
                System.out.println("No elements in Linked List");
            }
        }
        public static void printList() {
            System.out.println("Elements in the list are");
            System.out.println("-------------------------");
            Link temp = first;
            while (temp != null) {
                System.out.println(temp.data);
                temp = temp.nextlink;
            }
        }
    }
}