How to reverse a linked list (3 different ways)

Introduction

There are couple of ways to reverse a linked list. One of them requires a pointer knowledge and one of them is pretty straight forward. In this article, 3 different ways of reversing a linked list is demonstrated. All the linked list reversing algorithms assume that given linked list is a double linked list.

Technique 1

In this way, a new linked list will be created and all the items of the first linked list will be added to the new linked list in reverse order.

public void ReverseLinkedList (LinkedList linkedList)
{
// ------------------------------------------------------------
// Create a new linked list and add all items of given 
// linked list to the copy linked list in reverse order
// ------------------------------------------------------------

LinkedList copyList = new LinkedList();

// ------------------------------------------------------------
// Start from the latest node
// ------------------------------------------------------------

LinkedListNode start = linkedList.Tail;

// ------------------------------------------------------------
// Traverse until the first node is found
// ------------------------------------------------------------

while (start != null)
{
// ------------------------------------------------------------
// Add item to the new link list
// ------------------------------------------------------------

copyList.Add (start.Item);

start = start.Previous;
}

linkedList = copyList;

// ------------------------------------------------------------
// Thats it!
// ------------------------------------------------------------
} 

This way is probably the most inefficient way among 3. Even though objects of each node is not copied to memory, a new link list node is created for each call to “Add” property. A new link list node means at least 3 pointers (Next, Previous, Item) will be created for each item. This way not only wastes memory, but also wastes processing power.

Technique 2

In this way, we will swap linked list node objects (references to the data). Swapping starts from the first node’s object and first node’s object is swapped with last node’s object. Then, second node’s object is swapped with one before the last node’s object.

Assuming we have N nodes in the link list.

Swap : 1st node’s object with Nth node’s object
Swap : 2nd node’s object with (N-1) node’s object
Swap : 3rd node’s object with (N-2) node’s object

After swapping:

Swapping goes on until the middle of the linked list is found.

public void ReverseLinkedList (LinkedList linkedList)
{

// ------------------------------------------------------------
// Create variables used in the swapping algorithm
// ------------------------------------------------------------

LinkedListNode firstNode; // This node will be the first node in the swapping
LinkedListNode secondNode; // This node will be the second node in the swapping
int numberOfRun; // This variable will be used to determine the number of swapping runs

// ------------------------------------------------------------
// Find the tail of the linked list
// ------------------------------------------------------------

// Assume that our linked list doesn’t have a property to find the tail of it.
// In this case, to find the tail, we need to traverse through each node.
// This variable is used to find the tail of the linked list
LinkedListNode tail = linkedList.Head; // Start from first link list node and go all the way to the end
while (tail.Next != null)
tail = tail.Next;

// ------------------------------------------------------------
// Assign variables
// ------------------------------------------------------------

firstNode = linkedList.Head;
secondNode = tail;
numberOfRun = linkedList.Length / 2; 
// Division will always be integer since the numberOfRun variable is an integer

// ------------------------------------------------------------
// Swap node’s objects
// ------------------------------------------------------------

object tempObject; // This will be used in the swapping 2 objects
for (int i=0; i < numberOfRun; i++)
{
// Swap the objects by using a 3rd temporary variable
tempObject = firstNode.Item;
firstNode.Item = secondNode.Item;
secondNode.Item = tempObject;

// Hop to the next node from the beginning and previous node from the end
firstNode = firstNode.Next;
secondNode = secondNode.Previous;
}

// ------------------------------------------------------------
// Thats it!
// ------------------------------------------------------------

} 

This way of reversing a linked list is pretty optimized and pretty fast. The only overhead of this algorithm is finding the end of the linked list.

Technique 3

In this way, the head of the linked list will point to the last node of the linked list. Also, each node’s “Next” and “Previous” properties need to be swapped too.

Next(red arrow) and Previous(blue arrow) are swapped

public void ReverseLinkedList (LinkedList linkedList)
{
LinkedListNode start = linkedList.Head;
LinkedListNode temp = null;

// ------------------------------------------------------------
// Loop through until null node (next node of the latest node) is found
// ------------------------------------------------------------

while (start != null)
{
// ------------------------------------------------------------
// Swap the “Next” and “Previous” node properties
// ------------------------------------------------------------

temp = start.Next;
start.Next = start.Previous;
start.Previous = temp;

// ------------------------------------------------------------
// Head property needs to point to the latest node
// ------------------------------------------------------------

if (start.Previous == null)
{
linkedList.Head = start;
}

// ------------------------------------------------------------
// Move on to the next node (since we just swapped 
// “Next” and “Previous”
// “Next” is actually the “Previous”
// ------------------------------------------------------------

start = start.Previous;
}

// ------------------------------------------------------------
// Thats it!
// ------------------------------------------------------------
} 

This way of reversing the linked list is performed in a single traverse through the link list. This way is more optimized than the second method. If the reversing requires to keep the link list nodes at their same position. Technique 2 will fail in that case.

Conclusion:

Way 1 is the most straight forward and it can be implemented pretty quickly. However it uses lot’s of system resources. Every time a new node is added, a new memory in the heap will be reserved. Way 2 is pretty professional but if link list doesn’t keep track of the tail of it, link list will be traversed twice. In this case, it will be slower than way 3. Way 3 is the most professional and the fastest one

Original of this article can be found here

You must Sign In to use this message board.

FAQ  Noise Tolerance Very HighHighMediumLowVery Low  Search Messages    Layout Expand All MessagesThread ViewNo Javascript (slow)No Javascript Preview    Per page 102550

Msgs 1 to 2 of 2 (Total in Forum: 2) (Refresh) FirstPrevNext

start.Next = start.Previous; does not compile JayDacca 4:07 28 Sep '08   You can not set start.Next Sign In·View Thread·PermaLink Effect on existing references to list items supercat9 20:28 13 Jul '08   If references exist to list items, creating a new list in the reverse order will leave those references pointing to the old copy. If a garbage-collection-based allocator is used, this will be fine provided those references are only used to access single items. If the existing references are used to enumerate (iterate through) the list, any enumeration in progress when the list is reversed will continue to completion using whatever items existed prior to the reversal operation. It may be desirable for the objects in the list to have a disposed flag, so that objects which are deleted after the list is reversed will not be processed by the enumerator. Swapping object data pointers around, your second suggested approach, will break any existing references to list items. Swapping the 'next' and 'previous' pointers will not prevent existing references from accessing single list items, but could cause severe confusion if existing references are used to enumerate the list. A means of avoiding this would be to have every list item contain a reference to a "direction" flag. The list could then be reversed by simply changing the flag. Enumerators could sample the flag when starting operation, so that they could run to completion even if a list was "reversed" midstream. Sign In·View Thread·PermaLink 5.00/5 (1 vote)

Last Visit: Wednesday, November 19, 2008 2:16 PM     Last Update:Wednesday, November 19, 2008 2:16 PM