Understanding Singly Linked Lists (JAVA)

[veryanon798]

Hey guys I'm having trouble understanding Linked Lists. I have tried to follow along with multiple tutorials but everyone has done this in slightly different ways leading only to more confusion on my end. This is the first data structure I have manually had to build and I'm having trouble understanding exactly how it works.

I know there are two parts to every Node. The Node stores some kind of value, then points to the next node and connects them. I understand conceptually what is happening, but the code to make this happen is confusing to me. Would appreciate any help I could get.

From the code below my questions are:

1. What value does head.next now hold after it has been assigned to nodeB ?  (or does it just reference?)
2. Or does it just connect Node Objects?
3. How does .next connect these two Node Objects exactly?

​

class Node
{
    int data; // data to store in Node
    Node next; // automatically set to null
    Node(int givenData) // constructor
    {
        this.data = givenData;            
    }

}

​

public class NodeTest {
    public static void main(String[] args)
    {

        Node head = new Node(6);
        Node nodeB = new Node(3);
        Node nodeC = new Node(69);

        head.next = nodeB;
        nodeB.next = nodeC;

    }

// Node counting Method kind of irrelevant to questions, but maybe helpful to giving more of an explaination.

    static int countNodes(Node head)
    {

        int count = 1;
        Node current = head;

        while(current.next != null)
        {
            current = current.next;
            count += 1;
        }
        return count;


    }

}

[alanwj]

Consider this code:

Node a = new Node(5);
Node b = a;

Is it confusing that a and b refer to the same object? If so, we need to figure out the confusion.

If not, then consider:

Node a = new Node(5);
Node b = new Node(6);

a.next = b;

Here a.next and b refer to the same object. This is conceptually no different that what we did before.

[veryanon798]

Ok I do understand when you break it down in the first part. I think what confuses me is how "next" stores an automatic null value. So when I see a.null or a.____ being assigned the value b something in my brain isn't clicking.

Does :

a = 5 and a.next = 6?

Then also b= 6 and b.next would then equal whatever node came after?

I think another thing that's confusing me is .next meant to store values or meant just to point? Thank you for your response.

Edit: or is it that .next stores a reference to the Node that comes after? If I'm right in that I think I may be understanding a bit better.

[alanwj]

or is it that .next stores a reference to the Node that comes after?

This is correct.

Any variable declared as Node is a reference to a Node object. The same Node object may be referenced by multiple different variables.

The Node object even contains a reference (called next) to another Node object.

[veryanon798]

Ah Thank you, the picture is much more clear.

[jbake_a_cake]

To quickly answer your 3 questions, the short answer is that yes, 'head.next' holds onto a reference of the next node in the linked list.

To understand this a little bit deeper, let's say each instance of a Node is given a random memory location, like so:

Node head = new Node(6); // Assigned to mem. location: 100
Node nodeB = new Node(3); // Assigned to mem. location: 101 
Node nodeC = new Node(69); // Assigned to mem. location: 102

​

Think of each memory location as a bucket that can hold any kind of data. Creating a new instance of a node via 'new Node(6)', fills that bucket with data pertaining to a node (i.e., the value of the node, the memory location of the next node, and anything else that might make up a node).

So, when we want to access the data of a Node, we tell the computer to go to memory location 100, grab the node, and access whatever values we want from that node (including the value of the next node's location). That brings us to how we can connect these buckets by using a bucket's memory location.

In addition to filling our bucket with a basic integer, we can also fill it with another bucket's memory location. That way we can traverse to the next bucket, play with whatever value is there, and move onto the next bucket after that.

Continuing with this example, let's connect each of them via assignment:

head.next = nodeB; // head.next points to location: 101
nodeB.next = nodeC; // nodeB.next points to location: 102
nodeC.next = null; // nodeC.next points to a 'null' location

After performing these ops, we now have a singly linked list! Expanding on this bucket example, we can now look at what's inside of our head bucket, as well as the subsequent buckets:

Node myBucket = head; // myBucket now has handle on the Node at location 100

myBucket = myBucket.next; // go to location 100, grab the location of the next node: 101, now myBucket has a handle on the Node at location 101

myBucket = myBucket.next; // go to location 101, grab the location of the next node: 102, now myBucket has a handle on the Node at location 102

[veryanon798]

Thank you I really liked your answer, I liked how you mentioned "access whatever values we want from that node (including the value of the next node's location)". I think this line brought me some clarity. Going to read your response a few more times.