Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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])));
    }
}
share|improve this question
1  
You should probably just use Java's LinkedList‌​. If you were working in some company, it would not be well seen if you spend some time reinventing the wheel. –  toto2 Jul 3 at 23:02
    
@toto2 when you appear for interview, they actually want to test how you would write these basic datastrutures from scratch. Thus reusing LinkedList is good in real world, but not in interviews –  JavaDeveloper Jul 4 at 17:44
2  
And it's sad. Same with sorting algorithms. If a developer would ever reimplement those things, he/she should be fired for wasting time and $$$. But that's what they ask in interviews instead of asking practical questions. –  toto2 Jul 4 at 18:01

3 Answers 3

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()));
}
share|improve this answer
1  
Using Streams here is, although not the most efficient alternative, absolutely not "completely off-topic" and a very good recommendation to learn overall! –  Simon André Forsberg Jul 3 at 23:48
    
@Simon I don't think a Stream is any less efficient than a LinkedList for this problem. It will only be inefficient if you have to convert to Stream and the back to a Collection. –  toto2 Jul 3 at 23:58
    
I can't say I have benchmarked it, so I'm not sure, but given the overhead classes and methods a Stream adds, it's usually not faster. At least that's the wide-spread belief –  Simon André Forsberg Jul 4 at 11:47
1  
Actually, if you google some of his questions, they are coming straight (word for word) from geeksforgeeks.org. Same problems, with many different solutions in the comments on the postings. He's using this site as a debugging/sounding board. –  JohnP Jul 4 at 13:21
    
@JohnP please instruct me if it violates any stack-overflow conventions. I am under impressions that I am doing exactly what this site is meant for - code review aka sounding/debugging –  JavaDeveloper Jul 6 at 22:42

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.

share|improve this answer
1  
It's not removeRange, it's removeRanges. Your second bug is not a bug but a feature, if you read his input&output example more carefully. –  mkalkov Jul 4 at 6:25
    
"Traverse the linked list such that you retain M nodes then delete next N nodes, continue the same till end of the linked list." Indeed correct, @mkalkov. –  Simon André Forsberg Jul 4 at 8:47
    
@mkalkov - I used the wrong word. I used remove instead of retain. Let me fix that. –  rolfl Jul 4 at 11:18
    
@mkalkov - been chatting in the 2nd monitor, you should visit some time. –  rolfl Jul 4 at 11:41

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.

share|improve this answer
    
I have upvoted your feedback, meaning its very impressive. The remainder follows my differences with you. I suggest create is a better name than createNode, since, 1. its private function, thus its implicit what it creates, leads to smaller names –  JavaDeveloper Jul 4 at 17:22
    
The last field reduces the construction time of the list, since from O(n^2) to O(n) –  JavaDeveloper Jul 4 at 17:26
    
Also i need size field in toArray or even in toList for initial capacity –  JavaDeveloper Jul 4 at 18:40
    
Can you explain why list construction time would jump to O(n^2) if last field is removed? As for the size field, it isn't necessary with toList because you don't have and actually should not specify initial capacity of ArrayList. I agree that renaming create is more of a preference than a hard requirement. –  mkalkov Jul 4 at 18:54
    
If a list has 10 nodes, and i want to insert 11th, how do I insert 11th node without keeping track of 10th node ? I would need to traverse the whole list. Whats the good use of it? Thus for (each node) { traverse from first to last } –  JavaDeveloper Jul 4 at 19:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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