CODEWITHSUNDEEP
data-structureslinked-list
Jumanazar Said
Jumanazar Said

Reputation: 131

what does x.next.prev mean in linked lists (data structures)?

I understand that x.next is the next element to x, and x.prev is the previous element to x. But what does x.next.prev or x.prev.next mean?

I hope there are knowledgeable people here who have stackoverflow of knowledge :-)). Thank you.

Upvotes: 1

Views: 10562

Answers (2)

starikoff
starikoff

Reputation: 1660

These forms make sense e.g. in adding and removing nodes of doubly linked lists, to save some wording.

Assume you have a doubly linked list like this:

Assume you are writing code that removes the node B from it. For that, you first make the "back" pointer of C point to A instead of B. It would be

C.prev = A

To achieve this:

If you only had a handle of B in your code, you would first find those A and C and then do the same:

C = B.next
A = B.prev
C.prev = A

Or, without the temporary variables:

B.next.prev = B.prev

This is essentially your x.next.prev. When later changing the forward pointer of A to point from B to C, you would write B.prev.next = B.next, which contains your second form x.prev.next.

For doubly linked lists, this is useful not only in removing, but also adding new nodes. Check out more pseudocode for that here.

Also note that in the situation in the diagram above the "invariant" B.next.prev == B does not hold. You can meet code that has to deal with this condition violation, for example, in lock-free algorithms. There, when reading x.next.prev you aren't sure that it is the same as x and have to deal with the situation when it's not.

Upvotes: 3

user3614225
user3614225

Reputation: 31

"x.next" refers to the next node in the linked list. This node (like all of the nodes in the list) has a "next" and a "previous" pointer. The "previous" pointer of this node refers to the original node.

So x.next.previous refers to the current node, as long as "x.next" is non-null.

Likewise, x.prev.next refers to the current node, as long as "x.prev" is non-null.

Upvotes: 3

Related Questions