Building a linked list in Java

Question

This is an example from my book. As I see it, when you create a list with this class, you create two objects (first and last, which are null). I can't figure out why, when you put both first and last "Node" objects in the add method. Shouldn't it create two elements when you set both first = n and last = n. For example, if I call list.add(2), shouldn't both first and last be 2 now ?

public class List {

    private Node   first = null;
    private Node   last = null;

    public List(){
        first = null;
        last = null;

    }   

    private static class Node{

        public int   value;
        public Node   next;

        public Node ( int value, Node next){
            this.value = value;
            this.next = next;       
        }
    }   

    public void add (int value){
        Node   n = new Node (value,null);

        if(first==null){
            first = n;
            last = n;

        }else{
            last.next = n;
            last = n;
        }
    }

    public int size(){
        int   number = 0;
        Node   n = first;
        while(n != null){
            number++;
            n = n.next;
        }
        return number;
    }
}

I suggest you write unit tests

Savino Sguera
– Savino Sguera

2012-01-19 18:42:49 +00:00
Commented Jan 19, 2012 at 18:42 — Savino Sguera
– Savino Sguera, Commented Jan 19, 2012 at 18:42

ruakh · Accepted Answer · 2012-01-19 18:45:06Z

3

As i see it, when u create a list with this class, you create two objects (first and last, which are null).

That's not true. first and last are not objects, but references to objects. And in this case, they start out as null references, meaning that they don't refer to any object at all.

When you write first = n; last = n;, you set first and last to both refer to the same object — whatever object n refers to.

For example, if list.add(2), shouldn't now both first and last be 2?

Yes, they'll both refer to the same Node instance, whose value is 2.

answered Jan 19, 2012 at 18:45

ruakh

185k29 gold badges292 silver badges324 bronze badges

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

6 Comments

user1159186 Over a year ago

Thank you for the quick answer. So, I actually have two elements who point to the same value.

ruakh Over a year ago

@user1159186: I wouldn't put it quite that way, no. Since you're talking about a linked-list, "element" sounds like "list element", and "value" sounds like the value of a Node. Your list has only one element. The list object has two fields, which both point to the same Node (i.e., to the same list element). Naturally that Node has only one value.

user1159186 Over a year ago

If i were to add another node, lets say, list.add(2), list.add(3) and list.add(4), would now the first = node.value = 2 and last = node.value = 3 or 4?

ruakh Over a year ago

@user1159186: Suppose you wrote List list = new List(); list.add(2); list.add(3); list.add(4);. Then list.first.value would be 2, list.first.next.value would be 3, and list.first.next.next.value would be 4. Also, list.last and list.first.next.next would refer to the same object, so list.last.value would be 4 and list.first.next.next.next would be null (since list.last.next is always null).

user1159186 Over a year ago

So a new "next Node" is created everytime the add method is called?

|

ThePrimeagen · Accepted Answer · 2012-01-20 03:48:53Z

0

Yes i see that first and last are needed. Probably later on first will be much more useful if you have dequeue (remove first) or a search (which i guess can be done from the end rather than at the start, same process for a simple linear search).

As for your question. Yes if you started with a blank list and said list.add(2). Both first and last will be pointing to node with value 2. This is because the first element and the last element in the list are the same, hence 1 element in the list. Its both first and last (and middle if you want to be weird).

but if you did list.add(1), list.add(2). You would get first = node.value == 1 and second = node.value == 2

edited Jan 20, 2012 at 3:48

answered Jan 19, 2012 at 18:45

ThePrimeagen

4,5824 gold badges35 silver badges45 bronze badges

3 Comments

ruakh Over a year ago

Re: "First no need for last": That's not true. This class's add(int) method adds a new element to the end of the list. If you got rid of the last field, that would require iterating through the whole list. (I suppose the functionality would be equivalent, but since you're suggesting changing size() to be O(1) rather than O(n), I don't see why you'd call it "weird" that add(int) is already O(1) rather than O(n).)

user1159186 Over a year ago

Wow, i think i get it now. You guys are great!

ThePrimeagen Over a year ago

wopsy! of course i did not read that part. It makes sense. Your correct. I did not see the whole add with the last. For some odd reason in my head i was thinking Queue rather than your standard LinkedList. I am a dummy here and there

Collectives™ on Stack Overflow

Building a linked list in Java

2 Answers 2

6 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related