Linked List as an ADT in C

Finally finished with this nifty little project I bring it to your curious eyes. Abstract data types are as ominous as the name sounds to most people, but in reality it simply means that the function (implementation) of the data type is hidden from its interface. It is a relatively simple implementation. In object oriented languages we have the all time powerful encapsulation, in which contents of objects are not directly accessible by the programs which use them. The concept is nearly the same with abstract data types.

 

For example, the code:

typedef struct {float x; float y;} point;

 

Would define a structure of type point which contains two floating point values. This is fine and dandy, but what if you don’t want everyone in the world to know that your omnipotent point contains these two floats? Well abstract it! We do this easily by declaring pointers to a point (in this case):

 

Point.h

typedef struct abstractpoint * point;

 

Point.c

typedef struct item * Item;

struct item {float x;};

struct abstractpoint {item x; item y;};

 

We have now just abstracted point to the point that it is no longer directly accessible by programs using it. But how do we access those nifty little floats in our points? Well by the definition of a data type we have to have operations defined for use on the values it contains. Its as simple as defining setters and getters for this case. Thats right, object-oriented concepts in C?! Craziness. But truth. Take a look for yourself.

 

Here is my Abstract Data Type Linked List:

LinkedList.h

typedef struct linkedlist *LinkedList;

 

LinkedList listInit(int maxSize); // Intialize the list with maxSize nodes

void listEmpty(LinkedList); // Make the list empty

int emptyList(LinkedList); // Check to see if the list is empty

void insertNext(LinkedList, int); // insert a new node in the list

int removeNode(LinkedList); // remove the next node in the list

void traverseList(LinkedList); // Starting from the top of the list, print the item of each node

void first(LinkedList); // Move the list pointer to the first node in the list

void last(LinkedList); // Move the list pointer to the last node in the list

 

// Setters and getters for node values

void setNode(LinkedList, int);

int getNode(LinkedList);

LinkedList.c

#include

#include

#include "LinkedList.h"

 

typedef struct listnode* Node; // This structure will define a Node to be a pointer to listnode

struct listnode {int item; Node next;}; // listnode will contain an integer item and a link to the next node

struct linkedlist {Node head; Node *pointer; Node tail;}; // linkedlist ADT will contain three node references. head, a pointer to a node, and a tail

 

int nodeCount;

 

// Create a new node with a reference to a next node and an integer item value

Node new(int item, Node next){

    Node n = malloc(sizeof n); //  Allocate enough space for this new node

    n->item = item; // Set its value to the int item argument

    n->next = next; // Set its pointer to next to itself

    return n;

}

// This function will move the list pointer to the next node in the list

void next(LinkedList list){

    Node n = *list->pointer;

    list->pointer = &n->next;

}

// Return the value of the node to which the pointer points

int getNode(LinkedList list){

    return (*list->pointer)->item;

}

 

// Return the number of nodes in the list

int getNodeCount(){

    return nodeCount;

}

 

// Initialize the list setting the head and tail nodes to null and allowing the pointer to point to the head node

LinkedList listInit(int maxSize){

    LinkedList list = malloc(sizeof *list);

    list->head = NULL;

    list->tail = NULL;

    list->pointer = &list->head;

    

    nodeCount = 0; // Set the initial node count to zero

    return list;

}

 

// Check to see if the list is empty by returning 1 if the list is empty

int emptylist(LinkedList list){

    return list->head == NULL;

}

 

// Insert the next node in the list by simply passing two arguments: the current list and the value to be set

// to the new node

void insertNext(LinkedList list, int item){

    Node n = new(item, NULL); // Create a new node with a NULL pointer value

    

    // Check to see if this new node is the first node inserted by seeing if the head node contains no value

    if(list->head == NULL){

        list->tail = n; // Set the tail equal to the new node

        list->head = list->tail; // Set the head equal to the tail

        nodeCount++; // Increment the node counter

        return;

    }

    

    // If the inserted node is not the head simplly set the tail's next node to node n

    list->tail->next = n;

    list->tail = list->tail->next; // Set the tail to its next node (new node)

    nodeCount++; // Increment the node counter

}

 

// Remove a node from the passed list

int removeNode(LinkedList list){

    Node n; // Reference node n

    n = *list->pointer; // Reference the location of the node of the pointer for n, this is just to return the pointer's value

    *list->pointer = (*list->pointer)->next; // Set the node which the pointer points to to point to the next node in the list, ergo removing it

    nodeCount--; // Decrement the node counter

    return n->item; // Return the integer value of the removed node

}

 

// Move through the passed list by means of the list pointer

void traverseList(LinkedList list){

    list->pointer = &list->head; // Set the list pointer to point to the head node

    int i = 1; // This integer value is just for output clarity

    while(*list->pointer != NULL){

        printf("List[%d]: %d\n", i++, (*list->pointer)->item);

        next(list); // Move along the list to the next node

    }

}

 

void setNode(LinkedList list, int item){

    (*list->pointer)->item = item;

}

 

// Set the list pointer to the first node in the list

void first(LinkedList list){

    list->pointer = &list->head;

}

 

// Set the list pointer to the last node in the list

void last(LinkedList list){

    list->pointer = &list->tail;

}

 

// Deallocate the space used for the list and set the head and tail equal to null

void listEmpty(LinkedList list){

    list->head = NULL;

    list->tail = NULL;

    *list->pointer = NULL;

free(list);

}