Repeatedly skip M nodes then delete N nodes then skip M nodes and so on

Question

Given a linked list and two integers M and N. Traverse the linked list such that you retain M nodes then delete next N nodes, continue the same until end of the linked list.

• Input:

  M = 2, N = 2
  Linked List: 1->2->3->4->5->6->7->8

• Output:

  Linked List: 1->2->5->6

I'm looking for code review, optimizations and best practices.

public class DeleteNAfterM<T> {

    private Node<T> first;
    private Node<T> last;
    private int size;

    public DeleteNAfterM(List<T> list) {
        for (T item : list) {
            create(item);
        }
    }

    private void create(T item) {
        Node<T> node = new Node<T>(item);
        Node<T> l = last;

        if (first == null) { 
            first = node;
        } else {
            l.next = node;
        }
        last = node;
        size++;
    }

    private static class Node<T> {
        private T item;
        private Node<T> next;

        Node(T item) {
            this.item = item;
        }
    }


    public void deleteNAfterM(int m, int n) {
        if (first == null) {
            throw new IllegalArgumentException(" the linkedlist should not empty.");
        }
        if (m < 0)  {
            throw new IllegalArgumentException("m: " + m + " should not be less than zero.");
        }
        if (n < 0) {
            throw new IllegalArgumentException("n: " + n + " should not be less than zero.");
        }

        if (m == 0 && n > 0) {
            size = 0;
            first = last = null;
            return;
        }

        Node<T> node = first; 

        while (node != null) { 
            for (int i = 1; i < m && node != null; i++) {
                node = node.next; // can be thought of as int x = a[i];
            }

            if (node == null || node.next == null) return; 

            Node<T> temp = node;

            for (int i = 0; i < n && temp != null; i++) {
                temp = temp.next; // can be thought of as int x = a[i];
                size--;
            }

            if (temp == null) return;

            node.next = temp.next;
            node = node.next;
        }
    }

    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<T> x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }
}

public class DeleteNAfterMTest {

    @Test
    public void test1() {
        // last node is not deleted
        DeleteNAfterM<Integer> deleteMAfterN1 = new DeleteNAfterM<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
        deleteMAfterN1.deleteNAfterM(2, 2);
        Object[] itemList1 =  deleteMAfterN1.toArray();
        Integer[] expected1 = {1, 2, 5, 6};
        assertTrue(Arrays.equals(expected1, Arrays.asList(itemList1).toArray(new Integer[itemList1.length])));
    }

    @Test
    public void test2() {
        // last node is deleted
        DeleteNAfterM<Integer> deleteMAfterN2 = new DeleteNAfterM<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
        deleteMAfterN2.deleteNAfterM(2, 1);
        Object[] itemList2 =  deleteMAfterN2.toArray();
        Integer[] expected2 = {1, 2, 4, 5};
        assertTrue(Arrays.equals(expected2, Arrays.asList(itemList2).toArray(new Integer[itemList2.length])));
    }

    @Test
    public void test3() {
        // edge case - nothing  should be deleted
        DeleteNAfterM<Integer> deleteMAfterN3 = new DeleteNAfterM<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
        deleteMAfterN3.deleteNAfterM(4, 0);
        Object[] itemList3 =  deleteMAfterN3.toArray();
        Integer[] expected3 = {1, 2, 3, 4, 5, 6};
        assertTrue(Arrays.equals(expected3, Arrays.asList(itemList3).toArray(new Integer[itemList3.length])));
    }

    @Test
    public void test4() {
        // edge case - everything should be deleted.
        DeleteNAfterM<Integer> deleteMAfterN4 = new DeleteNAfterM<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
        deleteMAfterN4.deleteNAfterM(0, 1);
        Object[] itemList4 =  deleteMAfterN4.toArray();
        Integer[] expected4 = {};
        assertTrue(Arrays.equals(expected4, Arrays.asList(itemList4).toArray(new Integer[itemList4.length])));
    }
}

Answer 1

You should probably just use Java's LinkedList‌​. If you were working for some company, it would not be well seen if you spent some time reinventing the wheel.

Now, for something that is completely off topic:

You seem to have a whole bank of interview questions which you are answering and submitting on codereview. Those questions seem kind of old. You could play around with newer technology. It's fun and, if you want to get hired, it shows you like programming (even if you will not use that technology in your work). For example, I am answering your question with Java 8 below. Stream is not a linked list, but it is related: It's basically a lazily evaluated linked list.

