Jump to content

SLLNode Remove method?

- - - - -

This topic has been archived. This means that you cannot reply to this topic.
6 replies to this topic

#1
ZipOnTrousers

ZipOnTrousers

    Learning Programmer

  • Validating
  • PipPipPip
  • 94 posts
K I've been asked to implement a remove method in a Singly Linked List class which implements the class List. The classes are below:

List

import java.util.Iterator;



public interface List {
    // Each List object is an indexed list (sequence) whose elements are
    // objects.

    //////////// Accessors ////////////
    public boolean isEmpty ();
    // Return true if and only if this list is empty.

    public int size ();
    // Return this list's length.

    public Object get (int i);
    // Return the element with index i in this list. Throw an
    // IndexOutOfBoundsException if i is out of range.

    public boolean equals (List that);
    // Return true if and only if this list and that have the same length, and
    // each element of this list equals the corresponding element of that.

    //////////// Transformers ////////////

    public void clear ();
    // Make this list empty.

    public void set (int i, Object elem);
    // Replace by elem the element at index i in this list. Throw an
    // IndexOutOfBoundsException if i is out of range.

    public void add (int i, Object elem);
    // Add elem as the element with index i in this list. Throw an
    // IndexOutOfBoundsException if i is out of range.

    public void add (Object elem);
    // Add elem after the last element of this list.

    public void addAll (List that);
    // Add all the elements of that after the last element of this list.

    public Object remove (int i);
    // Remove and return the element with index i in this list. Throw an
    // IndexOutOfBoundsException if i is out of range.

    //////////// Iterator ////////////

    public Iterator iterator ();
    // Return an iterator that will visit all elements of this list,
    // in left-to-right order.
}

Linked List

import java.util.Iterator;
import java.util.NoSuchElementException;
/**
 *
 * @author
 */


public class LinkedList implements List {

    // Each LinkedList value is an unbounded list whose elements are
    // objects.

    // This list is represented as follows: first and last are links to the
    // first and last nodes of a SLL containing the elements; length is the
    // number of elements.
    protected SLLNode first, last;
    protected int length;

    //////////// Constructor ////////////

    public LinkedList () {
    // Construct a list, initially empty.
        first = last = null;
        length = 0;
    }

    //////////// Accessors ////////////

    public boolean isEmpty () {
    // Return true if and only if this list is empty.
        return (first == null);
    }

    public int size () {
    // Return this list's length.
        return length;
    }

    public Object get (int i) {
    // Return the element with index i in this list. Throw an
    // IndexOutOfBoundsException if i is out of range.
    // complete this method and remove return null;
        if (i < 0 || i >= length)
            throw new IndexOutOfBoundsException();
        else {
            SLLNode curr = node(i);
            return curr.element;
        }
        
    }

    public boolean equals (List that) {
    // Return true if and only if this list and that have the same length, and
    // each element of this list equals the corresponding element of that.
        LinkedList other = (LinkedList) that;
        if (length != other.length)
            return false;
        for (SLLNode curr1 = first, curr2 = other.first;
                curr1 != null;
                curr1 = curr1.succ, curr2 = curr2.succ) {
            if (! curr1.element.equals(curr2.element))
                return false;
        }
        return true;
    }

    //////////// Transformers ////////////

    public void clear () {
    // Make this list empty.
        first = last = null;
        length = 0;
    }

    public void set (int i, Object elem) {
    // Replace by elem the element at index i in this list. Throw an
    // IndexOutOfBoundsException if i is out of range.
        if (i < 0 || i >= length)
            throw new IndexOutOfBoundsException();
        SLLNode curr = node(i);
        curr.element = elem;
    }

    public void add (int i, Object elem) {
    // Add elem as the element with index i in this list. Throw an
    // IndexOutOfBoundsException if i is out of range.
        if (i < 0 || i > length)
            throw new IndexOutOfBoundsException();
        SLLNode newest = new SLLNode(elem, null);
        if (i == 0) {
            newest.succ = first;
            first = newest;
        } else {
            SLLNode pred = node(i-1);
            newest.succ = pred.succ;
            pred.succ = newest;
        }
        if (newest.succ == null)
            last = newest;
        length++;
    }

    public void add (Object elem) {
    // Add elem after the last element of this list.
        SLLNode newest = new SLLNode(elem, null);
        if (first == null)
            first = newest;
        else
            last.succ = newest;
        last = newest;
        length++;
    }

