En Abstract datatype ( ADT ) liste , eller lenket liste som det er mer ofte kalles, er en av de grunnleggende datastrukturer i informatikk og en av de første alternativene til den enkle matrise lært av en informatikk student. Selv om det ofrer muligheten til å flytte til midten av listen uten å søke gjennom listen først , gjør ADT liste det trivially lett å utvide og krympe de lagrede data . Denne koden er implementert i Java , siden Java sin innebygde Linked List datastruktur tillater oss å komme direkte til poenget, men den samme logikken kunne gjennomføres med minimum endring på andre C -lignende språk . Instruksjoner
en

Lag dine to koblede lister og starte dem med noen sorterte data ved å lime inn følgende i en Java -fil : en

LinkedList list1 = new LinkedList ( ) ;

LinkedList list2 = new LinkedList ();

for ( int x = 0 ; x < 100; x + + ) du har to koblede lister fylt med tilfeldige tall som har blitt sortert
2

Opprett en ny Lenket liste for å holde det fusjonerte listen ved å lime inn følgende : .

LinkedList fusjonert = new LinkedList ();
3

Sett opp en enkel mens loop . Denne sløyfen vil fortsette så lenge begge listene har minst ett element i dem , og det vil flytte den minste av de beste elementene til den sammenslåtte liste : .

//Mens begge listene er ikke tomme

mens ( ! list1.isEmpty ( ) && ! ​​list2.isEmpty ( ) ) {

if ( list1.peek ( ) < = list2.peek ( ) ) {

fusjonert . add ( list1.pop ( ));

} else {

merged.add ( list2.pop ( ));

}

}

" Peek "-kommandoen ser på elementet i fronten av listen , mens " Pop" både ser på elementet og fjerner den . Når sammenligningen er gjort, du bare ønsker å titte på toppen av listen for å se hvilke som er mindre. Når det gjelder tid til å flette listene , ønsker du å ta bort den øverste verdien og sette den på de nye listene .
4

Fullfør jobben . Så snart enten er tom , er det ikke nødvendig å fortsette med å gjøre sammenligninger. Derfor er de gamle sløyfe endene , og en annen sløyfe opprettet for å fylle resten av det fusjonerte liste med resten av dataene i den siste listen:

//Mens den første listen er ikke tom

mens {

merged.add ( list1.pop ( ));

} ( list1.isEmpty ( ) ! )

//mens den andre listen ikke er tom.

mens {

merged.add ( list2.pop ( ));

} ( list2.isEmpty ( ) ! )
5

skrive ut resultatene slik at du kan inspisere det fusjonerte listen og sikre at det fungerte riktig : en

int x = 1;

for ( Double y: fusjonert ) {

System. out.println ( x + " " + y ) ;

x + +;

}