CODEWITHSUNDEEP
javalinked-listiterator
David Rouleau
David Rouleau

Reputation: 61

How to remove from an immutable linked list?

I need to make a linked list using a remove() method, which takes a parameter, e, a generic stand in, and removes the linked node which contains e, then the method returns a new Linked list containing all elements except e.

I have no idea how to implement this and the farthest I have gotten is this:

  public Set<E> remove(E e) {
    LinkedNode<E> current = null;
    if(!this.contains(e)) {//if this list doesnt contain e, return this
        return this;
    } else {//otherwise go through this set and if it contains e return new set w/out it
        for(E j:this) {
            if(j.equals(e)) {
                current = new LinkedNode<E>(j,current);
            }
        }
    }
    Set<E> newSet = new LinkedSet<E>(current);
    for(E i:newSet) {
        System.out.print(i +", ");
    }
    return newSet;
  }

this code uses an iterator so the enhanced for loop works, but it returns sets with the wrong info. I think this might be because the tail end of the new set I want still has the link to the end of the old list, but this is just a guess.

The last output I got was:d, b, a, c, e, b, d, a, c, e, b, d, a, and the input was:c,a,d,b,e

I was trying to remove c

Upvotes: 2

Views: 4385

Answers (2)

ilinykhma
ilinykhma

Reputation: 990

Assume that there are no dublicates in your list (because actually return type is a set) or at least we need to remove only first occurency.

We could copy elements of current list to new list before 'e' position and use elements after 'e' as tail for both lists. In this way we would copy just part of list, there will be shared elements now. For immutable collection it's ok, but you need be careful with other LinkedList methods implementations.

public Set<E> remove(E e) {

    if (!this.contains(e)) {
        return this;
    }

    final LinkedNode<E> head = new LinkedNode<E>(this.head);

    // Copy elements of current list to new list before 'e' position
    LinkedNode<E> current = this.head, newListCurrent = head;
    while (!e.equals(current.next)) {
        newListCurrent.next = new LinkedNode<E>(current.next);
        newListCurrent = newListCurrent.next;
        current = current.next;
    }

    // Now current.next is element to remove. Link tail of new list to tail of current list
    newListCurrent.next = current.next.next;
    return new LinkedList<E>(head);
}

It's like pseudocode, but i need full code of your LinkedList and LinkedNode to use them correctly. I've not enought reputitation to ask about it in comment ))

Upvotes: 0

Karol Dowbecki
Karol Dowbecki

Reputation: 44932

Assuming you are returning remaining elements from remove() method you can add every element which is not e:

public Set<E> remove(E e) {
  Set<E> newSet = new LinkedSet<E>();
  for(E j : this) {
    if (!j.equals(e)) {
       newSet.add(j);
    }
  }
  return newSet;
}

Upvotes: 2

Related Questions