How to reverse a doubly linked list in C++ with half number of iterations of its size

This post briefly describes a performant way to reverse a doubly linked list in C++. The key differentiator is number of iterations required which are simply half of the size of list. Also no new list is instantiated.

The modus operandi is simple. Starting with the head we view each node as having a reflection from the tail end. In case of even sized lists we would have all the nodes from 0 to listSize/2 to have reflections but in case of odd sized lists we would have one node left, which we would term as the median. We just need to swap the nodes on one side of the median with their corresponding reflections on the other side. Median need not be swapped and remains as pivotal node.

Way:

  1. Start with two iterators one as the headCursor and the other as the tailCursor. Initially they are pointing at head and tail respectively.
  2. Loop over to half of the listSize.
  3. Just swap the currentNode which is headCursor->next with the reflectionNode which is tailCursor->prev. Make sure we reassign all the next and prev links properly.
  4. For even sized lists , while you reach position when current index of iteration is equal to listSize/2 – 1, insert a dummy node , prior to swapping of the nodes. This is done just to avoid problems related to reassignment of nodes. Once swapping is done the dummy node is removed and later on deleted.

Here is the complete code for the Doubly linked list template

/*
 * DoublyLinkedList.h
 *
 *  Created on: Jan 16, 2013
 *      Author: hussainp
 */

#ifndef DOUBLYLINKEDLIST_H_
#define DOUBLYLINKEDLIST_H_

#include
#include
using namespace std;

template
class DLinkedList;

template
class DNode {
private:
	E elem;
	DNode* prev;
	DNode* next;
	friend class DLinkedList ;
};

template
class DLinkedList {
public:
	DLinkedList();
	~DLinkedList();
	bool empty() const;
	const E& front() const;
	const E& end() const;
	void addFront(const E&);
	void addEnd(const E&);
	void removeFront();
	void removeEnd();
	void print();
	int size();
	void reverse();
	DNode* nodeAtPos(int);
private:
	DNode* head; // head and tail are merely sentinels
	DNode* tail; // they shouldn't be used to hold data
protected:
	void add(DNode*, const E&);
	void remove(DNode*);
};

template DLinkedList::DLinkedList() :
		head(NULL), tail(NULL) {
	head = new DNode();
	tail = new DNode();

	head->next = tail;
	tail->prev = head;
}

template DLinkedList::~DLinkedList() {
	while (!empty()) {
		removeFront();
	}
	delete head;
	delete tail;
}

template bool DLinkedList::empty() const {
	return (head->next == tail && tail->prev == head);
}

template const E& DLinkedList::front() const {
	return head->next->elem;
}

template const E& DLinkedList::end() const {
	return tail->prev->elem;
}

template void DLinkedList::add(DNode* posNode,
		const E& elem) {
	DNode* newNode = new DNode();
	newNode->elem = elem;

	newNode->next = posNode;
	newNode->prev = posNode->prev;
	posNode->prev->next = posNode->prev = newNode; // assign new node in between

}

template void DLinkedList::remove(DNode* posNode) {
	posNode->prev->next = posNode->next;
	posNode->next->prev = posNode->prev;
	delete posNode;
}

template void DLinkedList::addFront(const E& e) {
	add(head->next, e);
}

template void DLinkedList::addEnd(const E& e) {
	add(tail->prev, e);
}

template void DLinkedList::removeFront() {
	remove(head->next);
}

template void DLinkedList::removeEnd() {
	remove(tail->prev);
}

template void DLinkedList::print() {
	DNode* iterator = head->next;
	cout << endl;
	while (iterator != tail) {
		cout << iterator->elem << "\t"; 		iterator = iterator->next;
	}
	cout << endl;
}
/**
 * Traverses half of the list and swaps a node with another node(here by termed as the reflection node)
 * which lies at a position = listSize - (i +1) for every i.
 * Reassignment of element is not needed, hence a soul saver from
 * the copy constructor thing ( '=' assignment operator stuff).
 */
template void DLinkedList::reverse() {
	int median = 0;
	int listSize = size();
	int counter = 0;

	if (listSize == 1)
		return;

	DNode* tempNode = new DNode();

	/**
	 * A temporary node for swapping a node and its reflection node
	 */
	DNode* dummyNode = new DNode();

	DNode* headCursor = head;
	DNode* tailCursor = tail;

	for (int i = 0; i < listSize / 2; i++) { 		
                headCursor = headCursor->next;
		tailCursor = tailCursor->prev;

		DNode* curNode = headCursor;
		DNode* reflectionNode = tailCursor;

		if (listSize % 2 == 0 && listSize / 2 - 1 == i) {
			/**
			 * insert a dummy node for reflection
			 * for even sized lists at median position
			 */
			curNode->next = dummyNode;
			dummyNode->prev = curNode;

			reflectionNode->prev = dummyNode;
			dummyNode->next = reflectionNode;

		}
		/**
		 * swap the connections from previous and next nodes for current and reflection nodes
		 */

		curNode->prev->next = curNode->next->prev = reflectionNode;

		reflectionNode->prev->next = reflectionNode->next->prev = curNode;

		/**
		 * swapping of the nodes
		 */

		tempNode->prev = curNode->prev;
		tempNode->next = curNode->next;

		curNode->next = reflectionNode->next;
		curNode->prev = reflectionNode->prev;

		reflectionNode->prev = tempNode->prev;
		reflectionNode->next = tempNode->next;

		if (listSize % 2 == 0 && listSize / 2 - 1 == i) {
			/**
			 * remove the dummy node for reflection
			 * for even sized lists from the median
			 */
			reflectionNode->next = curNode;
			curNode->prev = reflectionNode;
		}

		/**
		 * Reassign the cursors to position over the recently swapped nodes
		 */
		tailCursor = curNode;
		headCursor = reflectionNode;
	}

	delete tempNode, dummyNode;
}

template int DLinkedList::size() {
	int count = 0;
	DNode* iterator = head;

	while (iterator->next != tail) {
		count++;
		iterator = iterator->next;
	}
	return count;
}

template DNode* DLinkedList::nodeAtPos(int pos) {
	DNode* iterator = head->next;
	int listSize = size();
	int counter = 0;
	while (counter < pos) { 		
                iterator = iterator->next;
		counter++;
	}

	return iterator;
}
#endif /* DOUBLYLINKEDLIST_H_ */
About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s