Singly LinkedList headAdd / headDelete methods

[Cemal Özdemir]

Hello,

Algorithm and Java beginner here. I constructed a singly linked list like this:

public class LinkedList {

public LinkedList head;

String key;
LinkedList link;

public LinkedList(String key) {
    this.key = key;
    this.link = null;
    head = this;
}

public void headAdd(String key) {
// Something is wrong about this part!
LinkedList temp = head;
LinkedList newHead = new LinkedList(key);
newHead.link = temp;
}

public void headDelete() {
// And this part too...
head = head.link;
}

public String toString() {
    return key;
}

public static final String CANONICAL_NULL = "null list";
static final String NODE_LEFT = "(";
static final String NODE_RIGHT = ")";

public static String canonical(LinkedList list) {
    if (list == null) {
        return CANONICAL_NULL;
    }
    LinkedList current = list.head;
    StringBuffer sb = new StringBuffer();
    while (current != null) {
        sb.append(NODE_LEFT);
        sb.append(current.key);
        sb.append(NODE_RIGHT);
        current = current.link;
    }
    return sb.toString();
}
}

When this code is tested with an automatic scoring tool, my methods headAdd and headDelete are failing. How can I correct these methods without changing any other part of the code?

Thank you for your help.

[Winston Gutkowski]

Cemal Özdemir wrote:When this code is tested with an automatic scoring tool, my methods headAdd and headDelete are failing.

'Fraid that's not enough information.

How are they failing? And please provide exact messages.

One thing I do see though is that you seem to be combining both a 'Node' and a 'List' in your class.

Normally a "linked list" is a list that contains Nodes (actually only one - the first one, or 'head'). Each Node then contains a pointer to the one that follows it - or null if it's the last one in the chain.

Thus you normally have two classes: LinkedList and Node; and the latter is usually a static nested class, because it really only has any meaning inside your list class.

HIH

Winston

[Cemal Özdemir]

Hello again, these are the test cases:


TEST: linkedlist_headDelete_1
description: delete from 1-node list
Correct: ** null list **
Yours: ** null list **
5 SUCCESS

TEST: linkedlist_headDelete_2
description: delete from 2-node list
Correct: (b0)
Yours: ** null list **
0 FAILED

TEST: linkedlist_headAdd_1
description: Add 1-node list
Correct: (b0)
Yours: (b0)
5 SUCCESS

TEST: linkedlist_headAdd_2
description: Add 2-node list
Correct: (b1)(b0)
Yours: (b0)
0 FAILED

TEST: linkedlist_headAdd_3
description: Add 3-node list
Correct: (b2)(b1)(b0)
Yours: (b0)
0 FAILED

[Winston Gutkowski]

Cemal Özdemir wrote:Hello again, these are the test cases:

Much better. After a cursory glance, one thing I see is that in your headAdd() method you create a newHead object, but never assign it to head, so your list will keep pointing to the original one. Nothing else leaps out at me, so it may be your only problem.

I still say that the structure is wrong though. A single-linked list should only have 1 pointer per value and you have 2: 'head' and 'link'.

Winston