CODEWITHSUNDEEP
c++linked-listnodesdoubly-linked-list
ivnM
ivnM

Reputation: 157

Difference between node.prev.next = ... and node =

For the code shown, what exactly would the difference be. From my understanding it should return the current.data value and change the pointer for current to current.next for both. Additionally, can anyone explain the intricacies of current.prev.next = ... and current = ...in general? DoubleLinkedLists, still confuses me a little. Thank you!

public T next() {
    if (!hasNext()){
        throw new NoSuchElementException();
    }
    T data = current.data;
    current = current.next;
    return data;
}

vs

public T next() {
    if(!hasNext()) {
        throw new NoSuchElementException();
    }
    current = current.next;
    return current.prev.data;
}

Upvotes: 1

Views: 2001

Answers (1)

Kingsley
Kingsley

Reputation: 14906

TL;DR ~

If you had a doubly linked list, AND the node has both a previous node and a next node. Saying node->previous->next will indeed get you back to the start point. But if you're at the head or tail of the list the code will crash (because it's trying NULL->next). So don't do that.

Ok, let's forget about data-structures for a minute.

Imagine a "node" is a person, with a t-shirt on. All over that t-shirt is written their name (the data).

In the first case, the people are lined up, all facing the same direction, and the person behind has their arm extended, pointing to the person in front of them. If you're looking for "Joe", you can see whether the current person is "Joe", and whether there is another person to check (who "Joe" is pointing at, or if he's the last person).

This is a single-linked list. Each person only knows about themselves, and the next person. Each person can only "see" the person in front of them, not the person behind. To find out a person's name, you have to ask the person themselves, or the person pointing at them. That is, ask the node.data, or the node->next.data. You can ask the person about who is next, but not who is previous. They don't know who is previous.

Now imagine the people are in a line sideways, pointing at the two people on either side. This is a doubly-linked list. Each person is pointing to a previous person and a next person. Any given person can tell you their name, and the name of the people they point at. It's also possible to move in both directions along the list of people, since they can tell you who they point at in both directions.

This gives us some Code:

structure NodeSingle
{
    String       name;
    NodeSingle   next;
}

and

structure NodeDouble
{
    String       name;
    NodeDouble   previous;
    NodeDouble   next;
}

So we start with an empty (singly linked) list.

Along comes "Bob". Bob has no-one to point to (no next, nor previous), so in data terms we get ["Bob", <>].

Then comes "Sally". For whatever reason we want the list to be sorted alphabetically. So we look at Bob, and decide Sally needs to come next. So we make Bob point at Sally. ["Bob", <Sally>] and ["Sally", <>].

Then comes "Ernst", he has to go between Bob and Sally: ["Bob", <Ernst>] ["Ernst",<Sally>] ["Sally", <>]

In programming terms, this is where the node->next is used. When we added "Sally", we could say ["Bob"]->next = new NodeSingle("Sally").

If [Sally] had to go between [Bob] and [Tina], then obviously ["Bob"]->next = new NodeSingle("Sally", <Tina>)

The doubly linked list is approximately the same, except there's the previous pointer to take care of too.

So when programming, it's possible to reference nodes: node->next->next ... etc. IF the next and prev are defined (and that's a big if), this is used to move along the chain.

Imagine a simple search function:

// Return the node with name = <for_this_name> or NULL
NodeSingle *find(NodeSingle *list, String for_this_name)
{
    while (list != NULL && list->name != for_this_name)
        list = list->next;  // skip to next node
    return list; 
}

Upvotes: 1

Related Questions