    public void addAll (List that) {
    // Add all the elements of that after the last element of this list.
        Iterator iter = that.iterator();
        while (iter.hasNext())
            this.add(iter.next());
    }

[B]    public Object remove (int i) {
    // Remove and return the element with index i in this list. Throw an
    // IndexOutOfBoundsException if i is out of range.
    // complete this method and remove return null;
        if (i < 0 || i >= length)
            throw new IndexOutOfBoundsException();
        else {
             SLLNode selectedNode = node(i);
             node(i).element = node(i).succ.element;
             last = null;
             length--;
             return selectedNode;
        } 
    }[/B]

    //////////// Iterator ////////////

    public Iterator iterator () {
    // Return an iterator that visits all elements of this list, in
    // left-to-right order.
        return new LinkedList.LRIterator();
    }

    /////////// Auxiliary method ////////////

    protected SLLNode node (int i) {
    // Return a link to the node containing the element with index i in
    // this list.
        SLLNode curr = first;
        for (int j = 0; j < i; j++)
            curr = curr.succ;
        return curr;
    }

    //////////// Inner class ////////////

    private class LRIterator implements Iterator {

        private SLLNode place, prev, curr;

        private LRIterator () {
            place = first;
            curr = prev = null;
        }

        public boolean hasNext () {
            return (place != null);
        }

        public Object next () {
            if (place == null)
                throw new NoSuchElementException();
            Object nextElem = place.element;
            prev = curr;
            curr = place;
            place = place.succ;
            return nextElem;
        }

        public void remove () {
            if (curr == null)
                throw new NoSuchElementException();
            if (prev == null)
                first = first.succ;
            else
                prev.succ = curr.succ;
            length--;
        }
    }
}


SLLNode

public class SLLNode {

    protected Object element;    // ... value contained in this node.
    protected SLLNode succ;      // ... link to this node's successor.

    protected SLLNode (Object elem, SLLNode succ) {
        // Construct a node with value elem and successor succ.
        this.element = elem;
        this.succ = succ;
    }
}

The problem I'm having is with the bolded remove method. I want the user to be able to specify the element to remove, remove it and return what was removed then update the list. As it works now, all that happens is the entry to be removed is changed to equal the same as its successor and is returned, but not taken out of the list. Was wondering if anyone could point me in the right direction here?

#2
bobdark

bobdark

    Programmer

  • Members
  • PipPipPipPip
  • 164 posts
seems to me its happening because you update node(i) instead of updating the predecessor node of node(i) to point to the successor of node(i).

#3
ZipOnTrousers

ZipOnTrousers

    Learning Programmer

  • Validating
  • PipPipPip
  • 94 posts
Ah yeah that makes sense now that you've said it. However, from what I can see from these classes, theres no way to get the predecessor as the SLLNode class only has element and successor... (this is an exercise we were given with partial code to complete so I dont think I can edit any of the classes other than those instructed to)

#4
bobdark

bobdark

    Programmer

  • Members
  • PipPipPipPip
  • 164 posts
How about checking whether i equals 0? If yes then you dont have to update the predecessor since its the head and doesn't have one. If i is bigger than 0, then you can locate the node with index i-1, and it would be your predecessor.

#5
ZipOnTrousers

ZipOnTrousers

    Learning Programmer

  • Validating
  • PipPipPip
  • 94 posts
     public Object remove (int i) {
    // Remove and return the element with index i in this list. Throw an
    // IndexOutOfBoundsException if i is out of range.
    // complete this method and remove return null;
        if (i < 0 || i > length )
            //if position entered is out of boands
            throw new IndexOutOfBoundsException();
        else {
             // store the node to be removed in local var. to be returned later
             SLLNode selectedNode = node(i);
             // if the node to be removed is not the first node in the list
             if (i > 0) {
                // make the predecessor of i link to i's successor
                node(i-1).succ = node(i).succ;
             // if i IS the first node in the list
             } else if (i == 0) {
                // make i = its successor
                node(i).element = node(i).succ;
             }
             length--;
             return selectedNode;
        } 
    }

K so I've managed to get it to work for any node, unless its the first node. To try and combat this I've introduced the above condition, though im not sure if my logic works here. If i is 0, and therefore node(i) is the head of the SLL, it makes node(i).element = its successor. But this doesn't remove node(i), it just displays some hexadecimal, I'm assuming because element is jut of type Object so instead of displaying the value of .succ its merely displaying a text representation of an object... Is there anyway to delete the first node?

#6
bobdark

bobdark

    Programmer

  • Members
  • PipPipPipPip
  • 164 posts
how about setting the 'first' to be the successor of current 'first'?

#7
ZipOnTrousers

ZipOnTrousers

    Learning Programmer

  • Validating
  • PipPipPip
  • 94 posts
K that works, totally forgot about the variable! That was driving me mental thanks bobdark.