Singly Linked List

Exercises (1)

Singly linked list: public functions (“methods”)

int list_init(struct list *l);
int list_destroy(struct list *l);
int list_insert(
    struct list *l,
    const char *key, struct point p);
unsigned int list_remove(
    struct list *l,
    const char *key);
unsigned int list_count(
    const struct list *l,
    const char *key);
void list_print(
    const struct list *l);

Exercises (2)

Singly linked list: public data structures

#define KEYLEN 31

struct point {
    int x;
    int y;
};

struct list {
    struct node *first;
};

Exercises (3)

Singly linked list: internals

struct node {
    char key[KEYLEN+1];
    struct point point;

    struct node *next;
};

Exercises (4)

• Implement a linked list as has been sketched above

Exercises (5)

Empty list Result of list_init() First element is NULL

struct list { struct node *first; }; ... l->first = NULL;

Exercises (6)

List containing one element struct node { char key[keylen+1]; struct point point; struct node *next; }; ... strcpy(n->key, key); n->point = point; n->next = NULL;

Exercises (7)

List containing two elements

Exercises (8)

Insertion

• Looking up the position

• Where does "B" belong?

Exercises (9)

Insertion

• New struct node

• malloc(sizeof(struct node))

• Initialization: key, data, next

Exercises (10)

Insertion

• Link new node

• Cut old connection

Exercises (11)

Insertion: done