Sign in to follow this  

Generic linked list node class, need some advice...

Recommended Posts

I guys, i have some questions regarding the design of my node class for a linked list or stack or whatever...

Let's show me some code, then i'll explain:

//-----------------------------------------------------------------------------
// Linked list node class
//-----------------------------------------------------------------------------
template <class T> class LinkedListNode {
public:
	LinkedListNode(){prev = next = NULL;}
private:
	T item;
	LinkedListNode<T> *prev, *next;
public:
	T GetItem(){return item;}
	void SetItem(T it){item = it;}

	LinkedListNode<T> *Prev(){return prev;}
	LinkedListNode<T> *Next(){return next;}
};

 

That method is fine, but waste time in GetItem()/SetItem(), so, i could add those 2 methods, ie:

	T* GetItemPtr(){return &item;}
	void SetItemPtr(T *it){item = *it;}

But that's ugly, and even if i use only one set of GetItem()/SetItem(): ie replace previous code with:

	T* GetItem(){return &item;}
	void SetItem(T *it){item = *it;}

	or
	
	T& GetItem(){return item;}
	void SetItem(T &it){item = it;}

it seem each methods has his pros and cons. What's worst is that you can't use more than one set or the compiler will cry...

 

Also, if the object T is not a class, but a simple variable (an int for example), it dosen't have a constructor, and im not sure if:

ZeroMemory(&item, sizeof(item));

will work on any kind of data (especially classes).

Any advice?

 

Share this post


Link to post
Share on other sites

Get/Set methods are a code smell. Just make 'item' public.

ZeroMemory(x,y) is a windows-specific macro for memset(x, 0, y) -- Seeing that it's microsoft-specific, you should generally use memset instead of ZeroMemory... but... no, it is not safe to memset every class to zero. You generally shouldn't do that in C++.

This class could be as simple as:

template<class T> struct LinkedListNode
{
	T item;
	LinkedListNode<T> *prev=0, *next=0;
};

 

Share this post


Link to post
Share on other sites
4 minutes ago, Hodgman said:

but... no, it is not safe to memset every class to zero. You generally shouldn't do that in C++.

 

yea that's my problem, how do i cope with this? I mean, i cannot in advance since T could be anything...

4 minutes ago, Hodgman said:

Get/Set methods are a code smell. Just make 'item' public.

That's a good point.

Edited by Vortez

Share this post


Link to post
Share on other sites
36 minutes ago, Hodgman said:

This class could be as simple as: <quote>

Yeah but that way leave the node's data uninitialized, and a constructor/destructor allow, for example, a c string allocation/deallocation

wich would be risky if T is a pointer (to a c string or whatever) uninitialized.

Maybe im shooting for the impossible "etopia", something that just can't happen without a compromise? I know i tend to be a little (lot) perfectionist since a few years, it's like i know to many way to do the same things, and im never sure which one to use...

 

Here's my whole code, just for fun...

 

#pragma once
//----------------------------------------------------------------------//
#include <Windows.h>
#include <stdio.h>
//----------------------------------------------------------------------//

template <class T> class LinkedList;

//-----------------------------------------------------------------------------
// Linked list node class
//-----------------------------------------------------------------------------
template <class T> class LinkedListNode {
public:
	LinkedListNode(){prev = next = NULL;}
private:
	T item;
	LinkedListNode<T> *prev, *next;
public:
	friend class LinkedList<T>;

	T& GetItem(){return item;}
	T* GetItemPtr(){return &item;}
	
	void SetItem(T& it){item = it;}
	void SetItemPtr(T* it){item = *it;}

	LinkedListNode<T> *Prev(){return prev;}
	LinkedListNode<T> *Next(){return next;}
};

