Nov 8, 2018

Linked List should be remembered for Java interview




class Node {
 int val;
 Node next;

 Node(int x) {
  val = x;
  next = null;
 }
}
Two popular applications of linked list are stack and queue.
Stack


class Stack{
 Node top; 
 
 public Node peek(){
  if(top != null){
   return top;
  }
 
  return null;
 }
 
 public Node pop(){
  if(top == null){
   return null;
  }else{
   Node temp = new Node(top.val);
   top = top.next;
   return temp; 
  }
 }
 
 public void push(Node n){
  if(n != null){
   n.next = top;
   top = n;
  }
 }
}

Queue

class Queue{
 Node first, last;
 
 public void enqueue(Node n){
  if(first == null){
   first = n;
   last = first;
  }else{
   last.next = n;
   last = n;
  }
 }
 
 public Node dequeue(){
  if(first == null){
   return null;
  }else{
   Node temp = new Node(first.val);
   first = first.next;
   return temp;
  } 
 }
}

Java standard library already contains a class called "Stack", and LinkedList can be used as a Queue. (LinkedList<E> is a doubly-linked list implementation of the List and Deque interfaces) If you directly need a stack or queue to solve problems in your interview, you can directly use them.

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to "Stack" class. For example:

   Deque<Integer> stack = new ArrayDeque<Integer>();

Example of Binary Tree Preorder Traversal in Java