Understanding linear linked list

I have some problems understanding the linear linked list data structure. This is how I define a list element:

class Node{
    Object data;
    Node link;

    public Node(Object pData, Node pLink){
        this.data = pData;
        this.link = pLink;
    }
}

To keep it simple we say that a list are linked nodes so we do not need to define a class list (recursion principle).

My problem is that I am really confused in un开发者_如何学编程derstanding how nodes are connected, more precisely the sequence of the nodes when we connect them.

Node n1 = new Node(new Integer(2), null);
Node n2 = new Node(new Integer(1), n1);

What is link? Is it the previous or the next element? Any other suggestions to help me understanding this data structure?

Maybe this drawing will help you to understand.

(Be aware that arrows are references NOT pointers for Java)

The "list" will be a reference to the very first node.

link is a reference to the next Node in the list.

So you would start at the first node in the list, n1, which you'd have a direct reference to. To get the second node in the list, you'd reference n1.link.

To iterate over the list, you would have to have some starting point, such as n1, then repeatedly reference link:

Node n = n1;
while (n != null) {
    println(n.data);
    n = n.link;
}

In a singly-linked list, it's "next".

It looks like Java, even though you haven't tagged it as such. If that's true, consider using generics:

public class Node<T>
{
    T value;
    Node<T> next;
}

I have two suggestions.

First, about the "is this the previous or the next element": it depends on your data structure. Usually it is the next element.

Second, I'd recommend using a pointer or a reference. (And your C++ syntax is incorrect: this is a pointer, and the new operator also returns a pointer. Not sure if you use C++ though, since you didn't specify a lanugage.)

So for example:

class Node {
    Object data;
public:
    Node *next;

    Node (Object pData, Node *pLink) {
        this->data = pData;
        this->next = pLink;
    }
}

This would be a more valid structure. Then you could do:

Node *n3 = new Node(new Integer(2), null);
Node *n2 = new Node(new Integer(1), n1);
Node *n1 = new Node(new Integer(3), n2);

or simply

Node *n1 = new Node(new Integer(3), new Node(new Integer(1), new Node(new Integer(2), NULL)));

Then you could iterate through the list as follows:

for (Node *current = n1; current != NULL; current = current->next)
{
    // do something with the current element
}

I hope this helps!

If you use a modern language, there are already premade linked list structures in C++'s stl, in .NET it's in System.Collections.Generic and I'm sure there is also a Java counterpart.