Click here to Skip to main content
12,451,232 members (53,799 online)
Rate this:
 
Please Sign up or sign in to vote.
See more: C++
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 23-Jan-13 23:39pm
neo29582
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.
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 1

You could probably change struct to class very easily. Not sure what you have got against struct's though.
  Permalink  
Comments
kaushik4study 24-Jan-13 14:02pm
   
__jhon is right just do what he said. One more thing what the issue with the struct?
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 2

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?
  Permalink  
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 :-)
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 4

#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)
  Permalink  

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

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Mobile
Web02 | 2.8.160826.1 | Last Updated 25 Jan 2013
Copyright © CodeProject, 1999-2016
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100