CODEWITHSUNDEEP
data-structuresrecursion
DarkLeafyGreen
DarkLeafyGreen

Reputation: 70426

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 understanding 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?

Upvotes: 1

Views: 510

Answers (4)

duffymo
duffymo

Reputation: 308858

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;
}

Upvotes: 1

PeterMmm
PeterMmm

Reputation: 24630

Maybe this drawing will help you to understand.

alt text

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

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

Upvotes: 5

Venemo
Venemo

Reputation: 19077

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.

Upvotes: 0

earldouglas
earldouglas

Reputation: 13473

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;
}

Upvotes: 4

Related Questions