title: Best Solution For the Train Composition
body: <p>Recently I answered My Online Interview test Wherein I was asked Following question </p>
  
  <blockquote>
    <p>A TrainComposition is built by attaching and detaching wagons from the left and the right sides.</p>
    
    <p>For example, if we start by attaching wagon 7 from the left followed by attaching wagon 13, again from the left, we get a composition of two wagons (13 and 7 from left to right). Now the first wagon that can be detached from the right is 7 and the first that can be detached from the left is 13. Implement a TrainComposition that models this problem.</p>
  </blockquote>
  
  <p>I used doubly linked list to solve the issue</p>
  
  <pre><code>class Node
  
  {
      protected int data;
      protected Node next, prev;
      /* Constructor */
      public Node()
      {
          next = null;
          prev = null;
          data = 0;
      }
  
      /* Constructor */
  
      public Node(int d, Node n, Node p)
      {
          data = d;
          next = n;
          prev = p;
      }
  
      /* Function to set link to next node */
      public void setLinkNext(Node n) {
          next = n;
      }
      /* Function to set link to previous node */
      public void setLinkPrev(Node p) {
          prev = p;
      }
  
      /* Funtion to get link to next node */
  
      public Node getLinkNext() {
          return next;
      }
  
      /* Function to get link to previous node */
  
      public Node getLinkPrev() {
          return prev;
      }
  
      /* Function to set data to node */
      public void setData(int d) {
          data = d;
      }
  
      /* Function to get data from node */
  
      public int getData() {
          return data;
      }
  }
  
  public class SortedSearch {
      protected Node start;
      protected Node end;
      public int size;
      /* Constructor */
      public SortedSearch()
      {
          start = null;
          end = null;
          size = 0;
      }
      public boolean isEmpty()
      {
          return start == null;
      }
  
      public int getSize()
      {
          return size;
      }
  
      public void attachWagonFromLeft(int wagonId) {
          Node nptr = new Node(wagonId, null, null);
          if (start == null)
          {
              start = nptr;
              end = start;
          }
          else
          {
              start.setLinkPrev(nptr);
              nptr.setLinkNext(start);
              start = nptr;
          }
          size++;
      }
      public void attachWagonFromRight(int wagonId) {
          Node nptr = new Node(wagonId, null, null);
          if (start == null)
          {
              start = nptr;
              end = start;
          }
          else
          {
              nptr.setLinkPrev(end);
              end.setLinkNext(nptr);
              end = nptr;
          }
          size++;
      }
      public int detachWagonFromLeft() {
          int value=0;
          if (size == 1)
          {
              value = start.getData();
              start = null;
              end = null;
              size = 0;
              return value;
  
          }
          value = start.getData();
          start = start.getLinkNext();
          start.setLinkPrev(null);
          size--;
          return value;
      }
  
      public int detachWagonFromRight() {
          int value=0;
              value = end.getData();
              end = end.getLinkPrev();
              end.setLinkNext(null);
              size-- ;
              return value;
      }
  
      public static void main(String[] args) {
          SortedSearch tree = new SortedSearch();
          tree.attachWagonFromLeft(7);
          tree.attachWagonFromLeft(13);
          tree.attachWagonFromLeft(12);
          tree.attachWagonFromLeft(10);
          tree.attachWagonFromLeft(6);
          tree.attachWagonFromLeft(4);
          tree.attachWagonFromLeft(3);
          tree.attachWagonFromLeft(2);
          System.out.println(tree.detachWagonFromRight()); // 7
          System.out.println(tree.detachWagonFromRight()); // 13
          System.out.println(tree.detachWagonFromRight()); // 7
          System.out.println(tree.detachWagonFromRight()); // 13
          System.out.println(tree.detachWagonFromRight()); // 7
          System.out.println(tree.detachWagonFromRight()); // 13
  
      }
  }
  </code></pre>
  
  <p>And tested it accordingly. But when submitted it said failed internal test cases, and the answer was marked wrong. 
  Can you please tell which is the best solution for this problem.</p>