Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie

Java Linked List Question

Options
  • 29-07-2011 1:55pm
    #1
    Registered Users Posts: 181 ✭✭


    Suppose the method below has been added to a LinkedLsit implementation.

    public int doStuff(Object object){
    int result = 0;
    if(!isEmpty()){
    for(Node current = firstNode, previous = null; current != null; previous = current, current = current.next){
    if(current.data.equals(object)){
    result++;
    if(current == firstNode){
    firstNode = current.next;
    }else{
    previous.next = current.next;
    }
    length--;
    }
    }
    }
    return result;
    }


    What is the role of the method and what is the significance of its integer return value?

    This is a question from a previous final year exam in college for data structures.
    PS I know this is a remove function but just dont know how to phrase the answer.

    Thanks in advance


Comments

  • Registered Users Posts: 181 ✭✭Mutant


    0vertone wrote: »
    Ehm. Its not a remove function. It is 2:24 in the morning though so I could be just missing it.

    I wont point out exactly what its doing because that would be doing too much but I will tell you how to get your answer and I'll be as specific as possible.

    Go through each conditional. Analyze exactly what its checking and think why it might be checking it.

    particular mention goes to this:
    if(current.data.equals(object)){result++;}

    This is the only time result is ever changed and should give you a clear indication of what the method is doing from this one line. Once you get that, the rest should follow pretty easy.

    Also
    Length--;

    Length is never defined. Its never instantiated. Its never anything. But Assuming it is an exam question, the probably expect you to assume that it has been.

    package adts;

    import java.util.Vector;

    public class LinkedList implements ListInterface {
    private class Node {
    private Object data; // entry in the list
    private Node next; // link to next node

    private Node(Object dataPortion){
    data = dataPortion;
    next = null;
    }

    private Node(Object dataPortion, Node nextNode){
    data = dataPortion;
    next = nextNode;
    }
    } //

    private Node firstNode; // reference to the first node
    private Node lastNode ;
    private int length = 0 ; // current num entries in list

    public LinkedList(){
    clear();
    }

    public boolean add(Object newEntry) {
    Node newNode = new Node(newEntry);

    if(isEmpty()){
    firstNode = newNode;
    }
    else{
    Node lastNode = getNodeAt(length);
    lastNode.next = newNode; // make last node reference new node
    }
    length++;
    return true;
    }

    public boolean addAtTail(Object newEntry) {
    Node newNode = new Node(newEntry);

    if(isEmpty()){
    firstNode = lastNode = newNode;
    }
    else{
    //Node lastNode = getNodeAt(length);
    lastNode.next = newNode;
    }
    length++;
    return true;
    }


    private Node getNodeAt(int givenPosition){
    Node currentNode = firstNode;

    for(int i=1;i<givenPosition;i++){
    currentNode = currentNode.next;
    }
    return currentNode;
    } // end getNodeAt


    public boolean add(int newPosition, Object newEntry) {
    boolean isSuccessful = true;

    if((newPosition >=1) && (newPosition<=length+1)){
    Node newNode = new Node(newEntry);

    /* Case 1: Adding to the start of the list */
    if(isEmpty() || (newPosition == 1)){
    newNode.next = firstNode;
    firstNode = newNode;
    }
    /* Case 2: newPosition > 1, list not empty */
    else{
    Node nodeBefore = getNodeAt(newPosition-1);
    Node nodeAfter = nodeBefore.next;
    newNode.next = nodeAfter;
    nodeBefore.next = newNode;
    }
    length++;
    }
    else{
    isSuccessful = false;
    }
    return isSuccessful;
    }

    public void clear() {
    firstNode = null;
    length = 0;
    } // end clear

    public boolean contains(Object anEntry) {
    return findNode(anEntry) != null ;
    }

    private Node findNode(Object anEntry) {
    if (!isEmpty() && (anEntry != null) ) {
    for (Node current = firstNode; current != null ;
    current = current.next) {
    if (current.data.equals(anEntry))
    return current ;
    }
    }
    return null ;
    }

    public void display() {
    // TODO Auto-generated method stub

    }

    public Object getEntry(int givenPosition) {
    Object result = null ;
    if (!isEmpty() && (givenPosition <= length) ) {
    result = getNodeAt(givenPosition).data;
    }
    return result ;
    }

    public int getLength() {
    return length;
    }

    public boolean isEmpty() {
    return length == 0;
    }

    public boolean isFull() {
    return false;
    }

    public Object remove(int givenPosition) {
    Node result = null; // return object

    if((givenPosition >= 1) && (givenPosition <= length)){
    Node before = getNodeAt(givenPosition-1); // get entry to be removed.
    result = before.next ;
    before.next = before.next.next ;
    length--;
    }
    return result;
    }

    public boolean remove(Object objectToRemove) {
    boolean result = false ;
    if (!isEmpty()) {
    for (Node current = firstNode, previous = null; current != null ;
    previous = current, current = current.next) {
    if (current.data.equals(objectToRemove)) {
    result = true ;
    if (current == firstNode) {
    firstNode = current.next ;
    } else {
    previous.next = current.next ;
    }
    length-- ;
    }
    }
    }
    return result;
    }

    public boolean replace(int givenPosition, Object newEntry) {
    boolean result = false;
    if((givenPosition >=1) && (givenPosition <= length)){
    Node node = getNodeAt(givenPosition);
    node.data = newEntry ;
    result = true ;
    }
    return result;
    }

    public boolean addGroup(Vector objects, int start) {
    if (start > 0 && start <= getLength() + 1) {
    LinkedList mini = new LinkedList() ;
    for (int i = 0 ; i < objects.size() ; i++) {
    mini.add(objects.get(i)) ;
    }
    Node startNode = getNodeAt(start-1) ;
    mini.getNodeAt(objects.size()).next = startNode.next ;
    startNode.next = mini.getNodeAt(1) ;
    length += objects.size() ;
    return true ;
    }
    return false;
    }

    public Vector getRange(int pos1, int pos2) {
    Vector result = new Vector() ;
    if (pos1 < 0) {
    if (pos2 < 0 ) {
    int temp = pos1 ;
    pos1 = getLength() + pos2 + 1;
    pos2 = getLength() + temp + 1;
    }
    }
    if (pos1 <= pos2 && pos2 <= getLength() && pos1 >0) {
    for (Node current = getNodeAt(pos1); pos1 <= pos2 ;
    pos1++ , current = current.next) {
    result.add(current.data) ;
    }
    }
    return result;
    }

    public boolean swap(Object one, Object two) {
    Node node1 = findNode(one) ;
    Node node2 = findNode(two) ;
    if (node1 != null && node2 != null) {
    Object temp = one ;
    node1.data = two ;
    node2.data = temp ;
    return true ;
    }
    return false;
    }

    }
    That is an example solution from the course, as you see the part in red is the same as my original topic, Thats how i know its a remove function, the thing is i dont know how to explain it.


  • Registered Users Posts: 255 ✭✭boblong


    Mutant wrote: »
    how to explain it.

    OK, so basically the algorithm is:
    foreach node in nodes:
      if node.value == toberemoved
        delete(node)
    

    The way delete() commonly works in linked list implementations is to "skip" over the node you want to remove.

    If the node we want to remove is currently the first node, we skip over it by placing the firstNode pointer to be the next node. ie.

    ToOOo.png

    Otherwise, we use the previousNode pointer (which we've been keeping track of) to skip over the node:

    PtpKJ.png

    The second version of the code you posted returns a boolean value to mark that something has been found. The first version increments a counter.


  • Registered Users Posts: 181 ✭✭Mutant


    boblong wrote: »
    OK, so basically the algorithm is:
    foreach node in nodes:
      if node.value == toberemoved
        delete(node)
    

    The way delete() commonly works in linked list implementations is to "skip" over the node you want to remove.

    If the node we want to remove is currently the first node, we skip over it by placing the firstNode pointer to be the next node. ie.

    ToOOo.png

    Otherwise, we use the previousNode pointer (which we've been keeping track of) to skip over the node:

    PtpKJ.png

    The second version of the code you posted returns a boolean value to mark that something has been found. The first version increments a counter.

    Thank you very much, that was very well explained,

    Im sorry forgot to point out the boolean int difference in the question.

    I dont think it makes a big difference, does it?

    And can you tell me whats the significance of the integer type in the first post is,


Advertisement