связанные списки

[Lusin]

Здравствуйте, в С++ есть такая тема как "связанные списки". Ни как не могу с ней разобраться. не могу понять, что с собой представляет связанный список. помогите пожалуйста понять это или подскажите книгу.

[Lusin]

помогите разбиратся в этом программе. не могу понять зачем так много указателей и для чего они?


class list {
public:
list *head; //начало списка
list *tail; //конец списка
list *next; // следующий элемент
int num; //число для хранения
list() {head=tail=next=0;}
virtual void store(int i)=0;
virtual int retrieve()=0;
};

class queue: public list {
void store(int i);
int retrieve();
};
void queue::store(int i){
list *item;
item = new queue;
if(!item) cout << "ошибка выделения памяти." << endl;
item->num=i;
if(tail)
tail->next=item;
tail=item;
item->next=NULL;
if(!head)
head=tail;
}
int queue ::retrieve() {
int i;
list *p;
if(!head)
cout << "empty" << endl;
i=head->num;
p=head;
head=head->next;
delete p;
return i;
}
class stackublic list {
void store(int i);
int retrieve();
};

void stack ::store(int i) {
list *item;
item =new stack;
if(!item) cout << "ошибка выделения памяти." << endl;
item->num=i;
if(head)
item->next=head;
head=item;
if(!tail)
tail=head;
}
int queue ::retrieve() {
int i;
list *p;
if(!head) cout << "empty" << endl;
i=head->num;
p=head;
head=head->next;
delete p;
return i;
}

[Granus]

Вроде их называют связными списками, ну да ладно. Каждый элемент списка - это совокупность некоторых данных и ссылки на следующий элемент списка (такие списки называются односвязными; если добавить ссылку на предыдущий элемент - то двусвязными). Отсюда и обилие указателей - именно они и представляют собой ссылку на следующий/предыдущий элемент. Банальный пример структуры:

struct list {
  int data;
  list *next;
};

У последнего элемента next должен иметь некое значение, отличимое от других, для обозначения конца списка (логично выбрать 0). В список удобно вставлять новые элементы или удалять их (выполняется за константное время), но неудобно обращаться к элементам по индексу, как в массиве (потому что элемент с заданных индексом еще найти нужно, а в массиве известен его адрес). Одна из основных операций - проход по всему списку от начала до конца. А вообще - читайте книжки, или, например, википедию, там довольно понятно все изложено.

Updated

В вашем примере кода все непросто для изучения, там создается класс списка и различные варианты (стек, очередь) структур данных. Если хотите, могу по-быстрому налопатить простенький односвязный список с объяснением, как все работает, это несложно.

[Lusin]

помогите если не трудно. эта программа слишком сложно для меня.