Façons optimales de parcourir une LinkedList-Java
La situation
J'ai une interview avec TripAdvisor demain et j'ai décidé pour la pratique de créer ma propre liste de liens personnalisée. J'essaie de trouver le meilleur moyen de le traverser.
Question principale: J'ai réussi à parcourir ma liste chaînée, mais je crois il y a une meilleure façon de le faire. Comment feriez-vous pour le traverser ?
Question bonus: À quoi ressemblent mes classes globales ? Y a-t-il quelque chose que je devrais/ne devrais pas ajouter ? Il semble bien fonctionner mais est-ce optimal ?
Question bonus # 2: Enfin, je me demandais si quelqu'un avait un aperçu des questions/concepts d'entrevue typiques que je dois connaître ?
Grandement apprécié.
Voici mes cours
// *********************************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 y a-t-il une meilleure façon de le faire ? //Grâce }
1 answers
Je changerais votre fonction de traversée pour être plus comme ceci:
public void traverse(){
Node<T> pointer = head;
while (pointer != null){
System.out.println(pointer.getData());
pointer = pointer.getLink();
}
}
Il est également courant de représenter la classe Node comme une classe interne privée de LinkedList car elle n'est généralement nécessaire nulle part ailleurs.
En ce qui concerne l'interview elle-même, les questions de traversée sont plus typiques des arbres binaires (par exemple. imprimer les éléments dans l'ordre de tri). Les questions LinkedList sont plus axées sur les opérations de suppression/insertion qui nécessitent toutes deux une attention particulière aux cas périphériques (que se passe-t-il lorsque vous retirez la tête par exemple). Une question LinkedList plus avancée demanderait comment détecter un cycle, je m'assurerais que je connaissais au moins une méthode pour le faire (jetez un oeil à la tortue et à l'algorithme Hare).
MODIFIER:
Les questions d'algorithme seront presque toujours de la liste suivante:
- Manipulation de chaîne telle que:
- Chaîne inversée
- Comptez combien de fois chaque lettre apparaît dans un Chaîne (utilisez une Carte pour cela)
- LinkedList questions telles que:
- Comment supprimer un nœud, portez une attention particulière aux cas de bord tels que le retrait de la tête
- Comment inverser une liste de liens (faire de la queue la tête)
- Questions d'arbre binaire telles que:
- Traversée en ordre
- S'il y a une question d'équilibrage BTree, vous n'aurez pas besoin de l'implémenter, comprenez simplement qu'un arbre binaire complètement déséquilibré est simplement un lien Liste.
- Comprenez que la recherche d'un Arbre binaire équilibré est O(log n) par rapport à une Liste Chaînée ou à un Arbre Binaire complètement déséquilibré qui est O(n).
- On vous demandera probablement de décrire la complexité de la solution que vous venez de donner (notation big-O)