Programexempel från Progmet-föreläsning 5, tisdag 18 september 2012
===================================================================

Obs: Ingen föreläsning på torsdag (20 september 2012)!

Planering för idag:

1. Tidskomplexitet!
   Läs: http://basen.oru.se/kurser/progmet/2012-2013-p1/texter/thomas/komplexitet/
   Gör: http://basen.oru.se/kurser/progmet/2012-2013-p1/inlamning-2/

2. Dubbellänkade listor

Om vi hinner (fet chans...):

3. Funktionsbibliotek med generella funktioner,
   generiska datatyper (t ex en generisk lista)

4. C++ och klasser



Dubbellänkade listor
--------------------

Vad?
----

struct talpost {
    double talet;
    struct talpost *previous;
    struct talpost *next;
};



Tips, när vi ändå ritar och definierar structar: "Listhuvud"
------------------------------------------------------------

struct tallista {
    struct talpost *first_in_list;
    struct talpost *last_in_list;
};

....

struct tallista talen; // Bättre abstraktion!
insert_first(&talen, 17.0);



Varför?
-------

Vissa operationer blir enklare!
(stoppa in och ta bort länkar i listan, traversering baklänges...)


Hur?
----

Se exemplet nedan, ListOfDoubles!



Dubbellänkade listor av flyttal: ListOfDoubles
----------------------------------------------

ListOfDoubles -- en dubbellänkad lista med double-flyttal, gjord som en abstrakt datatyp



baklanges.cpp
-------------

// baklanges.cpp -- använder ListOfDoubles

#include <stdlib.h>
#include <stdio.h>
#include "ListOfDoubles.h"

int main(void) {
    ListOfDoubles *talen = LOD_create();

    FILE *tsin = fopen("reella-tal.txt", "r");
    double talet;
    while (fscanf(tsin, "%lf", &talet) != EOF) {
        LOD_insert_first(talen, talet);
    }
    fclose(tsin);

    FILE *tsut = fopen("ny-fil.txt", "w");
    while (LOD_length(talen) > 0) {
        talet = LOD_get_first(talen);
        LOD_remove_first(talen);
        fprintf(tsut, "%f\n", talet);
    }
    fclose(tsut);

    LOD_destroy(talen);

    return 0;
}



ListOfDoubles.h
---------------

// ListOfDoubles.h

#ifndef LISTOFDOUBLES_H
#define LISTOFDOUBLES_H

struct LOD_link {
    double data;
    struct LOD_link *previous;
    struct LOD_link *next;
};

struct ListOfDoubles {
    struct LOD_link *sentinel;
    int length; // Cached for performance
};

typedef struct LOD_link LOD_link;
typedef struct ListOfDoubles ListOfDoubles;

extern ListOfDoubles *LOD_create(void);
extern void LOD_destroy(ListOfDoubles *this_list);
extern int LOD_length(ListOfDoubles *this_list);

extern double LOD_get(ListOfDoubles *this_list, int position);
extern double LOD_get_first(ListOfDoubles *this_list);
extern double LOD_get_last(ListOfDoubles *this_list);

extern int LOD_find(ListOfDoubles *this_list, double wanted);

extern void LOD_insert(ListOfDoubles *this_list, double new_data, int position);
extern void LOD_insert_first(ListOfDoubles *this_list, double new_data);
extern void LOD_insert_last(ListOfDoubles *this_list, double new_data);

extern void LOD_remove(ListOfDoubles *this_list, int position);
extern void LOD_remove_first(ListOfDoubles *this_list);
extern void LOD_remove_last(ListOfDoubles *this_list);

#endif
// #ifndef LISTOFDOUBLES_H



ListOfDoubles.cpp
-----------------

// ListOfDoubles.cpp

#include <stdlib.h>
#include <stdio.h>
#include "ListOfDoubles.h"

static void *safe_malloc(size_t s) {
    void *result = malloc(s);
    if (result == NULL) {
        fprintf(stderr, "ListOfDoubles: Memory full. Couldn't allocate %lu bytes.\n", (unsigned long)s);
        exit(EXIT_FAILURE);
    }
    return result;
}

