CODEWITHSUNDEEP
javalinked-list
vaindil
vaindil

Reputation: 7864

Removing head from a linked list in Java

This should be a fairly basic question, but I cannot for the life of me figure it out. I'm using two files given to me by my instructor, and I have to write a method removeFirst that will remove the head from a declared linked list and return that old head value. It cannot take any parameters. Here's file 1 and file 2.

My code for removeFirst and debugging is below. I do not know how to reference the aList without being able to use it as a parameter, especially since the linked list is not global. When I use the debugging code, it prints aList, then prints 21 (the head of the list that it should be removing, and which is what removeFirst should be returning), but then it does not print the updated linked list -- it's just blank.

removeFirst code:

public IntNode removeFirst() {
    IntNode cur = getHead();

    head = cur.getNext();
    head.setPrev(null);

    cur.setNext(null);

    return cur;
}

Debug code (at bottom of main):

for(int i = 0; i < aList.size(aList.getHead()); i++) {
    aList.print(aList.findObject(i));
}

aList.print(aList.removeFirst());
System.out.println("");

for(int j = 0; j < aList.size(aList.getHead()); j++) {
    aList.print(aList.findObject(j));
}

Upvotes: 1

Views: 8492

Answers (3)

Yogendra Singh
Yogendra Singh

Reputation: 34387

I think you doing all fine except the return. You need to return head in place of cur as cur is representing the removed head node(previous one).

public IntNode removeFirst() {
    IntNode cur = getHead();

     head = cur.getNext();
     head.setPrev(null);

     cur.setNext(null);

     return head;
 }

EDIT: Since you have updated your question, here is the answer of your second question;

You can refer aList using this operator.

Update: I added removeFirst() method in your MyLinkedList class as it is then I added these thwo statements in your method (in the end)

    aList.removeFirst();
    aList.print(aList.getHead());
    System.out.println("");

It works correctly and prints the output as:

    84 88 92 96 100 
    100 96 92 88 84 
    Size = 5
    Adding another IntNode
    21 84 88 92 96 100 
    Adding yet another IntNode
    21 52 84 88 92 96 100 
    The object is 92
    The object containing 50 was not found.
    The object removed has 96 in it.
    The object containing 50 was not found. Nothing was removed.
    21 52 84 88 92 100 
    Removing Head
    52 84 88 92 100

Upvotes: 1

Grambot
Grambot

Reputation: 4523

My assumption would be that since you're accessing all your Objects by reference you are essentially destroying your list as you execute the removeFirst()

IntNode cur = getHead();

same as

cur = head;

As they're accessible in the same scope. By doing this when you execute:

head.setPrev(null);
...
cur.setNext(null);

you're basically doing this:

head.setPrev(null);
...
head.setNext(null);

or....

null <-- head --> null

See where this is going?

What you're aiming to do is get a copy of the node you're removing and then destroying that copy's reference to the list.

IntNode cur = new IntNode(getHead().getVal());

and when you're trying to remove the old head from the node:

head.setNext(head.getNext());
head.setPrev(null);

Upvotes: 1

Ted Hopp
Ted Hopp

Reputation: 234857

You need to return head; instead of return cur;

EDIT Sorry. I evidently misunderstood your problem statement. The above is appropriate if the removeFirst() method is supposed to return the new head of the list. If it's supposed to return the removed element (as is clear now after your comment and edit of the original post), then it should be working properly.

Presumably removeHead() is an instance method in your list class. You don't need to pass a parameter because the list is available as this inside the method.

It would help to see the class definition for aList. Your file 1 link says it's to MyLinkedList.java, but the pasted code there is for IntNode.java.

EDIT 2 The problem, I think, may be your debug code. findObject(j) does not return the jth element of the list--it returns the list element that contains j as a value. From the code, it looks like MyLinkedList.print(IntNode) prints the entire list starting at the indicated node. What happens if you replace the for loops in your debug code with simply:

aList.print(aList.getHead());

Upvotes: 6

Related Questions