doubly linked list

Hello!
I have made a doubly linked list that functions as both a stack and maps a character to a long and have a few questions about the program i wrote.

the list:

List.h

#ifndef LIST_H
#define LIST_H

#include<iostream>

struct node {
	uint8_t m_data;
	uint32_t m_frequency;
	node* next{ nullptr };
	node* prev{ nullptr };

	node(uint8_t data, uint32_t frequency) : m_data{ data }, m_frequency{ frequency } {};

	uint8_t getData() const;
	uint32_t getFrequency() const;
};

class List {
private:
	node* head;
	node* tail;
public:
	List();
	~List();
	void push(uint8_t data, uint32_t frequency);
	void pop();
	void print(); //test func
	void checkLinkage(); //test func
	const node* top();
};

#endif

List.cpp

#include<iostream>
#include"List.h"


/*------------LIST_RELATED_FUNCTIONS------------*/
List::List() {
	head = nullptr;
	tail = nullptr;
}//end of List cunstructor

List::~List() {
	node* temp = tail;
	while (tail != nullptr) {
		tail = tail->prev;
		if (tail != nullptr) tail->next = nullptr;
		delete temp;
		temp = tail;
	}//while tail != nullptr
}//end of List destructor

void List::push(uint8_t data, uint32_t frequency) {
	node* newNode = new node(data, frequency);
	if (head == nullptr) {
		head = newNode;
		tail = newNode;
	}//if head == nullptr
	else {
		newNode->prev = tail;
		tail->next = newNode;
		tail = newNode;
	}//else head != nullptr
}//end of push function

void List::pop() {
	if (tail != nullptr) {
		node* temp = tail;
		tail = tail->prev;
		if (tail != nullptr) tail->next = nullptr;
		delete temp;
	}//if head != nullptr
}//end of pop function
/*------------TEST_FUNCTIONS------------*/
void List::print() {
	node* temp = tail;
	while (temp != nullptr) {
		std::cout << "Data: " << temp->m_data << " Frequency: " << temp->m_frequency << '\n';	//only for test porpuse 
		temp = temp->prev;
	}//while temp != nullptr
}//end of print function

void List::checkLinkage() {
	node* temp = head;																				/*these will be removed when the program is finished*/
	while (temp != nullptr) {
		std::cout << "Data: " << temp->m_data << " Frequency: " << temp->m_frequency << '\n';	//only for test porpuse 
		temp = temp->next;
	}//while temp != nullptr
	temp = tail;
	while (temp != nullptr) {
		std::cout << "Data: " << temp->m_data << " Frequency: " << temp->m_frequency << '\n';	//only for test porpuse 
		temp = temp->prev;
	}//while temp != nullptr
}
/*------------TEST_FUNCTIONS------------*/

const node* List::top() {
	return tail;
}
/*------------LIST_RELATED_FUNCTIONS------------*/

/*------------NODE_RELATED_FUNCTIONS------------*/
uint8_t node::getData() const {
	return m_data;
}

uint32_t node::getFrequency() const {
	return m_frequency;
}
/*------------NODE_RELATED_FUNCTIONS------------*/

main

#include<iostream>
#include"List.h"

int main() {
	List list;
	list.push('a', 1);
	list.push('b', 2);
	list.push('c', 3);
	list.push('d', 4);

	
	const node* topval;
	topval = list.top();																					//or use this to access the data
	std::cout << "Top data: " << topval->m_data << " Top frequency: " << topval->m_frequency << std::endl;
	list.pop();
	topval = list.top();
	std::cout << "Top data: " << topval->m_data << " Top frequency: " << topval->m_frequency << std::endl;

	list.push('d', 4);
	list.checkLinkage();
	std::cout << '\n';

	for (int i{}; i < 3; i++) {
		list.pop();
		list.print();
		std::cout << '\n';
	}

	return 0;
}

UPDATE:
the code has been modified and new functions were added.

new questions:
-is it a good practice to make functions such as top() to access the data inside the nodes?
-in what other ways can i access m_data and m_frequency for the tail in main apart from using the function top() ? perhaps there is a better way of doing so?
-critique on the code will be much appreciated
-if you have any ideas on how to make the code more efficient i would like you to share them here

Last edited on

gunnerfunner (2127)

-did i free the memory correctly in the destructor ?

you could check this yourself by given struct node a vocal dtor:
~node (){std::cout << "goodbye " << m_data << ", " << m_frequency << "\n";}
based on this your list seems to be releasing memory all right but you can add a vocal ctor as well just to be super-sure.