//-----------------------------------------------------------------------------
// Linked list class
//-----------------------------------------------------------------------------
template <class T> class LinkedList {
public:
	LinkedList();
	~LinkedList();
public:
	typedef LinkedListNode<T> NODE;
private:
	int   NodesCount;
	NODE *head, *tail;
private:
	void  Initialize();
	bool  IndexInRange(int index);
	bool  IndexOutOfBounds(int index);
private:
	bool  IsHead(NODE* n);
	bool  IsTail(NODE* n);
public:
	int   GetSize();
	bool  IsEmpty();

	NODE* GetNode(int index);
	NODE* GetFirstNode();
	NODE* GetLastNode();
	
	bool  NodeExist(NODE* n);
	int   FindNode(NODE* n);

	T*    GetItem(int index);
	bool  SetItem(int index, T& item);

	int   FindItem(T& item);
	bool  ItemExist(T& item);

	NODE* Push(T& item);
	NODE* Insert(int index, T& item);
	bool  Delete(int index);
	bool  Pop();
	void  Clear();
};

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//-----------------------------------------------------------------------------
// Constructor...
//-----------------------------------------------------------------------------
template <class T> LinkedList<T>::LinkedList()
{
	Initialize();
}

//-----------------------------------------------------------------------------
// Destructor...
//-----------------------------------------------------------------------------
template <class T> LinkedList<T>::~LinkedList()
{
	Clear();
}

//-----------------------------------------------------------------------------
// Initialise the list
//-----------------------------------------------------------------------------
template <class T> void LinkedList<T>::Initialize()
{
	head = NULL;
	tail = NULL;
	NodesCount = 0;
}

//-----------------------------------------------------------------------------
// Return true if the index is valid
//-----------------------------------------------------------------------------
template <class T> bool LinkedList<T>::IndexInRange(int index)
{
	return index >= 0 && index < NodesCount;
}

//-----------------------------------------------------------------------------
// Return true if the index is valid
//-----------------------------------------------------------------------------
template <class T> bool LinkedList<T>::IndexOutOfBounds(int index)
{
	return index < 0 || index > NodesCount;
}

//-----------------------------------------------------------------------------
// Return true if the list is empty
//-----------------------------------------------------------------------------
template <class T> bool LinkedList<T>::IsEmpty()
{
	return NodesCount == 0;
}

//-----------------------------------------------------------------------------
// Return the number of nodes in the list
//-----------------------------------------------------------------------------
template <class T> int LinkedList<T>::GetSize()
{
	return NodesCount;
}

//-----------------------------------------------------------------------------
// Return true if the given pointer is the head node
//-----------------------------------------------------------------------------
template <class T> bool LinkedList<T>::IsHead(NODE* n)
{
	return head == n;
}

//-----------------------------------------------------------------------------
// Return true if the given pointer is the tail node
//-----------------------------------------------------------------------------
template <class T> bool LinkedList<T>::IsTail(NODE* n)
{
	return tail == n;
}

//-----------------------------------------------------------------------------
// Return the node at the given position
//-----------------------------------------------------------------------------
template <class T> LinkedListNode<T>* LinkedList<T>::GetNode(int index)
{
	int i = 0;
	NODE* node = head;
	
	while(node){
	
		if(index == i)
			return node;
		
		node = node->Next();
		i++;	
	}

	return NULL;
}

//-----------------------------------------------------------------------------
// Return the first node of the list
//-----------------------------------------------------------------------------
template <class T> LinkedListNode<T>* LinkedList<T>::GetFirstNode()
{
	return head;
}

//-----------------------------------------------------------------------------
// Return the last node of the list
//-----------------------------------------------------------------------------
template <class T> LinkedListNode<T>* LinkedList<T>::GetLastNode()
{
	return tail;
}

//-----------------------------------------------------------------------------
// Return true if the given node can be found in the list
//-----------------------------------------------------------------------------
template <class T> bool LinkedList<T>::NodeExist(NODE* n)
{
	NODE* node = head;

	while(node){

		if(node == n)
			return true;

		node = node->Next();
	}

	return false;
}

