Реализация однонаправленного шаблонного связанного списка

[MaTBeu]

Если этот список будете использовать только вы, то можно, а если для массового использования - имхо STL рулит.

[Blade]

Для массового понятно, что никто не будет использовать мой список, это все для себя.
А кстати, в Си STL нету =)

[pu4koff]

Сообщение от Blade

И еще есть идея реализовать этот список как DLL, что бы использовать его в программах на Си. Возможно ли это будет сделать и вообще, стоит ли оно того? Проще наверно просто переписать его под Си, но с DLL интереснее =))

В dll класс запихать можно, но в си Вы этот класс врядли сможете использовать. Да и не рекомендуется работать с классом из dll напрямую. Конструкторы/деструкторы вроде как лучше в самой dll вызывать. Шаблонов в си так же нет вроде как.
Только если с dll работать через собственные, так сказать API, функции.
А уже внутри dll пользовать свой список.
т.е. создаёте в dll следующие функции:
int create_list(); // Создаёт список и возвращает его идентификатор (идентификатор, чтобы можно было несколько списков пользовать одновременно)
void push_back(int list_id, void *new_item); // Добавить элемент new_id в список list_id
и т.д.
Как вот итемы тут правильно передавать я без понятия
А список Ваш наружу не должен выходить. Всё общение исключительно через эти функции
ЗЫ. может есть и более хороший вариант. Сам этим не занимался, так что возможно не прав в чем-то

[ISergeyN]

Как не крути, а шаблон в -> dll? (имхо бред!)

[Night_Light]

Пример реализации итератора. Итераторы намного привычнее и практичнее для перебора элементов коллекции.

class node;
template <typename T> class list
{
private:
class node //Класс node содержит данные списка
    {
friend class list<T>;
        friend class ListIterator;
    private:
 node *next; //Указатель на следующий элемент в списке
        T val; //Данные списка

        node(): next(NULL){}
        ~node(){}
    };

    node *head; //Указатель на начало списка
    int count; //Количество элементов в списке
public:
/** List iterator */
    class ListIterator
    {
/** Current list item */
        node* m_Node;
    public:
 /** Check iterator is valid */
        bool IsValid() const
        {
return m_Node ? true : false;
        }


        /** Iterate to next node */
        void Next()
        {
if ( !IsValid()  )
throw;
            m_Node = m_Node->next;
        }

        /** Get current node value */
        T GetValue() const
        {
if ( !IsValid() )
throw;
            return m_Node->val;
        }


        /** Constructor */
        ListIterator( node* _node ) : m_Node( _node ) {}
    };


    list(): head(NULL), count(0){}
    ~list()
    {
clear(); //Функция освобождает память, используемую для хранения списка
    }
    int getCount() const //Возвращает количество элементов в списке
    {
return count;
    }

    int add(T data)//Добавление элемента в конец списка. Возвращает количество элементов в списке
    {
node *to_add = new node;
        to_add->next=NULL;
        to_add->val=data;
        if(head==NULL) //Если в списке нет элементов
            head=to_add;
        else
        {
            node *current;
            for(current=head;current->next!=0;current=current->next);
            current->next=to_add;
        }
        count++;
        return count;
    }

    int del(int x) //Удаление элемента из списка. Возвращает количество элементов в списке. 
    {			
//Возвращает -1, если произошла ошибка
        if (x>count) return -1;
        node *to_del=head;
        if (x==1) //Если нужно удалить первый элемент
        {
            head=head->next;
            delete to_del;
        }
        else
        {
            node *current=head;
            for(int i=1;i<x-1;i++)
                current=current->next;
            to_del=current->next;
            current->next=current->next->next;
            delete to_del;
        }
        count--;
        return count;
    }

    void clear() //Очистка списка
    {
node *current = head;
        node *to_del = head;
        while(to_del!=NULL)
        {
            current=current->next;
            delete to_del;
            to_del=current;
        }
        head=NULL;
        count=0;
    }

    T getData(int x) const //Возвращает данные из списка.
    {
 node *current;
        for(current=head;x>1;x--)
            current=current->next;
        return current->val;
    }

    /** Get list iterator */
    ListIterator GetIterator() const
    {
 return ListIterator( head );
    }
};


