Click here to Skip to main content
15,885,366 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hello Group

Can anyone point me to a linked list implementation in c++ with purely class and no structs used. Any links would be greatly appreciated.
I searched around codeproject and I found only implementations with node class as strcuts.

Thanks In aDVAnace
Posted
Comments
nv3 24-Jan-13 6:58am    
Is it an "Intrusive List" class that you are looking for, i.e. a class in which the list pointers are stored in the same object as the payload data? (Some people call them "internal storage" lists). Is that what you mean by "no structs used"?
Philippe Mori 24-Jan-13 9:37am    
Given than in C++ a class is essentially a struct with it default access specifier set to private, an easy answer would be to replace struct keyword with class and add a bunch of public:.
CPallini 24-Jan-13 15:40pm    
Good answer, my virtual 5. However, you don't need to add privete (you may possibly need to do the opposite).
Philippe Mori 24-Jan-13 16:10pm    
Now corrected... My mistake.

You could probably change struct to class very easily. Not sure what you have got against struct's though.
 
Share this answer
 
Comments
kaushik4study 24-Jan-13 14:02pm    
__jhon is right just do what he said. One more thing what the issue with the struct?
How about this to bake your noodle:-
template< class T >
	class CTFLink
	{
	public:	

		//--------------------------------------------------------------------------------
		CTFLink()
		{
			m_pNext = 0;
		}

		//--------------------------------------------------------------------------------
		CTFLink( T _t ) : m_Item( _t )
		{
			m_pNext = 0;
		}
		
		//--------------------------------------------------------------------------------
		//A slow but simple append implementation.
		//Appending to any item in the list always appends at the end.
		void Append( CTFLink< T >* ptNext )
		{
			CTFLink< T >* pEnd = this;

			while( pEnd->m_pNext != 0 )
			{
				pEnd = pEnd->m_pNext;
			}

			pEnd->m_pNext = ptNext;
		}

		//--------------------------------------------------------------------------------
		T& Item()
		{
			return m_Item;
		}

		T m_Item;

	protected:

		CTFLink< T >* m_pNext;
		
	};

It can be used by deriving a class from it, which instantly becomes a linked list of itself.

class CMyThing : public CTFLink< CMyThing >
{
...


Not perhaps the recommended way of doing things but it's fun and possibly the worlds simplest generic linked list. Can you come up with a simpler one?
 
Share this answer
 
v3
Comments
Philippe Mori 24-Jan-13 9:49am    
You don't have any method for accessing next item... and you should probably keep a pointer to your last item to make appending fast on large list.
Matthew Faithfull 24-Jan-13 14:13pm    
Accessing the next item is done by ->m_pNext which is always accessible from the current item becuase it's derived from TFLink<>.
The appending speed problem can be solved by always appending inserting at the head of the list but then you'd need to know externally which was your head item. In the scenario I sourced this from I don't always know that but I do always know some item in the list hence the inefficient solution.
It is to some degree 'joke' code but there are edge case scenarios where it can be useful. Consider the situation for example where you have no heap but you want to form an ordered traversable list during static initialization ( which occurs in essentially random order )
I certainly wouldn't recommend this for everyday use but it is a Linked List in C++ as the OP requested :-)
XML
#include <iostream>

template <class T>
struct Node
{
  T data;
  Node * next;
};

template <class T>
class LinkedList
{
public:
  LinkedList() : head(NULL), size(0) {};
  ~LinkedList() { destroyList(); };
  bool addNode(T data);
  bool deleteNode(T data);
  Node<T> * searchNode(T data);
  void printList();
  void reverseList();
  void sortList();
private:
  Node<T> * head;
  int size;
  void destroyList();
  Node<T>* mergeSort(Node<T> * head, int total);
  Node<T>* Merge(Node<T>* left, int lcount, Node<T>* right, int rcount);
  void print(Node<T> * tmp);
};

template <class T>
bool LinkedList<T>::addNode(T data)
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900