0

I realize that there are a few good threads already existing which discuss how to implement a linked list in Java, however I can't seem to find one which does not use a constructor like this,

public LinkList() {
    Link = null;
}

or something along these lines. However, I have not done this in my code, and therefore I am having trouble with writing a few of the methods.

I have a class called Link which contains the following code, note without any constructor like the one displayed above:

public class Link {
private Link next = null;
private String value = null;

public Link getNext(){
    return next;
}

public void setNext(Link nextLink){
    next = nextLink;
}

public String getValue(){
    return value;
}

public void setValue(String aValue){
    value = aValue;
}
}

and then I have my LinkedList class, which contains the following code:

public class LinkedList {
private Link head = null;
private Link tail = null;

public Link getHead(){
    return head;
}

public void setHead(Link aLink){
    head = aLink;
}

public Link getTail(){
    return tail;
}

public void setTail(Link aLink){
    tail = aLink;
}

public boolean isEmpty(){
    return(head == null && tail == null);
}

public void addLast(String aString){
    Link link = new Link();
    link.setValue(aString);
    //tail.setNext(link);
    if(isEmpty()){
        head = link;
    }else{
        tail.setNext(link);
    }
    tail = link;

    }

public void addFirst(String aString) {
    Link link = new Link();
    link.setValue(aString);

    if(isEmpty()){  
        tail = link;
    }else{
        head.setNext(link);
    }
    head = link;        
}

public Link removeFirst(){
    Link temp = head;
    head = temp.getNext();
    temp.setNext(null);

    return temp;
}

}

My addFirst Method, and my isEmpty Method both seem to be working but my addLast and removeFirst Methods are not. I have drawn pictures, looked at pseudo code, and searched around the internet, but I just cannot seem to figure this out.

I need to know how to get my addLast and removeFirst methods working without having to add in the constructor at the beginning like all the rest of the example code I keep seeing.

Here are the Tests they need to pass:

    @Test
public void testRemoveFirst(){
    list.addFirst("three");
    list.addFirst("two");
    list.addFirst("one");
    assertTrue("one".equals(list.removeFirst()));
    assertTrue("two".equals(list.removeFirst()));
    assertTrue("three".equals(list.removeFirst()));
}

@Test
public void testAddLast(){
    list.addFirst("three");
    list.addFirst("two");
    list.addFirst("one");
    assertTrue( "three".equals(list.removeLast()));
    assertTrue( "two".equals(list.removeLast()));
    assertTrue( "one".equals(list.removeLast()));
    assertNull(list.removeLast());
}
12
  • 7
    Why do you not want a constructor? Commented Oct 3, 2015 at 20:33
  • Can you provide a test case where those methods don't work? Commented Oct 3, 2015 at 20:34
  • 4
    (And why do you think the constructor has anything to do with your problem?) Commented Oct 3, 2015 at 20:35
  • You have a constructor in both classes, you use it yourself here Link link = new Link(); compiler will generate it for you. Commented Oct 3, 2015 at 20:36
  • 4
    "...my professor would like us to know how to create a Linked List without the use of one." - Aha. You're taking one of those classes that should be titled "stupid Java tricks." Commented Oct 3, 2015 at 20:58

2 Answers 2

2

One change in your code is needed: you want the new link to point to your old head as "next" (not the other way round) because you want to insert it at the beginning.

public void addFirst(String aString) {
        Link link = new Link();
        link.setValue(aString);

        if (isEmpty()) {
            tail = link;
        } else {
            link.setNext(head);
        }
        head = link;
    }

Also, you need to change your tests as now you compare String to Link instances instead of String to String

    assertTrue("one".equals(list.removeFirst().getValue()));
    assertTrue("two".equals(list.removeFirst().getValue()));
    assertTrue("three".equals(list.removeFirst().getValue()));

After those changes the test passes for me (the first one, you didn't implement removeLast method for the second one).

Sign up to request clarification or add additional context in comments.

10 Comments

Oh, Okay. That first part makes some sense, and I changed the test like you said and green light. However, I'm wondering wither or not there is a way to make it green light the way it was written? My professor was the one who wrote the test, but I thought he had said something along the lines that he had written one of them incorrectly. However, I'm not sure.
You can make them pass if your list.removeFirst() method will return String instead of Link. You should actually probably implement it this way as users of your List implementation shouldn't be aware of implementation details. Link class is an implementation detail and should be used only internally and not be visible externally (which can even be enforced by making it inner static class of List or making it package private in the same package as the List class). Also, you take String instance from user in add method, it would be consistent to return String in removeFirst.
I'm confused on how I would write this. Change it to a String type, and have it return a string, but how? My brain feels so fried from the hours I've spent on this.
You just need to change the last line of removeFirst method from return temp; to return temp.getValue(); and change the method signature to return String. Nothing else needs to be changed I think.
addLast looks quite fine to me. remove last is not really a simple inverse of removeFirst as you have a single-linked list. You have the reference to the tail Link but you don't know what's before your tail Link. Therefore when you will want to remove your tail you will want to change the pointer of 'what is before tail' to null but you cannot find it in any other way than iterating over the list until you find it. You can find some examples in google, like this one stackoverflow.com/questions/15792682/…
|
0

You do not need a constructor to assign null, 0 and false to object fields. Fields get these values automatically. Simply remove the constructor that only does such assignments and it will be no any difference in execution.

You can also assign other default values like int a = 17 directly in declaration, and you can also include expressions like int b = a + 1 assuming that the field a has been declared before. But you cannot pass parameters that must have different values for different instances. This is what the constructor is for.

You may still have other bugs remaining but it will be no constructor to blame.

Most often developers simply use the ready solution, LinkedList.

2 Comments

I am aware of this information. I think I was a little confused on what I was trying to ask. I'm just not sure where to go on this/ how to write and pass those two methods.
Why area you asking if you are aware?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.