explain Linked List data structure in Java

Question

Iknow java is passed by value. For linked list data structure, what is the difference between method size() and size1()? I think there are the same becasue the head and next reference point to the same thing in size1(). but the result is difference

public class IntList {
int item;
IntList next; 

public  IntList(int item, IntList next){
    this.item = item;
    this.next = next;
}

public int size(){
    int size = 1;
    while (next !=null){
        size++;
        next = next.next;
    }
    return size;
}

public int size1(){
    int size = 1;
    IntList head = next;
    while (head != null){
        size++;
        head = head.next;
    }
    return size;
}
public static void main(String[] args) {
    IntList L = new IntList(1,null);
    L = new IntList(2,L); 
    L = new IntList(3,L);
    L = new IntList(10,L);
    L = new IntList(20,L);
    System.out.println(L.size());

}

}

I am confused about the reference means in java.

Is the result different if you call `size1()` first? – shmosel Jun 19 '17 at 01:27 — shmosel, Jun 19 '17 at 01:27
yes. size() will modify the L; but size1() don't change L – jason Jun 19 '17 at 01:28 — jason, Jun 19 '17 at 01:28

score 1 · Answer 1 · answered Jun 19 '17 at 01:30

1

They're logically the same, but size() is actually pointing next to the final node, so the next size check will return 1. size1() uses a local variable to traverse the list, so the object state isn't affected.

answered Jun 19 '17 at 01:30

shmosel

49,289
6
73
138

sound good. why size1() don't change the object state. since the head and next point to the same things. head will point the the final node. Therefore, will the next also point to the last node since head = next? Thanks. – jason Jun 19 '17 at 01:41
@jason No, variables in Java [are never by reference](https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value). Both variables point to the same *object* to begin with, but changing one *reference* doesn't affect the other. – shmosel Jun 19 '17 at 01:43
That make sense Thanks so much. – jason Jun 19 '17 at 03:12
what happen if we add head.item = 1000; after head = head.next; in size(). will this statement change the value of L's item. Thanks. – jason Jun 19 '17 at 03:25
1

@jason Why don't you try? – shmosel Jun 19 '17 at 03:31
I try it, it definitely change the L. – jason Jun 19 '17 at 03:32
why head.item change the list's item. but head.next don't change the L's next? – jason Jun 19 '17 at 03:40
@jason You're not modifying `head.next`. – shmosel Jun 19 '17 at 04:03

Cole Nelson · Accepted Answer · 2017-06-19T14:58:59.443

1

This is a matter of issue with scope. In size1(), you are creating a local variable named head. When you call size1() it creates a reference variable that will be destroyed at the end of the call. This means that no matter how many times you call size1(), it will always give you the proper size.

However, when you use the field "next" in size(), it iterates through each variable until the end. However, once it gets there, it is notdestroyed because its scope is the object. This means the next time you call size(), and all subsequent calls (given no changes), it will always return 1.

edited Jun 19 '17 at 14:58

answered Jun 19 '17 at 02:02

Cole Nelson

124
5

yes, My concern is that "head" and "next" is pointing to same reference. "head" will finally point to the last node, so does the "next". "head" will be destroyed; "next" will notdestroyed but now it points to last node. Am I right? thanks. – jason Jun 19 '17 at 03:29
Yep, I just added a quick diagram. Hopefully it helps. – Cole Nelson Jun 19 '17 at 14:59

explain Linked List data structure in Java

2 Answers2