Lista

[Edzio123]

Oto moje pierwsze podejscie do listy.

Kod: [Zaznacz]

#include
using namespace std;

class List{

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

    Node *head;

    public:
        List(){
            head = NULL;
        }

        ~List(){
            while(head != NULL){
                Node *n = head -> next;
                delete head;
                head = n;
            }
        }

        void add(int value){
            Node *n = new Node;
            n->data = value;
            n->next = head;
            head = n;
        }


        void show_list(){
            Node *temp = head;
                for (int i = 0; i < 2; i++){
                cout << temp -> data << endl;
            }
        }

};

int main(){
    List First;
    First.add(4);
    First.add(5);
    First.show_list();
}

Zastanawiam sie jak mam wyświelic cala listłę. Majac 2 elementy otrzymuje efekt: 5 5.
Czy mogę procić o jakieś wskazówki?

[Paweł Kraszewski]

W show list nie przestawiasz temp na następny element. Dodatkowo FOR nie bardzo pasuje w tej postaci do list.

Lepiej tak:

Kod: [Zaznacz]

void show_list(){
            Node *temp = head;
            while(temp != NULL){
                cout << temp -> data << endl;
                temp = temp->next;
            }
        }

Pamiętaj, że lista w tej postaci działa jak stos (wciskasz nowy na początek), więc wyświetli elementy w kolejności odwrotnej do wstawiania.

[Edzio123]

Wielkie dzięki za wskazanie błędu. Próbuje zmienić funkcję dodawania, tak by mój program wrzucał element na koniec listy:

Kod: [Zaznacz]

void add(int value){
            Node *temp1 = head;    
            while(temp1->next!=NULL) //go to the last node
                temp1 = temp1->next;
        
            Node *temp;
            temp->data = value;
            temp->next = NULL;
            temp1->next = temp;
        }

Jednakże wyskakuje problem z pamięcią. Coś wychodzi poza zakres, ale niestety nie widzę co.
Jeszcze takie techniczne pytanie, czy dla temp i temp1 powwina być dyanmicznie zaalokowana pamięć?

[snajper_8383]

Zmiennej temp przydziel pamięć. W poprzedniej funkcji add to robiłeś, dlaczego tu tego nie robisz? temp jest pustym wskaźnikiem.

[Paweł Kraszewski]

Tak jak pisze kolega Snajper, zgubiłeś malloca.

Dodatkowo takie wstawianie jest O(n). Jak sobie zapamiętasz w klasie wskaźnik na ostatni element i będziesz poprawiał po każdym wstawieniu,  to wstawianie będziesz miał O(1). Dodajesz tylko ten jeden wskaźnik, nie zmieniasz struktury węzła, nie robisz listy podwójnie wiązanej.