#include <iostream>
#include "mylist.h"
//using namespace std;

struct my_type
{
    int x;
    double y;
};

int main()
{
list<int> my_list; //Пример использования списка с типом int

    my_list.add(-9);	
    for(int i=0;i<5;i++)
my_list.add(i);
    my_list.add(54);

    list<int>::ListIterator iter = my_list.GetIterator();
    while ( iter.IsValid() ) // Проверка на действительность итератора
    {
std::cout << iter.GetValue() << " ";
        iter.Next(); // Переход к следующему элементу
    }

    return 0;
}

Модератор: тег CODE

[ISergeyN]

я б немного по другому сделал итератор.
Примерно так:

//....
template <typename T> class list
{
private:
	class node { .... };
........
public:
	/** List iterator */
	class ListIterator
	{
		/** Current list item */
		node* m_Node;

		ListIterator( node* _node ) : m_Node( _node ) {}
		friend class list<T>;
	public:

		ListIterator& operator ++(){ m_Node = m_Node->next; return *this; }
		ListIterator  operator ++(int) {ListIterator tmp = *this; m_Node = m_Node->next; return tmp;}

		bool operator ==(const ListIterator& other) const { return m_Node == other.m_Node; }
		bool operator !=(const ListIterator& other) const { return m_Node != other.m_Node; }

		/** Get current node value */
		T &operator *() { return m_Node->val; }
		T *operator ->(){ return &m_Node->val; }

		/** Constructor */
		ListIterator() : m_Node(0) {}
	};

	list(): head(0), count(0){}
	list(const list<T> &other):head(0),count(0) { *this = other; }
	//.......
	bool empty() const { return (head == 0); }

	void operator=(const list<T>& other)
	{
		if(&other == this)
			return;

		clear();

		node* nod = other.head;
		while(nod)
		{
			push_back(nod->val);
			nod = nod->next;
		}
	}
	int push_back(T data) { /*int add(T data){....} */}
	//.......
	ListIterator begin() const { return ListIterator( head ); }
	ListIterator end()   const { return ListIterator( 0 );    }
};

class foo
{
public:
	foo(int y = 0):x(y) { }
	//~foo() { cout<<"destroy"<<endl; }
	int  get() { return x; }
	void set(int y) { x = y; }
private:
	int x;
};

int main()
{
	list<int> my_list; //Пример использования списка с типом int

	my_list.push_back(-9); 
	for(int i=0;i<5;i++)
		my_list.push_back(i);
	my_list.push_back(54);

	list<int>::ListIterator it;
	for(it = my_list.begin(); it != my_list.end(); ++it)
		cout<<*it<<endl;

	cout<<endl;

	list<foo> ls;
	ls.push_back(foo(10));
	ls.push_back(foo(15));
	ls.push_back(foo(20));
	ls.push_back(foo(30));

	list<foo>::ListIterator i;
	for(i = ls.begin(); i != ls.end(); ++i)
		cout<< i->get() <<endl;//(*i).get()
	return 0;
}

[Night_Light]

Сообщение от ISergeyN

я б немного по другому сделал итератор.
Примерно так: ...

Впринципе, если афтор не будет юзать STL алгоритмы то ему без разницы кстати, ему их лучше поддерживать )

[Blade]

Сделал новую реализацию. Добавил возможность сохранять список в файл и загружать его оттуда. Интератор все же решил не делать, потому-что мне так привычнее (осталось от Си ) Все равно этим списком вряд ли кто-то, кроме меня, будет пользоваться. Работать этот список может, как я понимаю, с абсолютно любыми типами данных.

Список

/* Реализация однонаправленного линейного шаблонного связанного списка
   28.03.2009 */

#include <fstream>

