Sorting Doubly Linked Lists

Sorting ints, and chars in a doubly linked list

Page 1 of 1

2 Replies - 3902 Views - Last Post: 20 October 2009 - 04:58 AM Rate Topic: -----

#1 saad.ahmad  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 09-September 09

Sorting Doubly Linked Lists

Post icon  Posted 19 October 2009 - 11:03 PM

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() << " ";

}




Is This A Good Question/Topic? 0
  • +

Replies To: Sorting Doubly Linked Lists

#2 bodom658  Icon User is offline

  • Villiage Idiom
  • member icon

Reputation: 113
  • View blog
  • Posts: 1,123
  • Joined: 22-February 08

Re: Sorting Doubly Linked Lists

Posted 20 October 2009 - 01:37 AM

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

Was This Post Helpful? 0
  • +
  • -

#3 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5641
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Sorting Doubly Linked Lists

Posted 20 October 2009 - 04:58 AM

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;
	}
};


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1