Java >> Tutoriel Java >  >> Java

Questions et réponses de l'entretien sur la structure de données de la liste chaînée supérieure

Structure des données de la liste liée

Une liste chaînée est une structure de données linéaire où chaque élément est un objet distinct. Voici la question la plus fréquemment posée dans l'interview Java. Une liste chaînée est l'un des sujets les plus appréciés lors du processus d'entretien sur la structure des données et les algorithmes.

Nous partons de la base :

Voici le code de LinkedList, comme vous le savez java JDK fournissant déjà une collection de structure de données. Donc la classe LinkedList déjà fournie dans java.util. Ici, nous partageons un niveau de connaissance de base de LinkedList. Commencez donc par le programme pour créer une LinkedList simple, puis passez à un niveau plus profond.

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

Maintenant, commençons les questions d'entretien les plus courantes et les plus importantes sur la structure de données de la liste liée en Java. C'est également une question importante pour les développeurs d'applications Android.

Question 1 . Comment trouver la longueur d'une liste chaînée (itérative et récursive)

Réponse : Itératif : L'itération est appliqué à l'ensemble d'instructions que nous voulons faire exécuter de manière répétée.

Récursif : Récursivité est un processus, où l'instruction dans un corps de fonction appelle la fonction elle-même.

Le codage est ici Trouver la longueur d'une liste liée

Question 2. Comment insérer un nouveau nœud dans une structure de données de liste chaînée

Réponse : L'insertion d'un nouveau nœud dans la liste liée peut faire 3 façons.

  • Au début de la liste liée
  • Au milieu de la liste liée
  • À la fin de la liste liée

Voici les 3 façons d'insérer des données dans une liste liée avec du code : Insérer un nouveau nœud dans une liste liée

Question n° 3. Dans une liste liée, trouvez le milieu de la liste et imprimez le numéro.

Entrée :-> 4-> 2-> 7-> 9-> 1

Sortie :7

#Single pointer approach

Dans cette approche, nous allons scanner toute la liste et compter le nombre de nœuds. Nous divisons le nombre par 2, puis parcourons à nouveau la liste jusqu'à ce nœud.

#Using 2 pointers

Avec 2 pointeurs pour parcourir la liste, nous pouvons trouver le milieu de la liste avec un seul balayage sur la liste liée.

  • pointer1 parcourt un nœud à la fois
  • pointe2 parcourt deux nœuds à la fois.

Ainsi, lorsque pointer2 atteint la fin de la liste chaînée, pointer1 pointera au milieu de la liste liée.

Pour plus de détails et de code : Rechercher le milieu d'une liste chaînée donnée

Question n° 4. Étant donné une liste chaînée et un nombre n, écrivez un programme qui trouve la valeur au nième nœud à partir de la fin de la liste chaînée.

Réponse : Vous pouvez trouver nième nœud utilisant la longueur de la liste chaînée

  • Calculez la longueur de la liste liée. Suivez ce didacticiel Trouver la longueur d'une donnée de liste chaînée
  • Afficher le (len – n + 1)ème nœud à partir du début de la liste chaînée.

Tutoriel complet :Programmer le nième nœud à partir de la fin d'une liste chaînée

Question n° 5. Étant donné le pointeur vers le nœud principal d'une liste chaînée, la tâche consiste à inverser la liste chaînée. Vous devez inverser la liste en modifiant les liens entre les nœuds.

Solutions : Méthode itérative

1. Initialiser trois pointeurs

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

2. Parcourez la liste chaînée. Dans la boucle while, procédez comme suit.
//stocker le nœud suivant
currentNode = currentNode->nextNode

// Inverse les pointeurs de nœud

currentNode -> next = previousNode 

// Avancer d'un pas le nœud précédent et actuel
previousNode = currentNode
currentNode = nextNode

exemple de code complet consultez ce post :inverser une structure de données de liste liée en java


Balise Java