Les meilleures façons de Parcourir dans une LinkedList - Java

La Situation

J'ai un entretien avec TripAdvisor demain et j'ai décidé pour la pratique de créer mon propre LinkedList. Je suis à essayer de comprendre la meilleure façon de parcourir à travers elle.

Principale Question: j'ai réussi à parcourir par le biais de ma Liste, mais je crois
il y a une meilleure façon de le faire. Comment voulez-vous traverser ?

Question Bonus: Comment faire de mon ensemble des classes de look ? Est-ce que je devrait/ne devrait pas ajouter ?
Il semble fonctionner très bien, mais est-il optimal ?

Question Bonus #2: Enfin, je me demandais si anyonehad toute la perspicacité de questions d'entrevue typiques/concepts que je dois savoir ?

Grandement apprécié.

Voici mes Classes

//*********************************Node Class*******************************************     
 public class Node<T> {
  Node<T> link;

  T data;

  public Node(T data) {

    this.data = data;
    link = null;

}

public T getData() {
    return data;

}

public Node<T> getLink() {

    return link;

}


public Node<T> setLink(Node<T> N) {

    this.link = N;
    return link;

}

public void setData(T newData) {

    this.data = newData;

}

}

    //****************************************Linked List Class*******************************

   public class LinkedList<T> {

Node<T> head;
T data;


public LinkedList(){
   head = null;
   }




public void add(T data){

    Node<T> newNode = new Node<T> (data);
    newNode.setLink(head);
    head = newNode;
}


  //had problems printing out the data in the last node

 public void traverse(){
    Node<T> pointer;
    pointer = head;

while (pointer.getLink()!=null){
        System.out.println(pointer.getData());
        pointer = pointer.setLink(pointer.getLink());
}

//Fixed problems For last node that doesnt get printed out
System.out.println(pointer.getData());

}

//Encore une fois est-il une meilleure façon de le faire ?
//Merci
}

Quel poste que vous convoitez?
Essayez de codereview.stackexchange.com
Pourquoi ne pouvez-vous pas simplement utiliser pointer = pointer.getLink();, et while (pointer != null) { (et supprimer votre dernier rapport d'Impression)
Les questions d'entrevue impliquant des listes liées généralement l'accent sur le "Supprimer" l'opération car il a peu intéressant bord-cas. Aussi une question d'entrevue à suivre quelque chose comme ce serait: "Comment voulez-vous détecter une circulaire de la liste liée, ou de l'un qui contient un cycle?"
Merci pour l'aperçu! Ne peux pas croire que je ne pense pas que la solution moi-même

OriginalL'auteur RonJermiah | 2013-10-29

  1. 5

    Je voudrais changer votre traversée de la fonction à être plus comme ceci:

    public void traverse(){
  Node<T> pointer = head;

  while (pointer != null){
    System.out.println(pointer.getData());
    pointer = pointer.getLink();
  }
}

    Aussi, il est courant de représenter le Nœud classe privée intérieure classe LinkedList, car il n'est généralement pas nécessaire n'importe où ailleurs.

    Autant que l'entretien lui-même va, traversée des questions les plus typiques pour les arbres (eg. imprimer les éléments dans l'ordre de tri). LinkedList questions sont plus porté sur les retirer/insérer des opérations qui exigent une attention minutieuse à la lisière des cas (ce qui se passe quand vous enlevez la tête par exemple). Un plus avancées LinkedList question serait de se demander comment détecter un cycle, je voudrais m'assurer que je savais au moins une méthode de le faire (avoir un coup d'oeil à la La tortue et le Lièvre de l'algorithme).

    EDIT:

    Algorithme de questions sera presque toujours à partir de la liste suivante:

    • De manipulation de chaîne tels que:
      • Inverse Chaîne
      • Compter combien de fois chaque lettre apparaît dans une Chaîne donnée (l'utilisation d'une Carte)
    • LinkedList des questions telles que:
      • Comment faire pour supprimer un nœud, une attention particulière à bord des cas comme la suppression de la tête
      • Comment inverser une linkedList (faire la Queue à la Tête)
    • Arbre binaire à des questions telles que:
      • Dans l'ordre de la traversée
      • Si il y a un Arbre d'équilibrage de la question, vous n'aurez pas besoin de la mettre en œuvre, il suffit de comprendre que déséquilibré Arbre Binaire est tout simplement une Liste Liée.
      • Comprendre que la recherche de l'équilibre Arbre Binaire est O(log n) par rapport à une Liste chaînée ou déséquilibré Arbre Binaire qui est O(n).
    • Vous sera probablement demandé de décrire la complexité de la solution que vous venez de donner (big-O notation)

    Voir cette et cette pour les questions liées à Java lui-même

    Juste un plus ici, ce Nœud est généralement mis en œuvre en tant que private static class Pas privé intérieur de la classe. --> docs.oracle.com/javase/tutorial/java/javaOO/nested.html et maintenant, je suis un nitpicker 🙂 Citant Joshua Bloch Effectif de Java - Point 22*: Favoriser le membre statique des classes non statiques.

    OriginalL'auteur Samuel O'Malley