private static <T> Stream<T> filterMAfterN(Stream<T> stream, int mValid, int nInvalid) {
    final AtomicInteger index = new AtomicInteger(0);
    return stream.filter(unusedValue -> {
        int rescaledIndex = index.getAndIncrement() % (mValid + nInvalid);
        return rescaledIndex < mValid;
    });
}

public static void main(String[] args) {
    Stream<Integer> stream = Stream.of(1, 2, 3, 4, 5, 6, 7, 8, 9);
    System.out.println(filterMAfterN(stream, 1, 2).collect(Collectors.toList()));
}

Answer 2

Bugs galore....

Bug 1

The user should always be able to call:

list.deleteNAfterM(0, list.size());

This should always be safe.... but, your code throws IllegalArgumentException if the list is empty.

Also, why call it deleteNAfterM, it should match other standard conventions, like remove for removing items, and I would suggest the name removeRanges, with an offset and a length, like everything else that does these things.

Bug 2

The original title of the question was: "Delete N Nodes after M in a linked list"

Apparently I got fixated on the after part of the title, when the actual description makes more sense and means 'from', not 'after'. The method name is still 'After', so, that, in a sense is all that's left of my Bug2:

• Calling the method deleteMAfterN() is a bad idea, it should be skipAndRemove. The variable names should be changed from M and N to be skip and remove

---

---

If you have 5 items in the list, and the method gets called as:

deleteNAfterM(0, 1)

I would expect it to retain 1 item.

Your code instead removes everything.....

    if (m == 0 && n > 0) {
        size = 0;
        first = last = null;
        return;
    }

This code is poorly thought out. You have obviously not tested any edge cases, and you don't seem to have any real idea of what the spec means....

... having a method deleteAfter... is a bad idea, it should be deleteFrom... at minimum because there is no way to specify deleting the first item in the list using deleteAfter....

Not much point in looking much further at the code. It's failed to pass the initial state checks.

Answer 3

1. Rely on battle-tested libraries and make sure you test your own code

Use standard LinkedList implementation unless this is just an exercise, in which case make sure you have an adequate test suite. Your test suite leaves a lot to be desired, and that's why your code works incorrect in the following two cases. In fact, this kind of exercise is a perfect one to try Test-Driven Development.

input: 1 2
remove 2 after 1
expected output: 1
actual output: 1 2

input: 1 2 3 4 5
remove 2 after 1
expected output: 1 4
actual output: 1 4 5

2. Naming

When I stumble upon a class called DeleteNAfterM or with another verb phrase, my first instinct is "This class probaly implements Command pattern or represents a first-class function". You class does neither and is instead a private linked list implementation. Why don't you call it "MyLinkedList" or something along these lines then?

I suggest that you rename create(...) method into createNode(...), and deleteNAfterM(m, n) into skipMremoveNInLoop(m, n) or at least removeNAfterM(n, m) (note argument order). Imagine that you have a list of files. If you remove a file from this list, the file still exists somewhere. However, if you delete a file from this list, the file is probably removed from the list as well as unlinked from file system.

Finally, there is no need to number test methods and write comments in their body when you can name test method accordingly. For example, test2 could have been named testLastNodeIsDeleted.

3. Design

The use of private static class is totally OK. I don't see why you need a pointer to the last field unless you access it often and want to avoid iterating through the list. I also don't see why you need size field. Besides that I would have implemented Iterable interface so that my list can be used with the enhanced for-loop.

Since you already use List<T>, you could as well replace toArray() method with toList() which would greatly simplify your tests. For example, this is how you would be able to write test1, assuming myList is a private field:

myList = new MyLinkedList<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
myList.skipMRemoveNInLoop(2, 2);
assertEquals(Arrays.asList(1, 2, 5, 6), myList.toList());

Even if you want to stick to toArray(), you should replace assertTrue(Arrays.equals(...)) with assertArrayEquals(...).

I also think that a first == null check looks strange in skipMRemoveNInLoop method. Why cannot your list be empty? This sounds like a quite common case.

4. Implementation

• You don't need Node<T> l variable inside createNode method.
• You have quite a few empty lines in the main loop inside skipMRemoveNInLoop method. I think it would be better to remove most of them and leave two code blocks: first one to skip nodes, and the second one to remove nodes.

Otherwise, I think your code looks fine and quite idiomatic. So, if I haven't mentioned something that's probably because that aspect looked OK to me. When you fix the aforementioned issues, paste a follow-up question so any remaining glitches can be uncovered.