X1

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// a concrete linked list
// list is a pointer to a struct - containing the head ptr

typedef struct _node *link;    // a link points ot a node

typedef struct _node {
    int value;
    link next;
} node;

// a list is represented by a pointer to a struct which contains
// a pointer to the first node of the list called the "head"
typedef struct _list {
    link head;
} *list;

// print out a list
void showList (list listToPrint) {
    assert(listToPrint!=NULL);
    link current = listToPrint->head;
    while (current!=NULL) {
        printf("[%d] -> ", current->value);
        current = current->next;
    }
    printf("X\n");
}

// inset item at the front of the list
void frontInsert (list l, int item) {
    // Create the node
    link ptrNewNode = malloc(sizeof(node));
    assert(ptrNewNode!=NULL);
    ptrNewNode->value = item;

    // Add the new node
    link oldHead = l->head;
    l->head = ptrNewNode;
    ptrNewNode->next = oldHead;
}

// count the number of items in the list
int numItems (list l) {
    int num = 0;
    link current = l->head;
    while (current!=NULL) {
        current = current->next;
        num++;
    }
    return num;
}

// insert at end of list
void append (list l, int value) {
    // Create the node
    link ptrNewNode = malloc(sizeof(node));
    assert(ptrNewNode!=NULL);
    ptrNewNode->value = value;
    ptrNewNode->next = NULL;

    // Add the node to the end of the list
    link current = l->head;
    if (current == NULL) {
        current = ptrNewNode;
    } else {
        while (current->next!=NULL) {
            current = current->next;
        }
        // Now current points to the last node, just add it
        current->next = ptrNewNode;
    }
}

// find the value stored at position i
// i MUST be a valid position in the list
// dont call this on positions outside the list
int lookup (list l, int position) {
    assert(position>=0);
    link current = l->head;
    int currentPos = 0;
    while (currentPos < position) {
        current = current->next;
        currentPos++;
    }
    return (current->value);
}