template <typename T> class list
{
private:
	class node //Класс node содержит данные списка
	{
		friend class list<T>;
	private:
		node *next; //Указатель на следующий элемент в списке
		T val; //Данные списка

		node(): next(NULL){}
		node(T data): next(NULL), val(data){}
		~node(){}
	};

	node *head; //Указатель на начало списка
	int count; //Количество элементов в списке
public:
	list(): head(NULL), count(0){}
	~list()
	{
		clear(); //Функция освобождает память, используемую для хранения списка
	}
	int getCount() const //Возвращает количесвто элементов в списке
	{
		return count;
	}
	
	int add(T data)//Добавление элемента в конец списка. Возвращает количество элементов в списке
	{
		node *to_add = new node(data);
		if(head==NULL) //Если в списке нет элементов
			head=to_add;
		else
		{
			node *current;
			for(current=head;current->next!=0;current=current->next);
			current->next=to_add;
		}
		count++;
		return count;
	}

	int del(int x) //Удаление элемента из списка. Возвращает количество элементов в списке. 
	{			   //Возвращает -1, если произошла ошибка
		if (x>count) return -1;
		node *to_del=head;
		if (x==1) //Если нужно удалить первый элемент
		{
			head=head->next;
			delete to_del;
		}
		else
		{
			node *current=head;
			for(int i=1;i<x-1;i++)
				current=current->next;
			to_del=current->next;
			current->next=current->next->next;
			delete to_del;
		}
		count--;
		return count;
	}
	
	void clear() //Очистка списка
	{
		node *current = head;
		node *to_del = head;
		while(to_del!=NULL)
		{
			current=current->next;
			delete to_del;
			to_del=current;
		}
		head=NULL;
		count=0;
	}
	
	T getData(int x) const //Возвращает данные из списка
	{
		node *current;
		for(current=head;x>1;x--)
			current=current->next;
		return current->val;
	}

	bool saveFile(char *fileName) const//Сохраняет список в файл. Возвращает 1, если произошла ошибка
	{
		ofstream out; //Поток для вывода
		out.open(fileName, ios::out|ios::binary); //Открытие файла
		if(!out)
			return 1;

		out.write((char *)&count, sizeof(int));
		node *current=head;
		for(int i=1;i<=count;i++)
		{
			out.write((char *)&current->val, sizeof(current->val));
			current=current->next;
		}
		out.close();
		return 0;
	}

	bool loadFile(char *fileName) //Загружает список из файла. Вовращает 1, если произошла ошибка
	{
		clear();
		ifstream in; //Поток для ввода
		in.open(fileName, ios::in|ios::binary);
		if(!in)
			return 1;

		in.read((char *)&count, sizeof(int));
		node *current;
		for(int i=1;i<=count;i++)
		{
			node *to_add = new node;
			in.read((char *)&to_add->val, sizeof(to_add->val));
			if(i==1)
			{
				head=to_add;
				current=to_add;
			}
			else
			{
				current->next=to_add;
				current=current->next;
			}
		}
		in.close();
		return 0;	
	}
};

Пример использования

#include <iostream>
#include "list.h"
using namespace std;

struct my_type
{
	int x;
	double y;
	char *str;
};
list<my_type> my_list; //Пример использования списка с типом, определенным пользователем

void print_struct(); //Функция вывода структуры на экран

int main()
{
	for(int i=1;i<=10;i++)
	{
		my_type *point = new my_type;
		point->x=i;
		point->y=i+0.2;
		point->str = "test";
		my_list.add(*point);
	}
	print_struct();

	my_list.del(1);
	my_list.del(3);

	my_list.saveFile("C:\\struct.txt");
	my_list.clear();
	my_list.loadFile("C:\\struct.txt");

	print_struct();

	my_list.clear();
}

void print_struct()
{
	cout << endl << my_list.getCount() << endl;
	for(int i=1;i<=my_list.getCount();i++)
		cout << my_list.getData(i).x << " " << my_list.getData(i).y << " " << my_list.getData(i).str << endl;
}

Это моя первая практика использования файлового ввода/вывода в С++ , поэтому посмотрите, может что-то не совсем правильно?