Jak utworzyć strukturę danych listy połączonej w języku Java? [Zamknięte]

135

Jaki jest najlepszy sposób tworzenia połączonej listy w Javie?

Lance Fisher
źródło
33
Najlepszym sposobem utworzenia listy połączonej jest użycie wbudowanej listy połączonej. Nie pisz ponownie wbudowanych klas.
Peter Lawrey
21
to pytanie jest uzasadnione i bardzo konstruktywne dla dyskusji programistów
anshulkatta

Odpowiedzi:

220

Oczywistym rozwiązaniem dla programistów znających Javę jest użycie klasy LinkedList już dostarczonej w java.util . Załóżmy jednak, że z jakiegoś powodu chciałeś stworzyć własną implementację. Oto szybki przykład połączonej listy, która wstawia nowe łącze na początku listy, usuwa od początku listy i przechodzi przez listę, aby wydrukować zawarte w niej łącza. Udoskonalenia tej implementacji obejmują utworzenie podwójnie połączonej listy , dodanie metod wstawiania i usuwania od środka lub końca, a także dodawanie metod pobierania i sortowania .

Uwaga : W tym przykładzie obiekt Link w rzeczywistości nie zawiera innego obiektu Link - nextLink jest w rzeczywistości tylko odniesieniem do innego łącza.

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();
    }
}
Aaron
źródło
7
możesz również dość łatwo ulepszyć ten kod, aby używać typów ogólnych dla typu danych, zamiast przechowywać int i double.
shsteimer
51
@shsteimer: całkiem zdecydowanie, ale ponieważ prawie jedynym dobrym zastosowaniem tego kodu jest zademonstrowanie techniki, nikomu nie pomoże. To tylko rozproszyłoby podstawową ideę.
Joachim Sauer
8
Nie jest dobrym podejściem OO mieć public Link nextLinki operować na nim poza zajęciami. To mogłoby być godne szacunku, Linkgdyby była to klasa wewnętrzna LinkList. Jest to kolejna porcja kodu napisana, ponieważ Java była tylko inną wersją-c.
Bart,
1
Po wstawieniu pierwszy element nigdy nie otrzyma następnego linku - chyba że brakuje mi czegoś z odniesieniami do języka Java
Chris S
Jak mogę zaimplementować metodę delete (index)?
JohnDow,
55

Java ma implementację LinkedList , którą możesz chcieć sprawdzić. Możesz pobrać JDK i jego źródła pod adresem java.sun.com .

dlinsin
źródło
Czy Linkedlist w Javie nie pozwala na wstawianie i usuwanie elementów w dowolnych pozycjach?
Seun Osewa,
10
Czy nie o to chodzi w połączonej liście?
jrockway
2
@Seun Osewa, jeśli chcesz dodać w dowolnej pozycji, użyj ArrayList :)
headgrowe
3
Zamiast pobierać pakiet JDK, aby wyświetlić jego implementację LinkedList, możesz po prostu wyświetlić jego LinkedList.javawersję online tutaj . Ta strona podświetla nawet składnię i renderuje komentarze Javadoc w tekście.
Rory O'Kane
17

Powyższa połączona lista jest wyświetlana w przeciwnym kierunku. Myślę, że powinno być poprawne wykonanie metody wstawiania

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;
    }
} 
arnab sarkar
źródło
1
Dodaj nowy na końcu, chyba że określono inaczej. :-)
9

O wiele lepiej jest używać java.util.LinkedList, ponieważ jest prawdopodobnie znacznie bardziej zoptymalizowana niż ta, którą napiszesz.

Jakub Arnold
źródło
15
I zadziała za pierwszym razem.
Peter Lawrey
7
//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;
            }
        }
    }
}
Anitha A.
źródło