-is the list truely doubly linked ? (did i miss anything)

afraid not as far as I can tell because a doubly linked list means that each node is linked to the node on either side, so that struct node usually has node* members previous and next. See here for an example:
http://www.cplusplus.com/forum/beginner/210745/#msg988500 and there are many others on this forum and elsewhere

is it well written or can be much improved ?

you could consider making node a stand-alone struct,
also node* temp – does it really need to be a data-member of List, could we not just declare one as and when required?
List methods like print() should be const qualified
also consider using the (overloaded) ctor's and member initialization to do a lot of the set-up work for you
avoid using namespace std: http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice

if i were to implement a sorting algorithm that sorts according to the frequency associated with the node what algorithm should i use

here's some info to get you started: http://stackoverflow.com/questions/1717773/which-sorting-algorithm-is-used-by-stls-listsort

globaltourist (201)

i do have it in the code:

struct node {
		uint8_t m_data;
		uint32_t m_frequency;
		node* next{ nullptr };
		node* prev{ nullptr };
	};

if i were to make a function to go through the nodes with both next from head to tail and prev from tail to head will it be enough to test linkage?

you could consider making node a stand-alone struct,

Can you explain why ? Im a self learner and cant understand why .

also node* temp – does it really need to be a data-member of List, could we not just declare one as and when required?

will be redone

List methods like print() should be const qualified

avoid using namespace std:

these were only for testing and will be removed

also consider using the (overloaded) ctor's and member initialization to do a lot of the set-up work for you

I just don't see what more i can automate it is my first attempt at making a doubly linked list

Bdanielz (506)

Since you are using the keyword 'new' that would imply that you should follow the rule of three.
http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three

gunnerfunner (2127)

if i were to make a function to go through the nodes with both next from head to tail and prev from tail to head will it be enough to test linkage

this would be an interesting test, what sort of function do you have in mind – it would have to be something akin to checking : node next's previous is == node || node previous's next is == node, apart from the edge cases but I think you're right, it does seem doubly linked overall

Can you explain why ? Im a self learner and cant understand why

a matter of personal preference really, hence the 'could' instead of the 'should' in the suggestion – I find it easier to keep structs/classes at arm's length as much as possible; you'll find text books with both approaches

… what more i can automate …

one possibility would be to overload the node ctor:

node(const uint8_t data, const uint32_t m_frequency) 
	: m_data(data), m_frequency(frequency){}
//... then lines 21-23 in OP could be collapsed into: 
 	node* newNode = node(data, frequency);

re Bdanielz (502) – I don't think rule of three/five is necessary here as resources are not acquired through the ctor and the list destructor, as checked through the vocal version, shows all resources are being released before exit

globaltourist (201)

@gunnerfunner (1505) thanks for the replay again you made a lot of things clearer for me!

Now when i think about it i should put the struct outside of the class but for a certain reason - i will need to add a function called top() that returns node& to the topmost node so that the data can be accessed and would like to know is there any other way other than moving it outside of the class (public: doesnt count its the same as outside of the class just with encapsulation) ?
Surely i can make two methods called getData() and getFrequency that return the value:
tail->data and tail->frequency but it doesnt seem like a good practice.
NOTE:
my idea about the "bad practice" was to just make the two functions private and be called inside of function top()

About the test i was thinking to just print out the data+frequency only using head->next each time and than doing the same through tail->prev and in theory the two should print the same with the only difference being that tail->prev will print it traversed

Lastly i made some research about merge sorting doubly linked lists and it is pretty hard to understand the algorithm behind it especially why the list is split into two parts (i know the recursive way will be shorter and for me is easier to comprehend but it is less time effective)
is there any resource you would advocate me to read to better understand the mechanics behind it ?

gunnerfunner (2127)

... i should put the struct outside of the class but for a certain reason ...

– yes, that's correct and your reason is more tangible and the only way to access node&
printing backward and forwards would indeed be a simple test to check doubly links
re merge sort google is taking me to the same pages that you're also seeing so it might be better if you pick an approach, make some headway and then post at whatever stage you're at

globaltourist (201)

I am making more research on the merge sort at the moment trying to find an in depth explanation on its implementation inside lists.
If you have time to look at the code i previously posted (it have been edited) it will be much appreciated. I included a top() function, fixed a bug inside of the pop() function, moved the struct outside of the class and implemented the double linkage check and the result clearly shows that the list is doubly linked. Lastly i made temp a local variable inside of the scope its used.

Now i'm looking forward to improving the current code and adding the merge sort function.

dhayden (5798)

