遍历 LinkedList 的最佳方法 - Java

Optimal ways to Traverse through a LinkedList - Java

提问by RonJermiah

The Situation

情况

I have a interview with TripAdvisor tomorrow and I decided for practice to create my own custom LinkedList. I'm trying to figure out the best way to traverse through it.

我明天接受 TripAdvisor 的采访，我决定练习创建自己的自定义 LinkedList。我试图找出穿越它的最佳方式。

Primary Question: I have managed to traverse through my Linked List however I believe there is a better way to do it. How would you traverse through it ?

主要问题：我已经设法遍历了我的链接列表，但是我相信有更好的方法来做到这一点。你将如何穿越它？

Bonus Question: How do my overall classes look ? Is there anything I should/should not add ? It seems to work fine but is it optimal ?

额外问题：我的整体课程看起来如何？有什么我应该/不应该添加的吗？它似乎工作正常，但它是最佳的吗？

Bonus Question #2: Lastly I was wondering if anyonehad any insight to typical interview questions/concepts that I must know ?

额外问题#2：最后，我想知道是否有人对我必须知道的典型面试问题/概念有任何见解？

Greatly appreciated.

不胜感激。

Here are my 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());

}

//Again is there a better way to do this ? //Thanks }

//还有没有更好的方法来做到这一点？//谢谢 }

采纳答案by Samuel O'Malley

I would change your traverse function to be more like this:

我会将您的遍历函数更改为更像这样：

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

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

Also it is common to represent the Node class as a private inner class of LinkedList because it is not typically needed anywhere else.

此外，通常将 Node 类表示为 LinkedList 的私有内部类，因为它通常在其他任何地方都不需要。

As far as the interview itself goes, traversal questions are more typical for binary-trees (eg. print out the elements in sorted order). LinkedList questions are more focussed on the remove/insert operations which both require careful attention to the edge cases (what happens when you remove the head for example). A more advanced LinkedList question would ask how to detect a cycle, I would make sure that I knew at least one method of doing this (have a look at the Tortoise and the Hare algorithm).

就面试本身而言，遍历问题对于二叉树更为典型（例如，按排序顺序打印出元素）。LinkedList 问题更侧重于删除/插入操作，这两者都需要仔细注意边缘情况（例如，当您删除头部时会发生什么）。一个更高级的 LinkedList 问题会询问如何检测循环，我会确保我知道至少一种方法（看看乌龟和野兔算法）。

EDIT:

编辑：

Algorithm questions will nearly always be from the following list:

算法问题几乎总是来自以下列表：

• String manipulation such as:
  • Reverse String
  • Count how many times each letter appears in a given String (use a Map for this)
• LinkedList questions such as:
  • How to remove a node, pay close attention to edge cases such as removing the head
  • How to reverse a linkedList (make the Tail the Head)
• Binary Tree questions such as:
  • In-order traversal
  • If there is a BTree balancing question you won't need to implement it, just understand that a completely unbalanced Binary Tree is simply a Linked List.
  • Understand that searching a balanced Binary Tree is O(log n) compared to a Linked List or a completely unbalanced Binary Tree which is O(n).
• You will probably be asked to describe the complexity of the solution you just gave (big-O notation)

• 字符串操作，例如：
  • 反转字符串
  • 计算每个字母在给定字符串中出现的次数（为此使用 Map）
• LinkedList 问题，例如：
  • 如何去除一个节点，注意去除头部等边缘情况
  • 如何反转链表（使尾部成为头部）
• 二叉树问题，例如：
  • 中序遍历
  • 如果有 BTree 平衡问题，您不需要实现它，只需理解完全不平衡的二叉树只是一个链表。
  • 了解与链表或完全不平衡的二叉树相比，搜索平衡的二叉树是 O(log n) 的 O(n)。
• 您可能会被要求描述您刚刚给出的解决方案的复杂性（大 O 符号）

See thisand thisfor questions related to Java itself

有关Java 本身的问题，请参阅此和此