Optimal ways to Traverse through a LinkedList - Java

Question

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.

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 ?

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 }

Answer 1

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.

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).

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)

See this and this for questions related to Java itself