0
\$\begingroup\$

Description:

Given a linked list move the last node to the front.

For example:

10 20 30 40 -> 40 10 20 30

Code:

class Main {
  static class Node {
    private int data;
    private Node next;

    Node(int data, Node next) {
      this.data = data;
      this.next = next;
    }

    Node append(int data) {
      Node newNode = new Node(data, null);
      Node current = this;

      while (current.next != null) {
        current = current.next;
      }
      current.next = newNode;
      return this;
    }

    public String toString() {
      Node current = this;
      StringBuilder sb = new StringBuilder();

      while (current != null) {
        // do something here
        sb.append(current.data);
        sb.append(" ");
        current = current.next;
      }
      return sb.toString();
    }
  }

  public static Node moveTailToHead(Node head) {
    if (head == null || head.next == null) {
      throw new IllegalStateException(
          "List should have atleast two elements");
    }

    Node current = head;
    Node prev = null;

    while (current.next != null) {
      prev = current;
      current = current.next;
    }
    prev.next = null;
    current.next = head;
    head = current;

    return head;
  }

  public static void main(String[] args) {
    Node head = new Node(10, null);
    head.append(20)
        .append(30)
        .append(40);
    System.out.println(head); // 10 20 30 40

    Node newHead = moveTailToHead(head);
    System.out.println(newHead); // 40 10 20 30

    try {
      System.out.println(
        "Should not happen: " + moveTailToHead(null));
    } catch (IllegalStateException e) {
      System.out.println(
        "Got expected exception for null node");
    }

    try {
      System.out.println(
        "Should not happen: " + moveTailToHead(new Node(10, null)));
    } catch (IllegalStateException e) {
      System.out.println(
        "Got expected exception for single node");
    }
  }
}

Question:

I am writing code in Java after a long time and would like to know if I am making any mistake or abusing any feature of Java.

\$\endgroup\$
2
\$\begingroup\$

You are only able to access Node's fields data and next from the method moveTailToHead(Node) because this method is declared in the same top level class as Node. I don't know why you chose this design for your code sample, but the fact that you made the method moveTailToHead a static method outside the class Node rather than an instance method of Node makes me think that moveTailToHead is also supposed to work "from the outside" without having access to Node's internal implementation details, so I'm wondering whether your code design in this regard is intentional. If it is, then I won't argue against it, but if it isn't and if moveTailToHead should also work if it were declared in a different top level class, then you need to implement a way for Node to provide some way of accessing the contents of the list it represents. A way to start could be for Node to implement the interface Iterable<Integer>, which would require Node to have an iterator() method. This method could, for instance, look like this:

@Override
public Iterator<Integer> iterator() {
    return new Iterator<Integer>() {
        private Node nextNode = Node.this; //the next node to be returned by next()
        private Node currentNode = null;   //the last node returned by next()
        private Node previousNode = null;  //the node that precedes currentNode

        @Override
        public boolean hasNext() {
            return nextNode != null;
        }

        @Override
        public Integer next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            } else {
                if (currentNode != null) {
                    previousNode = currentNode;
                }
                currentNode = nextNode;
                int nextData = nextNode.data;
                nextNode = nextNode.next;
                return nextData;
            }
        }

        @Override
        public void remove() {
            if (currentNode == null) {
                throw new IllegalStateException();
            } else if (previousNode != null) {
                currentNode.next = null;
                previousNode.next = nextNode;
                currentNode = null;
            } else {
                assert currentNode == Node.this;
                throw new UnsupportedOperationException();
            }
        }
    };
}

That way, you can also get rid of the code duplication whenever you iterate through the list using constructs like while (current.next != null) or similar.

If you look at the method remove(), it becomes apparent that the fact that you are using a Node object to refer to the actual list itself, which Xtreme Biker already criticized in his answer, is problematic. Since the head node also defines the list, it is not possible to remove the head node from the list, which is why I made the method throw an UnsupportedOperationException for the sake of completeness in this demonstration code.

But apart from this issue, with Iterable implemented, adding other methods to add or remove elements should not be very difficult, and then you can move the tail node to the head without having direct access to the private fields Node.data and Node.next.

\$\endgroup\$
  • \$\begingroup\$ Actually I wend overboard and implemented other methods in the Node class, since its an interview question (time constrained) the Node class is supposed to contain just data and next fields and the logic should go in the static method. \$\endgroup\$ – CodeYogi Mar 30 '18 at 6:14
0
\$\begingroup\$

The problem here is that each one of the Node elements knows only about its next element. Basically, you keep only a reference to your first Node element in order to refer to the whole linked list.

I would rather go with a wrapper which makes an abstraction over the Node class so as you can control useful parameters such as the size of the list, and offers the developer a greater API, something like this:

public class NodeLinkedList{

    private class Node{
        private int data;
        private Node next;

        Node(int data){
            this.data = data;
        }

        append(Node node){
            this.next = node;
        }

        convertInLast(){
            this.next = null;
        }
    }

    //Reference to the first element
    private Node list;

    //Auxiliar for size
    private int size;

    public NodeLinkedList(int first){
        list = new Node(first);
        size = 1;
    }

    public void append(int element){
        list.append(element);
        size ++;
    }

    public void lastToFirst(){
        if (size > 1){
            Node first = list;
            int i = 1;
            while (i < size){
                //Here, you do your switching stuff
            }
        }

    }

}
\$\endgroup\$
  • \$\begingroup\$ What do you win by storing the size? You cannot access the list by index. \$\endgroup\$ – bbnkttp Mar 30 '18 at 7:53
  • \$\begingroup\$ @bbnkttp it might be useful to implement the logic of switching the Last element to first place (you need to alter the element before the Last too) \$\endgroup\$ – Xtreme Biker reinstate Monica Mar 30 '18 at 17:44
0
\$\begingroup\$

I have some remarks.

You can get some better performance if you implement an void appendAll(Integer[]) that only walks to the end of the list once. Right now creating a linked list of size n with a chain of appends takes (n-1) + (n-2) + .. = n*(n-1)/2 = O(nˆ2).

I think you are throwing too much exceptions moveTailToHead. You should only throw exception if something exceptional happened or an assumption is broken.

  • The assumption head != null is fair and one should throw a NullPointerException in that case. This starts smelling like moveTailToHead should be an instance method of Node, then you did not need to worry about this edge case.
  • The head.next != null case is not exceptional and there is no need to have this exception. Or was this a requirement? In this case head=tail, so we do not need to switch. Just catch this base-case early and just return the argument. So if (head.next == null) { return head;}

You use new Node(data, null) everywhere. The second argument is always assigned null, so it should be removed and only a constructor with one parameter is needed.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.