remove elements in linked list

Question

If I have linkedlist which contains some elements. For example, myLinked={3,6 100,95 ,16, 19 ,7 13 ,44}. I want to remove any elements between 8 to 20. The linked list will remove 7, 16 ,19,13. could someone tell me how should I do this. Also, can I do this without using sorting .

Here is my LinkedList Class:

public class MyList
{
    static class Node
    {
        public Node(double item, Node next)
        {
            this.item = item;
            this.next = next;
        }

        public double item;
        public Node   next;
    }

    Node first;

    public MyList()
    {
        first = null;
    }

    public boolean isEmpty()
    {
        return first == null;
    }

    public void add (double item)
    {
        Node newfirst = new Node (item, first); 
        this.first = newfirst;
    }
}

Answer 1

First off, your add method places Nodes into the linkedlist in reverse order.

That is, if you were to make the following calls to your implementation:

MyList list = new MyList();

list.add(1.0);
list.add(2.0);
list.add(3.0);

Then your linked list would look like:

head-->3.0-->2.0-->1.0-->null

To fix this issue, your add method should look like:

public void add (double item)
{
    // create the new Node and have next point to null
    Node newNode = new Node (item, null);

    // the list was empty
    if (first == null)
    {
        this.first = newNode;
    }
    // loop until the end and attach the new Node
    else
    {
        Node next = first;
        Node prev = null;

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

Now, if run the following code:

MyList list = new MyList();

list.add(1.0);
list.add(2.0);
list.add(3.0);

Your linked list will look like:

head-->1.0-->2.0-->3.0-->null

Now that we have a proper add method, we can implement the method that will remove all Nodes that are within the removal bounds (e.g. lower and upper)

Here is the removal implementation:

public void removeBetween (double lower, double upper)
{
    Node current = first; // pointer to current Node
    Node prev = first; // pointer to previous Node
    Node removal = null; // pointer to Node we will remove

    // go through the entire linkedList
    while (current != null)
    {
        double data = current.item;

        // lower <= data <= upper
        // See note below on why use Double.compare()
        if (Double.compare(data, lower) >= 0 && Double.compare(data, upper) <= 0)
        {
            System.out.println("removing: " + data);
            removal = current;
        }

        // we found a Node to remove
        if (removal != null)
        {
            // special case it was the first
            if (removal == first)
            {
                // change first to next
                first = removal.next;
            }
            else
            {
                // move removals previous next to removal next
                prev.next = removal.next;
            }
        }

        // advance the pointers
        // only change previous if we didn't have a removal
        if (removal == null)
        {
            prev = current;
        }

        // move current along
        current = current.next;

        // detached the removal
        if (removal != null)
            removal.next = null;

        // reset the removal pointer
        removal = null;
    }
}

Note:

• Why use Double.compare() and not == when comparing doubles: Please see this post: Why can't we use '==' to compare two float or double numbers

Answer 2

    int min = 8; //the min value you want to remove
    int max = 20; //the max value you want to remove

    for (int i = 0; i < myLinkedList.size(); i++) {
        int current = myLinkedList.get(i); //get the current element of your list
        if(current > min && current < max){ //check if current is between those numbers
            myLinkedList.remove(i);
            i--;
        }
    }

Answer 3

Try this:

for(Iterator<Integer> iter = list.iterator(); iter.hasNext();) {
    Integer v = ((Integer)iter.next());
    if (v < 20 && v > 8) {
        iter.remove();
    }
}