LinkedList

[abhisheksainiabhishek]

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!

[dargueta]

It looks like you're going in the right direction. However, you do have a few problems. Your search function doesn't do what I think it's supposed to; you're never comparing the node data to the searchItem pointer, and you can't compare unequivalent types. The node variable in that function isn't declared properly, either.

And by the way, I have no idea what the *list pointer is for either. You technically don't need it.

To remove an item from a linked list, do the following:
1) Search through the list until you find the node before the item you want.
2) Save the next pointer of item you want to delete.
3) Set the next pointer of the current node (the node that comes before the node to delete) to the next pointer of the node to be deleted.
4) Delete the node.

void deleteNthNode(unsigned int n)
{
    Node *curr = head;
    for(unsigned int i = 0; i < n; ++i)
        curr = curr->next;
    //save pointer to node to be deleted
    Node *temp = curr->next;
    //break link by bypassing the node we want to delete
    curr->next = temp->next;
    //delete undesired node
    delete temp;
}

[hounder]

...i dont get it

[dargueta]

I made a diagram and attached it to this post. Let me know if that doesn't clear things up.