Как действует связный список?

Question

[sabn1k]

Немного не понимаю, что именно делает в этот момент код программы.

template<class TYPE>
struct link
{
	TYPE data;
	link* next;
};
template<class TYPE>
class linklist
{
private:
	link<TYPE>* first;
public:
	linklist(){ first = NULL; }
	void additem(TYPE d);
	void display() const;
};
template<class TYPE>
void linklist<TYPE>::additem(TYPE d)
{
	link<TYPE>* newlink = new link<TYPE>;
	newlink->data = d;
	newlink->next = first;
	first = newlink;
}
template<class TYPE>
void linklist<TYPE>::display() const
{
	link<TYPE>* current = first;
	while (current != NULL)
	{
		cout << endl << current->data;
		current = current->next;
	}
}

int main(int argc, char**argv)
{
	setlocale(0, "");
	linklist<double> ld;

	ld.additem(151.3);
	ld.additem(121.3);
	ld.additem(531.3);
	ld.display();

	linklist<char> lch;
	lch.additem('a');
	lch.additem('b');
	lch.additem('c');
	lch.display();
	_getch();
	return 0;
}

А именно, что происходит тут:

template<class TYPE>
void linklist<TYPE>::additem(TYPE d)
{
	link<TYPE>* newlink = new link<TYPE>;
	newlink->data = d;
	newlink->next = first; // вот здесь не пойму, что именно мы записываем в next
	first = newlink; // и здесь не пойму, что именно мы присваиваем first
}
/////////////////////////////////////////////
template<class TYPE>
void linklist<TYPE>::display() const
{
	link<TYPE>* current = first; // что именно мы записываем в current?
	while (current != NULL)
	{
		cout << endl << current->data;  
		current = current->next; // и тут тот же вопрос :/
	}
}

Имеется ввиду, как вообще все это работает? Связный список - это что-то по типу стека?

Answer 1

[Денис Загаевский]

Ответ на все ваши вопросы - указатели. Отвечать в рамках тостера на вопрос, что такое указатели - дело неблагодарное, ИМХО.

Answer 2

[Onito]

краткое описание:
1)в first хранится указатель но вершину списка(first = newlink;) здесь мы создаём новый элемент и сохраняем указатель на него.
2) newlink->next = first; - тут сохраняется предыдущая вершина списка
3) link* current = first; тут мы берём вершину списка и просто копируем в другую переменную
4) current = current->next; - из пункта 2) ясно что тут хранится указатель на предыдущую вершину, другими словами на предыдущий элемент.

Comments

[sabn1k]

Сейчас начал изучать STL и вспомнил этот огромный код связного списка. То есть, получается, что мне не нужно делать велосипед, а лучше создавать списки посредством конструктора list и пользоваться его методами?

[sabn1k]

Или это что-то другое?