[saad.ahmad]

Hi I had a question on how to sort ints in a doubly linked list...and also wanted to know how to include and sort chars in the doubly linked list

 #include<iostream>

template <typename D>
class dll
{
	struct node
	{
		D data;
		node* prev;
		node* next;
		node (D d ,node* p, node* n): data(d),prev(p),next(n) {}
	};
	node* head;
	node* tail;
public:
	dll(): head (NULL), tail (NULL) {}
	template<int N>
	dll(D(&arr) [N]):head(NULL),tail(NULL)
		
		{

			for( int i(0); i != N; ++i)
			push_back(arr[i]);
		}

bool empty() const { return ( !head || !tail ); }

operator bool() const { return !empty(); }

void push_back(D);

void push_front(D);

D pop_back();

D pop_front();
~dll()

	{
	while(head)
	{
		node* temp(head);
		head=head->next;
		delete temp;
		}
	}
};

template <typename D>

void dll<D>::push_back(D data)

{
tail = new node(data, tail, NULL);

if( tail->prev )

	tail->prev->next = tail;

 

if( empty() )

	head = tail;

}

template <typename D>

void dll<D>::push_front(D data)

{
head = new node(data, NULL, head);
if( head->next )
head->next->prev = head;

if( empty() )
	tail = head;

}

template<typename D>

D dll<D>::pop_back()

{

if( empty() )

	throw("dll : list empty");

node* temp(tail);

D data( tail->data );

tail = tail->prev;

 

if( tail )

	tail->next = NULL;

else

	head = NULL;

 

delete temp;

return data;

}

 
template<typename D>

D dll<D>::pop_front()

{

if( empty() )

throw("dll : list empty");

node* temp(head);

D data( head->data );

head = head->next;

 

if( head )

	head->prev = NULL;

else

	tail = NULL;

 

delete temp;

return data;

}

int main()

{

int arr[] = { 4, 6, 8, 32, 19 };

 
dll<int> dlist ( arr );

dlist.push_back( 11 );

dlist.push_front( 100 );

while( dlist )

std::cout << dlist.pop_back() << " ";

}

[bodom658]

well, you can sort the list like you would a singly linked list, just remember to set the prev pointer to the correct address.

As for including characters, you need to decide how you want to incorporate them into being sorted. (i'd recommend using their ACII values perhaps... if you are keeping it to characters and ints.)

This post has been edited by bodom658: 20 October 2009 - 01:37 AM

[baavgai]

That's a lot of messing about with pointers, though. I'd be tempted to make data a pointer and not deal with annoyance.

e.g.

struct Node {
	D *data;
	Node *prev, *next;
	
	Node(D d , Node *p, Node *n) : prev(p), next(n) {
		data = new D;
		*data = d;
	}
	
	~Node() { delete data; }
	
	void swap(Node &other) {
		D *temp = data;
		data = other.data;
		other.data = temp;
	}
};