Reverse double linked list

Quick change of the direction

About

For many algorithms its easier to work with polygons that are counterclockwise.

What algorithm people usually use

The most common algorithm for reversing the double linked list looks like this in java language

Point point = list.first;
Point nextPoint;

do {
nextPoint = point.next;
point.next = point.prev;
point.prev = nextPoint;
point = nextPoint;
} while (point != list.first);

We assume that the linked list is cycling one. Otherwise in the condition have to compare to null

Here is my faster one

Point point = list.first;
Point nextPoint;

do {
nextPoint = point.next;
point.next = point.prev;
point.prev = nextPoint;

if (nextPoint == list.first)
break;

point = nextPoint.next;
nextPoint.next = nextPoint.prev;
nextPoint.prev = point;

} while (point != list.first);

The number of cycles are the same. Also the used variables are the same. But there is one assignment less for every cycle.

So, that's the fastest for now!

Back to main menu