Please don't modify earlier posts. It makes reading the comments very hard because the comments may refer to code that you've changed. Post updated code in a new post.

The problem that always seems to occur in doubly linked list implementations is that the author updates the prev pointer but not the next, or the head pointer and not the tail. In your case, pop() doesn't update the head pointer when the list becomes empty.

But a more important question: why is this a doubly linked list at all? Since you only access it with push and pop, why not make it a singly linked list?

globaltourist (201)

Well it is a part of a bigger program that will be a huffman compressor and it is doubly linked because of the following:
1) deletion is O(1) complexity in doubly linked list as opposed to O(n) on singly linked once
2) sorting the list is a lot quicker when the list is doubly linked especially merge sorting the nodes

The problem that always seems to occur in doubly linked list implementations is that the author updates the prev pointer but not the next, or the head pointer and not the tail. In your case, pop() doesn't update the head pointer when the list becomes empty.

Thanks for that part! I thought there was something wrong with pop() i will change the function to check if head should be updated to nullptr once empty i think of doing the following:

void List::pop() {
	if (tail != nullptr) {
		node* temp = tail;
                if(tail == head) head = nullptr;  //this is the only addition
		tail = tail->prev;
		if (tail != nullptr) tail->next = nullptr;
		delete temp;
	}//if head != nullptr
}//end of pop function

Is the change above a suitable solution for updating head once the list is empty?

dhayden (5798)

That will work but I think this is more efficient since it piggybacks on an existing if statement.

void List::pop() {
	if (tail != nullptr) {
		node* temp = tail;
		tail = tail->prev;
		if (tail != nullptr) tail->next = nullptr;
		else head = nullptr; // list is now empty
		delete temp;
	}//if head != nullptr
}//end of pop function

You could simplify the destructor too:

List::~List() {
	while (head) {
		node* next = head->next;
		delete head;
		head = next;
	}
}

1) deletion is O(1) complexity in doubly linked list as opposed to O(n) on singly linked once

That's a bit misleading. It's true if you're deleting random elements, and if you haven't found the element already for some other reason. So it depends on the specific application. Since you're still developing the code, I think it makes sense to leave this as a doubly linked list for now. When the code is done, you could revisit whether it can be converted to a singly linked list.

globaltourist (201)

Thanks for the fast response! When i saw the way you simplified the code i understood that i made things more complicated than they need to be perhaps i will stop that habit with more experience. I will definitely use the changes!

I saw the doubly linked list as a more natural choice for the job i needed it to work as both the std::map<uint8_t,uint32_t> and std::list with the specific merge sort (that i will shortly add to the code) and from what i understood merge sort is faster on doubly linked lists and the main goal is for the code to be as fast and efficient as possible.

Why wont i just use list.h and map.h instead ? Well they are not 100% portable and i need only some of their functionality apart from that i can write the code in a more efficient way since i can make it specialized for the specific task.

globaltourist (201)

P.S:
I would like to know what do you think of the way i implemented the top() function and accessed the data and frequency ?

dhayden (5798)

Well [list.h and map.h] are not 100% portable

Yes they are. They are part of the C++ standard (although the proper names of the files just list and map).

top() seems fine to me. Keep in mind that it can return nullptr so you should check for that case, or make sure that the program logic ensures that a particular call won't return nullptr.

globaltourist (201)

Yes they are. They are part of the C++ standard (although the proper names of the files just list and map).

If so i tried reinventing the weel. I will use the standard library instead but other than that it can be considered practice.

top() seems fine to me. Keep in mind that it can return nullptr so you should check for that case, or make sure that the program logic ensures that a particular call won't return nullptr.

i will fix this one

TheIdeasMan (6817)

Just be careful when something says that one thing is faster than something else. C++ has several things which alter how quick things are: move semantics, concurrency and cache effects. The only real way to know is to actually test and time some data.

As an example, people think that lists are faster than a vector for some operations, but that is shown to be untrue up to a point.
https://isocpp.org/blog/2014/06/stroustrup-lists

Another example is the comparison between std::vector and std::unordered_map (uses a hash table). In the example code by JLBorges I link to, the find function is faster for the unordered_map , but insertion, sorting and finding altogether were faster for the vector up to about 5 million finds, with the full set being 10 million items.

http://www.cplusplus.com/forum/general/193311/#msg930382

As dhayden is saying, it depends on the specific application and it's data. Is the data going to be fairly static, or will there be lots of insertions? The latter has an effect on sorting / finding / container rehashing.

Good Luck !!

Topic archived. No new replies allowed.

C++

Forum

doubly linked list