0

Below is my code that provides a simple interface to link lists in C. So that it can behave simular to ArrayLists in java.

My question is this:

My code will only work for people who want to have a link list of ints and nothing else.

I understand that they can use the int to hold the address of their data type via pointers.

However, I want something more versatile.

Can I use void* instead of the int in the node struct. Then users can provide int, double, char etc...?

Code:

#include <stdio.h>

#include <stdlib.h>

int AL_appened(int val);
struct Tuple AL_find(int val);
int AL_remove(int val);
int AL_setup();
int AL_len();

typedef struct Node Node;
typedef struct Tuple Tuple;

struct Node{

    int val;

    Node *next;

};

struct Tuple{
    int index;
    int val;
};

Node *root, *curr;


int AL_appened(int val) {
    Node *tmp;
    tmp = (Node *)malloc(sizeof (Node));
    curr->next = tmp;
    tmp->val = val;
    curr = tmp;
    root->val++;
    return 0;

}



struct Tuple AL_find(int val){
    if(root->next) {
     curr = root->next;

        int count = 0;
        while (curr->next){

            if (curr->val == val){
                Tuple r = {count+=1, val};
                return r;
            }
            count++;
            curr = curr->next;

        }
        if (curr->val == val){
            Tuple r = {count+=1, val};
            return r;
        }
    }
        Tuple r = {-1, -1};
        return r;

}



int AL_remove(int val){
    Node *prev;
    prev = (Node *)malloc(sizeof (Node));
    curr = root;
    while (curr->next->val != val){
        prev = curr;
        curr = curr->next;
    }
    if (curr->next->val != val) return -1;
        curr->next = curr->next->next;
    root->val--;
    free(curr->next);
    return 1;

}


int AL_setup(){
    root = (Node *)malloc(sizeof(Node));
    root->val = 0;
    root->next = 0;
    curr = root;
    return 0;

}

int AL_len(){
    return root->val;
}

void printAll(){
    curr=root->next;
    while (curr->next != NULL) {
        printf("%d\n",curr->val);
        curr=curr->next;
    }
    printf("%d\n",curr->val);
}

int main(){
    AL_setup(); //setup the root, we will use root to keep track of the number of links
    AL_appened(1); // append 1 so it should look like root>1
    AL_appened(2); // append 2 so it should look like root>1>2
    AL_appened(3);
    AL_appened(4);
    printf("%d\n", AL_len()); // print len of list

    Tuple results = AL_find(4); // find 4 in list
    printf("%d %d\n", results.index, results.val); // return the index and the number found

    AL_remove(3);
    Tuple results2 = AL_find(4);
    printf("%d %d\n", results2.index, results2.val);

    results2 = AL_find(4);
    printf("%d %d\n", results2.index, results2.val);
    printAll(); // print entire list
    return 0;
}
4
  • 3
    Doorknob: Just when I've cast my vote for you ... ;) C doesn't have templates, does it? Feb 23, 2014 at 20:15
  • @Doorknob Or impredicative types! But this is C.
    – Sneftel
    Feb 23, 2014 at 20:16
  • @Constantinius Whoops, sorry for ignoring tags :P (also trying to answer C++ things when I have barely any knowledge in it :P)
    – tckmn
    Feb 23, 2014 at 20:16
  • check klib.sourceforge.net as using macros alternative for void*
    – qwr
    Feb 23, 2014 at 20:21

2 Answers 2

4

Well, you could have void* as the value type, but that would require an extra memory allocation per-node. Another approach I've seen is to put only the link in the struct, and have the user declare their own node type (with the link first), and cast to the generic node type. I've even seen linked list libraries put in preprocessor macros, such that DEFINE_LINKED_LIST(Foo) makes a FooList, a FooNode, an appendFoo function, etc. Finally, you could put all the types you think you might want into a union for the value.

Ultimately, there's no especially clean, pretty way of doing this; C is not well-suited to polymorphism. You'll need to decide which imperfect option you like best.

1

The linux programmers had a similar problem, and they came up with a general solution to it. In short, their approach is to define a list_head structure, that is inserted into whatever user structure that needs to be part of a linked list. Since the inclusion is the other way around as in your code, the linked list implementation 1. does not constrict the user structure in any way, and 2. allows a user structure to be a member of more than one linked lists. This is really a very flexible design, and as it's GPL'd, you can use it in any GPL'd code.

(This answer to another question on SO points to a user space adaption of the kernel lists. I have not tested it myself, so use it at your own risk. It looks sane, though.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.