//-----------------------------------------------------------------------------
// 
//-----------------------------------------------------------------------------
template <class T> int LinkedList<T>::FindNode(NODE* n)
{
	int i = 0;
	NODE* node = head;

	while(node){

		if(node == n)
			return i;

		node = node->Next();
		i++;	
	}

	return -1;
}

//-----------------------------------------------------------------------------
// Return the node at given position
//-----------------------------------------------------------------------------
template <class T> T* LinkedList<T>::GetItem(int index)
{
	if(IndexInRange(index)){
		NODE* node = GetNode(index);
		if(node)
			return node->GetItemPtr();
	}

	return NULL;
}

//-----------------------------------------------------------------------------
// 
//-----------------------------------------------------------------------------
template <class T> bool LinkedList<T>::SetItem(int index, T& item)
{
	if(IndexInRange(index)){
		NODE* node = GetNode(index);
		if(node){
			node->SetItem(item);
			return true;
		}
	}

	return false;
}

//-----------------------------------------------------------------------------
// new
//-----------------------------------------------------------------------------
template <class T> int LinkedList<T>::FindItem(T& item)
{
	int i = 0;
	NODE* node = head;
	
	while(node){

		if(node->GetItem() == item)
			return i;

		node = node->Next();
		i++;	
	}

	return -1;
}

//-----------------------------------------------------------------------------
// 
//-----------------------------------------------------------------------------
template <class T> bool LinkedList<T>::ItemExist(T& item)
{
	return FindItem(item) >= 0;
}

//-----------------------------------------------------------------------------
// 
//-----------------------------------------------------------------------------
template <class T> LinkedListNode<T>* LinkedList<T>::Push(T& item)
{
	NODE* new_node = new NODE;
	NodesCount++;

	// No head?
	if(!head){
		head = new_node;
		tail = new_node;
	} else {
		// Update previous and next pointers
		new_node->prev = tail;
		tail->next = new_node;
		// Update the tail
		tail = new_node;
	}

	// Copy the node's data
	new_node->SetItem(item);

	return new_node;
}

//-----------------------------------------------------------------------------
// 
//-----------------------------------------------------------------------------
template <class T> LinkedListNode<T>* LinkedList<T>::Insert(int index, T& item)
{
	if(IndexOutOfBounds(index))
		return NULL;

	// Get a pointer to the node where we want to insert, if any
	NODE* node = GetNode(index);
	if(!node)
		return Push(item);

	// Allocate the new node
	NODE* new_node = new NODE;
	NodesCount++;
	
	// Update new node pointers
	new_node->next = node;
	new_node->prev = node ? node->prev : NULL;
	
	// Create next and previous node pointer
	NODE* prev_node = new_node->prev;
	NODE* next_node = new_node->next;

	// Update next and previous node pointer
	if(prev_node){prev_node->next = new_node;}
	if(next_node){next_node->prev = new_node;}

	// Update head and tail pointers
	if(!new_node->prev){head = new_node;}
	if(!new_node->next){tail = new_node;}

	// Copy the node's data
	new_node->SetItem(item);

	// Return the newly allocated node
	return new_node;
}

//-----------------------------------------------------------------------------
// 
//-----------------------------------------------------------------------------
template <class T> bool LinkedList<T>::Delete(int index)
{
	// Check for index out of bounds exception...
	if(!IndexInRange(index) || IndexOutOfBounds(index))
		return false;

	// Get prev and next nodes pointers
	NODE* node = GetNode(index);
	NODE* prev = node->Prev();
	NODE* next = node->Next();

	// Update prev and next nodes pointers
	if(prev){node->prev->next = next;}
	if(next){node->next->prev = prev;}

	// Update head and tail pointers
	if(IsHead(node)){head = node->next;}
	if(IsTail(node)){tail = node->prev;}

	// Delete the node
	delete node;
	NodesCount--;

	return true;
}

//-----------------------------------------------------------------------------
// Remove the last node of the list
//-----------------------------------------------------------------------------
template <class T> bool LinkedList<T>::Pop()
{
	return Delete(NodesCount - 1);
}

