Linked list by reference or by value?

Question

Here is the question. Say a linked list is implemented as follows (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

Consider the linked list:

1 -> 2 -> 3 -> 4

I do something like:

ListNode newHead = head;
newHead = head.next.next; 
//Now newHead is pointing to (3) in the linked list.

Now I perform the magic:

newHead.val = 87

The linked list becomes:

1 -> 2 -> 87 -> 4

If I printed head and NOT newHead.

Why is this? I didn't modify anything with head but it still changed?

Apparently, it's because you are changing the same object. The ListNodes contain only the references to each ListNode. — matfax, Mar 15 '17 at 15:28
@MatthiasFax, is it always like this if I make a class and then do this? — sssszzzzzzssszzz, Mar 15 '17 at 15:30
Yes, if you don't clone or deep-copy the object, there will only be references to the value (except with primitives). Check these existing questions: http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value http://stackoverflow.com/questions/4600974/passing-primitive-data-by-reference-in-java — matfax, Mar 15 '17 at 15:33

score 0 · Answer 1 · answered Mar 15 '17 at 15:32

So you can use this:

Node Class:

public class IntNode {

    int value;
    IntNode next;

    public IntNode(int value) {
        this.value = value;
    }
}

Singly Linked List Class:

/**
 * A singly-linked list of integer values with fast addFirst and addLast methods
 */
public class LinkedIntList {

    IntNode first;
    IntNode last;
    int size;

    /**
     * Return the integer value at position 'index'
     */
    int get(int index) {
        return getNode(index).value;
    }

    /**
     * Set the integer value at position 'index' to 'value'
     */
    void set(int index, int value) {
        getNode(index).value = value;
    }

    /**
     * Returns whether the list is empty (has no values)
     */
    boolean isEmpty() {
        return size == 0;
    }

    /**
     * Inserts 'value' at position 0 in the list.
     */
    void addFirst(int value) {
        IntNode newNode = new IntNode(value);
        newNode.next = first;
        first = newNode;
        if(last == null)
            last = newNode;
        size++;
    }

    /**
     * Appends 'value' at the end of the list.
     */
    void addLast(int value) {
        IntNode newNode = new IntNode(value);
        if(isEmpty())
            first = newNode;
        else
            last.next = newNode;

        last = newNode;
        size++;
    }

    /**
     * Removes and returns the first value of the list.
     */
    int removeFirst() {
        if(isEmpty()) {
            System.out.println("RemoveFirst() on empty list!");
            System.exit(-1);
        }

        int value = first.value;
        if(first == last) {
            // List has only one element, so just clear it
            clear();
        }
        else {
            first = first.next;
            size--;
        }

        return value;
    }

    /**
     * Removes and returns the last value of the list.
     */
    int removeLast() {
        if(isEmpty()) {
            System.out.println("RemoveLast() on empty list!");
            System.exit(-1);
        }

        int value = last.value;
        if(first == last) {
            // List has only one element, so just clear it
            clear();
        }
        else {
            // List has more than one element
            IntNode currentNode = first;
            while(currentNode.next != last)
                currentNode = currentNode.next;

            currentNode.next = null;
            last = currentNode;
            size--;
        }
        return value;
    }

    /**
     * Removes all values from the list, making the list empty.
     */
    void clear() {
        first = last = null;
        size = 0;
    }

    /**
     * Returns a new int-array with the same contents as the list.
     */
    int[] toArray() {
        int[] array = new int[size];
        int i = 0;
        for(IntNode n = first; n != null; n = n.next, i++)
            array[i] = n.value;
        return array;
    }

    /**
     * For internal use only.
     */
    IntNode getNode(int index) {
        if(index < 0 || index >= size) {
            System.out.println("GetNode() with invalid index: " + index);
            System.exit(-1);
        }

        IntNode current = first;
        for(int i = 0; i < index; i++)
            current = current.next;
        return current;
    }
}

See the comments in the code for description.

Linked list by reference or by value?

1 Answers1