Java Linked List Question

Mutant

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

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.

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.



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



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.

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.



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



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,