//-----------------------------------------------------------------------------
// Clear the entire list
//-----------------------------------------------------------------------------
template <class T> void LinkedList<T>::Clear()
{
	while(Pop());
}

 

Feel free to critic.

 

Share this post


Link to post
Share on other sites

So boost has a "call_traits" library that solves this for setters and other function parameters.

Essentially, what it does is special case for built in types, pointer types, etc, and assume a large object for all user provided class types. Like boost, you can provide a helper template for the best way to pass T to setters and other functions. Or you can use enable_if, other sfinae mechanisms, or template specialization to achieve the same thing. 

With getters, you kind of need to choose either const T & or T and be consistent because it will effect how the function can be used. I don't see any point in providing a set function if get returns a T &. If you do want a function that just returns a T &, consider making it operator *, and following the interface of std::optional.

Share this post


Link to post
Share on other sites
4 hours ago, Vortez said:

Yeah but that way leave the node's data uninitialized, and a constructor/destructor allow, for example, a c string allocation/deallocation

wich would be risky if T is a pointer (to a c string or whatever) uninitialized.

Instead of allocating a default-initialized node (which is dangerous for primitive types) and then later filling it in like this:

	NODE* new_node = new NODE;
...
	new_node->SetItem(item);

The idomatic thing to do in C++ is to initialize it at the same time as it is allocated like this:

	NODE* new_node = new NODE(item);

In which case the node class would be something like:

template<class T> struct LinkedListNode
{
	LinkedListNode(const T& t) : item(t) {}
	LinkedListNode(T&& t)      : item(t) {}
	T item;
	LinkedListNode<T> *prev=0, *next=0;
};

 

Share this post


Link to post
Share on other sites

Normally the "NODE" class would be completely private to the linked list, so you wouldn't have functions like GetNode/NodeExist/FindNode.

Also, instead of SetItem/GetItem, you can have a single function that returns a reference to an item (which lets the user read or write to it).
e.g. Instead of

bool ok = list.SetItem(42, "Foo");

a more idiomatic interface would be something like:

bool ok = 42 < list.Size();
if( ok )
  list.ItemAt(42) = "Foo";
//or use operators"
if( ok )
  list[42] = "Foo";

 

Also, the normal thing to do in C++ is to try and avoid implementing algorithms such as FindItem inside your container classes. Instead, you implement an iterator type that allows existing algorithms to iterate through your collection themselves, and then re-use those existing algorithms.

e.g. instead of:

int index = list.FindItem("foo");
String result;
if( item >= 0 )
  result = *list.GetItem(index);

you'd use something like:

List<String>::iterator node = std::find( list.Begin(), list.End(), "foo" );
String result;
if( node != list.End() )
  result = *node;

 

Share this post


Link to post
Share on other sites
6 hours ago, Vortez said:

That method is fine, but waste time in GetItem()/SetItem(), so, i could add those 2 methods, ie:


	T* GetItemPtr(){return &item;}
	void SetItemPtr(T *it){item = *it;}

 

As a side-node, nothing prevents you from using your class with a pointer to a type:

 

	LinkedListNode<MyClass*> linked_list;
	// now storing pointers, so access will be fast
	

 

To ensure you deal with the type without pointers, references... have a look at type traits. For example, this page.

Share this post


Link to post
Share on other sites

Just out of curiosity, why the codes windows aren't showing a vertical bar for dragging when the text is more than x number of lines, for example? Or is there a way to do it? The site changed a lot since 3 years ago.

Share this post


Link to post
Share on other sites

Might I recommend you look at the way the C++ standard library does exactly what you're trying to do.  The code is available to you (albiet obfuscated with warts as mandated by the standard, for good reasons) and it's been tested and refined over decades and hundreds of millions of uses, so it's probably worth studying to pick up tips.

Your available C++ standard library implementation does not have uninitialized members, getters, or setters; is fast and efficient; and provides strong exception guarantees. You will find answers to all your questions (except maybe WTF how can anyone read this code?) in the source files on your computer.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this