Plan

  • Structure type / registration – revision
  • Simple linked lists
  • Doubly linked lists
  • Stacks
  • Queues

struct type

  • revision from laboratory 3

Simple linked lists

(LIFO, simple declaration)

Reading a simple linked list

void readSimpleList(listaSimpla& L) {
    unsigned int nrElements;
    cout<<"Number of elements: ";
    cin>>nrElements;
    tipDate element;
    L=NULL; listaSimpla p;
    for (unsigned int i=1; i<=nrElements; i++)
    {
        cout<<"Give the "<<i<<"-th element: ";
        cin>>element; p=new nod; p->info=element;
        p->urm=L;L=p;
    }
}

Displaying a simple linked list

void displatSimpleList(listaSimpla L) {
    listaSimpla p; p=L;
    while (p!=NULL) {
        cout<<p->info<<", ";
        p=p->urm;
    }
    cout<<"\n";
}

An example program

int main() {
    cout<<"List program\n\n"; listaSimpla L;
    cout<<"Reading:\n"; readSimpleList(L);
    cout<<"Displaying:\n"; displaySimpleList(L);
    return 0; 
}

Doubly linked list

(a structured has been used, the mechanism is FIFO)

#define tipDate int
struct nod {
    tipDate info;
    nod* urm;
    nod* prec;
};

struct listaDubla {
    nod* prim; nod* ultim;
    unsigned int lungime;
};

List initializing

void initialiseDoublyList(listaDubla& L)
{
    L.lungime=0;
    L.prim=NULL; L.ultim=NULL;
}

Adding an element to the list

void addToDoublyListElement(listaDubla& L, tipDate element) {
    if (L.lungime==0) {
        L.prim=new nod; L.prim->info=element;
        L.prim->urm=NULL; L.prim->prec=NULL;
        L.ultim=L.prim; L.lungime++; 
    }
    else {
        nod* p; p=new nod;
        p->info=element; p->urm=NULL;
        p->prec=L.ultim; L.lungime++;
        L.ultim->urm=p; L.ultim=p;
    }
}

Reading a doubly linked list

void readDoublyList(listaDubla& L)
{
    unsigned int nrElements;
    cout<<"Number of elements: ";
    cin>>nrElements;
    tipDate element;
    for (unsigned int i=1; i<=nrElements; i++)
    {
        cout<<"Give the "<<i<<"-th element: ";
        cin>>element;
        addToDoublyListElement(L, element);
    }
}

Displaying a doubly linked list

void displayDoublyList(listaDubla L)
{
    nod* p=L.prim;
    while (p!=NULL)
    {
        cout<<p->info<<", ";
        p=p->urm;
    }
    cout<<"\n";
}

Function main() and example program

#include <iostream>
using namespace std;
#define tipDate int
int main()
{
    cout<<"Program with doubly linked list\n\n";
    listaDubla L;
    initialiseDoublyList(L);
    cout<<"Reading:\n";
    readDoublyList(L);
    cout<<"Displaying:\n";
    displayDoublyList(L);
    return 0;
}

Program execution 

Deleting an element

void deleteElement(listaDubla L, unsigned int pozitieElement) { 
// deletes an element on an interior position
    nod* p=L.prim;
    nod* q; nod* r;
    for (unsigned int i=1; i<=elementPosition-1; i++)
        p=p->urm;
    q=p->prec; r=p->urm;
    q->urm=r; r->prec=q;
    delete p;
    L.lungime--;
}

Program execution