Linked List

Hi,
I have to make a linked list library. I am very new to data structures in C and would very much appreciate if someone could help me out and tell me if I am in the right direction. I am not looking for solution to my assignment but I just want some guidance on Linked Lists as I am still unclear how they work. To make the things little bit clear I will post what I needed to do in my project.

Basically I have to make a linked list with two structure: LinkedList & ListNode. the linked list will make use of dynamically allocated memory (malloc) for the nodes.

Allocating memory is now the responsibility of the linked list library but of the program that uses it (so does the main function do this?).

Prototypes of the functions in the library.....

1)
int CreateLinkedLIst (int *comparator)(void *item1, void *item2), LinkedList **list)

returns pointer to a new linked list. Plus, stores the comparator function, which is used when searching for items.

2)
int Insert (LinkedList *list, void *item)

Insert an item in the list.

3)
int Delete (LinkedList *list)

Delete the current item from the linked list


4) int Search(LinkedList *list, void 8searchItem)

search for some item in the linked list (this function will use the comparator function).

/*********************************************************
My questions: according the function prototypes given, what is the list variable...is it the pointer of the "current" item. Why in CreateLinkedList function the list variable has two pointers, double.


From what I get I have made the function and structuress as follows:

//*****************************************************
typedef struct ListNode {
void *item; //The actual item
struct ListNode *next; //pointer to the next item
} NODE;



typedef struct LinkedList {

struct LinkedList *list; //the current item of the list?????
struct LinkedList *head; //pointing in the beginning of the list
} LINKEDLIST;
//*********************************************



int CreateLinkedList (int (*comparator)(void *item1, void *item2), LinkedList **list)

{

NODE *node;

if(!(node=malloc(sizeof(NODE)))) return NULL;
node->list=list;
node->next=NULL;
return node;



//my attempt of comparator function
while(node)
{
if(comparator(node->list, list)>0) return node;
node=node->next;
}
return NULL;
}




}


//The following code creates and insert a new node after an existing node.
int Insert (LinkedList *list, void *item)

{

NODE *newNode;
newNode=CreateLinkedList(item);
newNode->next = list;
return newNode;

}



int Search (LinkedList *list, void *searchItem)
{

int n=1;


node=&head;
while(node->next!=NULL)
{
if(node->item==list)
break;
else
n++;
node=node->next;
}
return n;



}


Am I using the the variables names properly as given in the function prototypes.
How would I delete the current item form the list as the Delete function has only calls *list variable, I beleive which is the current. But then how does it set the last node to the current one.

I know I have flooded the board with too many questions but this is mainly because of my lack beginning in using the data structures in C.

Please advise me. Thanks!

This is actually an advanced topic. You need to know pointers inside out and you need fundamental knowledge of data structures which are made more difficult with the use of pointers.

First, your Insert and Delete functions should take the exact same arguments. Your Delete function as it is won't work. You need to give the linked list as well as a node or an index to that node.

I can tell you that your function prototypes are completely FUBAR. Most of your functions return an index yet NONE of your functions take an index as input. So ALL 100% of your functions are completely useless.

Also, if you're gonna have a "current item", you need navigation functions like NextIndex and PrevIndex, but it's easier to just pass an index as an argument.

There's more. Your initial prototype:

int CreateLinkedLIst (int (*comparator)(void *item1, void *item2), LinkedList **list);

The way you use it is to have:



myLinkList will then be allocated by CreateLinkedList. The reason for the double indirect reference is so that CreateLinkedList has a pointer not to the linked list, but to your pointer in your main function so that it can update your local variable that points to the linked list. Usually, anything you pass to functions won't get updated locally. By passing a pointer to it, the function CAN update it. You started of with that entity being a pointer, so you end up with a pointer to a pointer.

The problem with the double pointer is that it means your library will allocate the linkedlist. That means you need another function to delete it. This contradicts your assertion that the library is not supposed to do any memory management.

Clear up these issues first.

We'll I'm not sure if you know the theory of it all but here's a quick run-down that I think once you read you may be able to restart this and do it cleaner and better.
Now there's different types of linked lists, but we'll worry about the simplest single chained linked list. Now pointers as I'm sure you've been taught are basically integers that hold a number that represent a location(address, think of it like a mailbox number or street number, or phone number) in the system memory, what's in this location could be anything, which is what makes pointers dangerous and what makes them powerful.
A linked list is simply an object that contains a pointer(address) to another one of the same kind. So imagine a room full of people 50% had blue shirts and 50% had red shirts, everyone with a blue shirt(current object) points(pointer) to the next person(next object) with a blue shirt and everyone with a red to the next person with a red, never twice pointing to the same person. And you wanted to find the last blue person(person pointing to nothing, a.k.a pointer == null), you would do it by going from the first blue shirt person and going to every next person that person is pointing to until you got to the end or the one you wanted to find, that's basically what a linked list is.
Not the best description but there's plenty of resources online you can read up on and check out.
The whole point of them is to have a list of object's or data, that takes up only the space it needs in memory and no more but can be dynamically added to and removed from.

Edit: shouldn't be saying objects in a C forum lol I meant structs oh monday mornings how you turn my brain to mush.