ListOfDoubles *LOD_create(void) {
    ListOfDoubles *this_list = (ListOfDoubles *) safe_malloc(sizeof(ListOfDoubles));
    LOD_link *sentinel = (LOD_link *) safe_malloc(sizeof(LOD_link));
    sentinel->data = -4711.4711; // Should never be used, but may give debugging hints if it shows up
    sentinel->previous = sentinel;
    sentinel->next = sentinel;
    this_list->sentinel = sentinel;
    this_list->length = 0;
    return this_list;
}

void LOD_destroy(ListOfDoubles *this_list) {
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel->next;
    while (current_link != sentinel) {
        LOD_link *doomed_link = current_link;
        current_link = current_link->next;
        free(doomed_link);
    }
    free(sentinel);
    free(this_list);
}

extern int LOD_length(ListOfDoubles *this_list) {
    return this_list->length;
}

double LOD_get(ListOfDoubles *this_list, int position) {
    int length = LOD_length(this_list);
    if (position < 0 || position >= length) {
        fprintf(stderr, "ListOfDoubles: Couldn't get from position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel->next;
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }
    return current_link->data;
}

extern double LOD_get_first(ListOfDoubles *this_list) {
    return LOD_get(this_list, 0);
}

extern double LOD_get_last(ListOfDoubles *this_list) {
    return LOD_get(this_list, LOD_length(this_list) - 1);
}

int LOD_find(ListOfDoubles *this_list, double wanted) {
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel->next;
    int position = 0;
    while (current_link != sentinel) {
        if (current_link->data == wanted)
            return position;
        ++position;
        current_link = current_link->next;
    }
    return -1;
}

void LOD_insert(ListOfDoubles *this_list, double new_data, int position) {
    int length = LOD_length(this_list);
    if (position < 0 || position > length) {
        fprintf(stderr, "ListOfDoubles: Couldn't insert at position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel;; // Points to the sentinel now, not to the first actual link
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    // We should insert the new link AFTER the "current_link" link

    LOD_link *new_link = (LOD_link *) safe_malloc(sizeof(LOD_link));
    new_link->data = new_data;
    new_link->previous = current_link;
    new_link->next = current_link->next;
    current_link->next->previous = new_link;
    current_link->next = new_link;

    this_list->length++;
}

void LOD_insert_first(ListOfDoubles *this_list, double new_data) {
    LOD_insert(this_list, new_data, 0);
}

void LOD_insert_last(ListOfDoubles *this_list, double new_data) {
    LOD_insert(this_list, new_data, LOD_length(this_list));
}

void LOD_remove(ListOfDoubles *this_list, int position) {
    int length = LOD_length(this_list);
    if (position < 0 || position >= length) {
        fprintf(stderr, "ListOfDoubles: Couldn't remove position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel->next; // Points to the first actual link now!
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    LOD_link *doomed_link = current_link;
    current_link->previous->next = current_link->next;
    current_link->next->previous = current_link->previous;

    free(doomed_link);

    this_list->length--;
}

void LOD_remove_first(ListOfDoubles *this_list) {
    LOD_remove(this_list, 0);
}

void LOD_remove_last(ListOfDoubles *this_list) {
    LOD_remove(this_list, LOD_length(this_list) - 1);
}



En alternativ implementation av t ex LOD_remove_first och LOD_remove_last
-------------------------------------------------------------------------

Ur ListOfDoubles.h:

#define LOD_remove_first(l)     LOD_remove((l), 0)
#define LOD_remove_last(l)      LOD_remove((l), LOD_length(l) - 1)



Traversering = "gå igenom listan"
------------

Som enkellänkad -- men man kan gå baklänges också!

Men: Om man har en sentinel, så är det inte:

    while (current_link != NULL) { ...

utan:

    while (current_link != sentinel) { ...



En speciell sorts traversering: upprensning (men: skräpsamling!)
-------------------------------------------

Som enkellänkad



En annan sorts traversering: Sökning (ur unique-1.cpp)
------------------------------------

Som enkellänkad

Liten optimering: Om man ska gå till en viss position i listan,
och den är i bakre halvan av listan,
så går det snabbare om man börjar i slutet och går bakåt.



Insättning först, sist och i mitten
-----------------------------------

Med cirkulär lista och sentinel blir alla lika!

    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel;; // Points to the sentinel now, not to the first actual link
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    // We should insert the new link AFTER the "current_link" link

    LOD_link *new_link = (LOD_link *) safe_malloc(sizeof(LOD_link));
    new_link->data = new_data;
    new_link->previous = current_link;
    new_link->next = current_link->next;
    current_link->next->previous = new_link;
    current_link->next = new_link;

    this_list->length++;



Borttagning
-----------

    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel->next; // Points to the first actual link now!
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    LOD_link *doomed_link = current_link;
    current_link->previous->next = current_link->next;
    current_link->next->previous = current_link->previous;

    free(doomed_link);

    this_list->length--;



Sökning i sorterad
------------------

Inte så intressant. Det finns bättre datastrukturer för sorterade data.



Insättning sorterad
-------------------

Inte så intressant. Det finns bättre datastrukturer för sorterade data.



Generella behållare och funktioner, på olika sätt och i olika språk
-------------------------------------------------------------------

Metod 1: typedef i C (eller makron)
Metod 2: void* i C
Metod 3: Templates i C++ (och Java, och C#...)
Metod 4: Använd den färdiga std::list från standardbiblioteket



Metod 1: typedef i C (eller makron)
-----------------------------------

cmax1.cpp
---------

// cmax1.cpp -- max-funktionen i C

#include <stdio.h>

int max_int(int tal1, int tal2) {
    if (tal1 > tal2)
        return tal1;
    else
        return tal2;
}

double max_double(double tal1, double tal2) {
    if (tal1 > tal2)
        return tal1;
    else
        return tal2;
}

int main(void) {
    int a, b;
    printf("Ange heltalet a: ");
    scanf("%d", &a);
    printf("Ange heltalet b: ");
    scanf("%d", &b);
    printf("Största heltalet var: %d\n", max_int(a, b));

    double x, y;
    printf("Ange reella talet x: ");
    scanf("%lf", &x);
    printf("Ange reella talet y: ");
    scanf("%lf", &y);
    printf("Största rellea talet var: %f\n", max_double(x, y));

    return 0;
}



cmax2a.cpp
----------

// cmax2a.cpp -- max-funktionen i C, som generisk funktion

#include <stdio.h>

typedef int MAX_DATATYP;

MAX_DATATYP max(MAX_DATATYP tal1, MAX_DATATYP tal2) {
    if (tal1 > tal2)
        return tal1;
    else
        return tal2;
}

int main(void) {
    int a, b;
    printf("Ange heltalet a: ");
    scanf("%d", &a);
    printf("Ange heltalet b: ");
    scanf("%d", &b);
    printf("Största heltalet var: %d\n", max(a, b));

    return 0;
}



cmax2b.cpp
----------

// cmax2b.cpp -- max-funktionen i C, som generisk funktion

#include <stdio.h>

typedef double MAX_DATATYP;

MAX_DATATYP max(MAX_DATATYP tal1, MAX_DATATYP tal2) {
    if (tal1 > tal2)
        return tal1;
    else
        return tal2;
}

int main(void) {
    double x, y;
    printf("Ange reella talet x: ");
    scanf("%lf", &x);
    printf("Ange reella talet y: ");
    scanf("%lf", &y);
    printf("Största rellea talet var: %f\n", max(x, y));

    return 0;
}

(och sen ska vi titta på paketet GenericList version 1...)



Metod 2: void* i C
------------------

(vänta till paketet GenericList version 2...)



Metod 3: Templates i C++ (och Java, och C#...)
----------------------------------------------

cppmax.cpp
----------

// cppmax.cpp -- max-funktionen i C++

#include <stdio.h>

template <typename T> T max(T tal1, T tal2) {
    if (tal1 > tal2)
        return tal1;
    else
        return tal2;
}

int main(void) {
    int a, b;
    printf("Ange heltalet a: ");
    scanf("%d", &a);
    printf("Ange heltalet b: ");
    scanf("%d", &b);
    printf("Största heltalet var: %d\n", max(a, b));

    double x, y;
    printf("Ange reella talet x: ");
    scanf("%lf", &x);
    printf("Ange reella talet y: ");
    scanf("%lf", &y);
    printf("Största rellea talet var: %f\n", max(x, y));

    return 0;
}

(och sen ska vi titta på paketet GenericList version 3...)



En generisk lista i C (och C++) - typ 1, med typedef
----------------------------------------------------

Precis som ListOfDoubles, men byt ut alla "double" mot "GL_DATA_TYPE",
och typedef:a den till vad det nu är för sorts data man vill stoppa in i listan...



GenericList1.h
--------------

// GenericList1.h

#ifndef GENERIC_LIST_H
#define GENERIC_LIST_H

typedef double GL_DATA_TYPE;

struct GL_link {
    GL_DATA_TYPE data;
    struct GL_link *previous;
    struct GL_link *next;
};

struct GenericList1 {
    struct GL_link *sentinel;
    int length; // Cached for performance
};

typedef struct GL_link GL_link;
typedef struct GenericList1 GenericList1;

extern GenericList1 *GL_create(void);
extern void GL_destroy(GenericList1 *this_list);
extern int GL_length(GenericList1 *this_list);

extern GL_DATA_TYPE GL_get(GenericList1 *this_list, int position);
extern GL_DATA_TYPE GL_get_first(GenericList1 *this_list);
extern GL_DATA_TYPE GL_get_last(GenericList1 *this_list);

extern int GL_find(GenericList1 *this_list, GL_DATA_TYPE wanted);

extern void GL_insert(GenericList1 *this_list, GL_DATA_TYPE new_data, int position);
extern void GL_insert_first(GenericList1 *this_list, GL_DATA_TYPE new_data);
extern void GL_insert_last(GenericList1 *this_list, GL_DATA_TYPE new_data);

extern void GL_remove(GenericList1 *this_list, int position);
extern void GL_remove_first(GenericList1 *this_list);
extern void GL_remove_last(GenericList1 *this_list);

#endif
// #ifndef GENERIC_LIST_H



GenericList1.cpp
----------------

// GenericList1.cpp

#include <stdlib.h>
#include <stdio.h>
#include "GenericList1.h"

static void *safe_malloc(size_t s) {
    void *result = malloc(s);
    if (result == NULL) {
        fprintf(stderr, "GenericList1: Memory full. Couldn't allocate %lu bytes.\n", (unsigned long)s);
        exit(EXIT_FAILURE);
    }
    return result;
}

GenericList1 *GL_create(void) {
    GenericList1 *this_list = (GenericList1 *) safe_malloc(sizeof(GenericList1));
    GL_link *sentinel = (GL_link *) safe_malloc(sizeof(GL_link));
    sentinel->data = -4711.4711; // Should never be used, but may give debugging hints if it shows up
    sentinel->previous = sentinel;
    sentinel->next = sentinel;
    this_list->sentinel = sentinel;
    this_list->length = 0;
    return this_list;
}

void GL_destroy(GenericList1 *this_list) {
    GL_link *sentinel = this_list->sentinel;
    GL_link *current_link = sentinel->next;
    while (current_link != sentinel) {
        GL_link *doomed_link = current_link;
        current_link = current_link->next;
        free(doomed_link);
    }
    free(sentinel);
    free(this_list);
}

extern int GL_length(GenericList1 *this_list) {
    return this_list->length;
}

GL_DATA_TYPE GL_get(GenericList1 *this_list, int position) {
    int length = GL_length(this_list);
    if (position < 0 || position >= length) {
        fprintf(stderr, "GenericList1: Couldn't get from position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    GL_link *sentinel = this_list->sentinel;
    GL_link *current_link = sentinel->next;
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }
    return current_link->data;
}

extern GL_DATA_TYPE GL_get_first(GenericList1 *this_list) {
    return GL_get(this_list, 0);
}

extern GL_DATA_TYPE GL_get_last(GenericList1 *this_list) {
    return GL_get(this_list, GL_length(this_list) - 1);
}

int GL_find(GenericList1 *this_list, GL_DATA_TYPE wanted) {
    GL_link *sentinel = this_list->sentinel;
    GL_link *current_link = sentinel->next;
    int position = 0;
    while (current_link != sentinel) {
        if (current_link->data == wanted)
            return position;
        ++position;
        current_link = current_link->next;
    }
    return -1;
}

void GL_insert(GenericList1 *this_list, GL_DATA_TYPE new_data, int position) {
    int length = GL_length(this_list);
    if (position < 0 || position > length) {
        fprintf(stderr, "GenericList1: Couldn't insert at position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    GL_link *sentinel = this_list->sentinel;
    GL_link *current_link = sentinel;; // Points to the sentinel now, not to the first actual link
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    // We should insert the new link AFTER the "current_link" link

    GL_link *new_link = (GL_link *) safe_malloc(sizeof(GL_link));
    new_link->data = new_data;
    new_link->previous = current_link;
    new_link->next = current_link->next;
    current_link->next->previous = new_link;
    current_link->next = new_link;

    this_list->length++;
}

void GL_insert_first(GenericList1 *this_list, GL_DATA_TYPE new_data) {
    GL_insert(this_list, new_data, 0);
}

void GL_insert_last(GenericList1 *this_list, GL_DATA_TYPE new_data) {
    GL_insert(this_list, new_data, GL_length(this_list));
}

void GL_remove(GenericList1 *this_list, int position) {
    int length = GL_length(this_list);
    if (position < 0 || position >= length) {
        fprintf(stderr, "GenericList1: Couldn't remove position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    GL_link *sentinel = this_list->sentinel;
    GL_link *current_link = sentinel->next; // Points to the first actual link now!
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    GL_link *doomed_link = current_link;
    current_link->previous->next = current_link->next;
    current_link->next->previous = current_link->previous;

    free(doomed_link);

    this_list->length--;
}

void GL_remove_first(GenericList1 *this_list) {
    GL_remove(this_list, 0);
}

void GL_remove_last(GenericList1 *this_list) {
    GL_remove(this_list, GL_length(this_list) - 1);
}



baklanges.cpp
-------------

// baklanges.cpp -- använder GenericList1

#include <stdlib.h>
#include <stdio.h>
#include "GenericList1.h"

int main(void) {
    GenericList1 *talen = GL_create();

    FILE *tsin = fopen("reella-tal.txt", "r");
    GL_DATA_TYPE talet;
    while (fscanf(tsin, "%lf", &talet) != EOF) {
        GL_insert_first(talen, talet);
    }
    fclose(tsin);

    FILE *tsut = fopen("ny-fil.txt", "w");
    while (GL_length(talen) > 0) {
        talet = GL_get_first(talen);
        GL_remove_first(talen);
        fprintf(tsut, "%f\n", talet);
    }
    fclose(tsut);

    GL_destroy(talen);

    return 0;
}



En generisk lista i C (och C++) - typ 2, med void-pekare
--------------------------------------------------------

En void-pekare (void*) kan peka på vilken sorts data som helst,
så låt listan innehålla void-pekare, som pekar på de riktiga dataelementen!



GenericList2.h
--------------

// GenericList2.h

#ifndef GENERIC_LIST_H
#define GENERIC_LIST_H

struct GL_link {
    void *data;
    struct GL_link *previous;
    struct GL_link *next;
};

struct GenericList2 {
    struct GL_link *sentinel;
    int length; // Cached for performance
};

typedef struct GL_link GL_link;
typedef struct GenericList2 GenericList2;

extern GenericList2 *GL_create(void);
extern void GL_destroy(GenericList2 *this_list);
extern int GL_length(GenericList2 *this_list);

extern void *GL_get(GenericList2 *this_list, int position);
extern void *GL_get_first(GenericList2 *this_list);
extern void *GL_get_last(GenericList2 *this_list);

extern int GL_find(GenericList2 *this_list, void *wanted);

extern void GL_insert(GenericList2 *this_list, void *new_data, int position);
extern void GL_insert_first(GenericList2 *this_list, void *new_data);
extern void GL_insert_last(GenericList2 *this_list, void *new_data);

extern void GL_remove(GenericList2 *this_list, int position);
extern void GL_remove_first(GenericList2 *this_list);
extern void GL_remove_last(GenericList2 *this_list);

#endif
// #ifndef GENERIC_LIST_H



GenericList2.cpp
----------------

// GenericList2.cpp

#include <stdlib.h>
#include <stdio.h>
#include "GenericList2.h"

static void *safe_malloc(size_t s) {
    void *result = malloc(s);
    if (result == NULL) {
        fprintf(stderr, "GenericList2: Memory full. Couldn't allocate %lu bytes.\n", (unsigned long)s);
        exit(EXIT_FAILURE);
    }
    return result;
}

GenericList2 *GL_create(void) {
    GenericList2 *this_list = (GenericList2 *) safe_malloc(sizeof(GenericList2));
    GL_link *sentinel = (GL_link *) safe_malloc(sizeof(GL_link));
    sentinel->data = (void*)0xdeadbeef; // Should never be used, but may give debugging hints if it shows up
    sentinel->previous = sentinel;
    sentinel->next = sentinel;
    this_list->sentinel = sentinel;
    this_list->length = 0;
    return this_list;
}

void GL_destroy(GenericList2 *this_list) {
    GL_link *sentinel = this_list->sentinel;
    GL_link *current_link = sentinel->next;
    while (current_link != sentinel) {
        GL_link *doomed_link = current_link;
        current_link = current_link->next;
        free(doomed_link);
    }
    free(sentinel);
    free(this_list);
}

extern int GL_length(GenericList2 *this_list) {
    return this_list->length;
}

void *GL_get(GenericList2 *this_list, int position) {
    int length = GL_length(this_list);
    if (position < 0 || position >= length) {
        fprintf(stderr, "GenericList2: Couldn't get from position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    GL_link *sentinel = this_list->sentinel;
    GL_link *current_link = sentinel->next;
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }
    return current_link->data;
}

extern void *GL_get_first(GenericList2 *this_list) {
    return GL_get(this_list, 0);
}

extern void *GL_get_last(GenericList2 *this_list) {
    return GL_get(this_list, GL_length(this_list) - 1);
}

int GL_find(GenericList2 *this_list, void *wanted) {
    GL_link *sentinel = this_list->sentinel;
    GL_link *current_link = sentinel->next;
    int position = 0;
    while (current_link != sentinel) {
        if (current_link->data == wanted)
            return position;
        ++position;
        current_link = current_link->next;
    }
    return -1;
}

void GL_insert(GenericList2 *this_list, void *new_data, int position) {
    int length = GL_length(this_list);
    if (position < 0 || position > length) {
        fprintf(stderr, "GenericList2: Couldn't insert at position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    GL_link *sentinel = this_list->sentinel;
    GL_link *current_link = sentinel;; // Points to the sentinel now, not to the first actual link
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    // We should insert the new link AFTER the "current_link" link

    GL_link *new_link = (GL_link *) safe_malloc(sizeof(GL_link));
    new_link->data = new_data;
    new_link->previous = current_link;
    new_link->next = current_link->next;
    current_link->next->previous = new_link;
    current_link->next = new_link;

    this_list->length++;
}

void GL_insert_first(GenericList2 *this_list, void *new_data) {
    GL_insert(this_list, new_data, 0);
}

void GL_insert_last(GenericList2 *this_list, void *new_data) {
    GL_insert(this_list, new_data, GL_length(this_list));
}

void GL_remove(GenericList2 *this_list, int position) {
    int length = GL_length(this_list);
    if (position < 0 || position >= length) {
        fprintf(stderr, "GenericList2: Couldn't remove position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    GL_link *sentinel = this_list->sentinel;
    GL_link *current_link = sentinel->next; // Points to the first actual link now!
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    GL_link *doomed_link = current_link;
    current_link->previous->next = current_link->next;
    current_link->next->previous = current_link->previous;

    free(doomed_link);

    this_list->length--;
}

void GL_remove_first(GenericList2 *this_list) {
    GL_remove(this_list, 0);
}

void GL_remove_last(GenericList2 *this_list) {
    GL_remove(this_list, GL_length(this_list) - 1);
}



baklanges.cpp
-------------

// baklanges.c -- använder GenericList2

#include <stdlib.h>
#include <stdio.h>
#include "GenericList2.h"

int main(void) {
    GenericList2 *talen = GL_create();

    FILE *tsin = fopen("reella-tal.txt", "r");
    double talet;
    while (fscanf(tsin, "%lf", &talet) != EOF) {
        double *talpekare = (double *)malloc(sizeof talet);
        *talpekare = talet;
        GL_insert_first(talen, talpekare);
    }
    fclose(tsin);

    FILE *tsut = fopen("ny-fil.txt", "w");
    while (GL_length(talen) > 0) {
        double *talpekare = (double *)GL_get_first(talen);
        double talet = *talpekare;
        free(talpekare);
        GL_remove_first(talen);
        fprintf(tsut, "%f\n", talet);
    }
    fclose(tsut);

    GL_destroy(talen);

    return 0;
}