Java >> Java tutorial >  >> Java

Top Linked List datastruktur interview spørgsmål og svar

Java

Linked List Datastruktur

En sammenkædet liste er en lineær datastruktur, hvor hvert element er et separat objekt. Her er det øverste (oftest) stillede spørgsmål i Java-interviewet. En sammenkædet liste er et af de mest foretrukne emner under datastruktur- og algoritmeinterviewprocessen.

Vi starter fra grundlæggende :

Her er koden til LinkedList, som du ved, java JDK leverer allerede en samling af datastruktur. Så LinkedList -klassen findes allerede i java.util. Her deler vi et grundlæggende kendskab til LinkedList. Så start med programmet, hvordan du opretter en simpel LinkedList, og gå derefter til et dybt niveau.

package in.eyehunt.data.struc;

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;
        Node(int d) {
            data = d;
            next = null;
        }
    }
    // Method to print all nodes
    public void printList() {
        Node n = head;
        System.out.print(" head");
        while (n != null) {
            System.out.print(" -> " + n.data);
            n = n.next;
        }
    }
    public static void main(String a[]) {
        //create a simple linked list with 5 nodes
        LinkedList linkedList = new LinkedList();
        linkedList.head = new Node(2);
        Node second = new Node(4);
        Node third = new Node(5);
        Node fourth = new Node(2);
        Node fifth = new Node(1);

        linkedList.head.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        fifth.next = null;// not needed to assign null
        linkedList.printList();
    }
}

Lad os nu starte de mest almindelige og øverste linkede liste-datastrukturinterviewspørgsmål i Java. Det er også et vigtigt spørgsmål for Android-appudviklere.

Spørgsmål 1 . Sådan finder du længden af ​​en sammenkædet liste (iterativ og rekursiv)

Svar: Iterativ : Iterationen anvendes på det sæt instruktioner, som vi ønsker at få udført gentagne gange.

Rekursiv : Rekursion er en proces, hvor udsagn i en funktionstekst kalder selve funktionen.

Kodning er her Find længden af ​​en LinkedList

Spørgsmål 2. Sådan indsætter du en ny node i en linket listedatastruktur

Svar: Indsættelse af ny node i linket liste kan gøre 3 måder.

  • I starten af ​​den linkede liste
  • Midt på den linkede liste
  • I slutningen af ​​den linkede liste

Her er alle 3 måder at indsætte data på i linket liste med kode: Indsæt en ny node i en linket liste

Spørgsmål #3. I givet en linket liste skal du finde midten af ​​listen og udskrive nummeret.

Indgang:-> 4-> 2-> 7-> 9-> 1

Udgang:7

#Single pointer approach

I denne tilgang vil vi scanne hele listen og tælle antallet af noder. Vi dividerer tallet med 2 og krydser så igen listen op til den node.

#Using 2 pointers

Med 2 pointere til at krydse listen, kan vi finde midten af ​​listen med kun én scanning på den linkede liste.

  • pointer1 rejser én node ad gangen
  • pointe2 rejser to noder ad gangen.

Således, når pointer2 når slutningen af ​​den linkede liste, pointer1 vil pege på midten af ​​den linkede liste.

For flere detaljer og kode: Find midten af ​​en given linket liste

Spørgsmål #4. Givet en sammenkædet liste og et tal n, skriv et program, der finder værdien ved den n'te node fra slutningen af ​​den sammenkædede liste.

Svar: Du kan finde n’t node ved hjælp af længden af ​​linket liste

  • Beregn længden af ​​linket liste. Følg denne vejledning Find længden af ​​en linket listedata
  • Udskriv den (len – n + 1) node fra begyndelsen af ​​den linkede liste.

Komplet selvstudium:Programmer til n'te node fra slutningen af ​​en linket liste

Spørgsmål #5. Givet markøren til hovedknudepunktet på en linket liste, er opgaven at vende den linkede liste. Du skal vende listen ved at ændre links mellem noder.

Løsninger: Iterativ metode

1. Initialiser tre pointere

currentNode = head; nextNode = null; previousNode = null;

2. Gentag gennem den linkede liste. I while-løkke, gør følgende.
//store næste node
currentNode = currentNode->nextNode

// Vend nodemarkører

currentNode -> next = previousNode 

// Flyt forrige og nuværende node et skridt frem
previousNode = currentNode
currentNode = nextNode

komplet kodeeksempel tjek dette indlæg:Vend en linket listedatastruktur i java


Java tag