Help with inserting into a linked list

Mt570 · #1 26-Sep-2009, 21:26

Hey I have to write a C program that is a linked list of customer data, with various functions.
The function I'm having trouble with is the insertAtIndex function, this function needs to insert a new customer data at the location indicated by the parameter "index". If index is 0 then it should be inserted as the first data in the linked list.

I can add one new element fine but when I try to add another the program crashes. Heres the code:

CPP / C++ / C Code:

int insertAtIndex(char * lastname, char * firstname, int id, float balance, int index)
{

  struct Contact *temp,*r;
    int i;
    temp=head;
    if(head == NULL) 
    { 

      head=r; 
      r->next = NULL; 
    }
    
    else
    {
        for(i=0;i<index;i++)
        temp=temp->next;
    
        if(temp==NULL)
        {
            printf("there are less than %d elements in list\n",index);
            return -1;
        }
        r=(struct Contact*)malloc(sizeof(struct Contact));
            strcpy(r->last_name,lastname);
        strcpy(r->first_name,firstname);
        r->id = id;
        r->balance = balance;
        r->next=temp->next;
        temp->next=r;
    }
        return index;

}

I can post my whole code with the main function if need to be. Any help would be appreciated.

Kimmo · #2 27-Sep-2009, 06:00

I'm not a C person but decided to fool around and came up with something like

CPP / C++ / C Code:

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

struct Contact
{
    char last_name[100];
    char first_name[100];
    int id;
    int balance;
    struct Contact* next;
};

struct Contact *head;

int insertAtIndex(char * lastname, char * firstname, int id, float balance, int index)
{

  struct Contact *temp,*r;
    int i;
    temp=head;
    if(head == NULL) 
    { 

      head=r; 
      r->next = NULL; 
    }
    
    else
    {
        // This has been modified
        for(i=0;i<index;i++)
        {
            temp=temp->next;
            if (temp == NULL)
                break;  // or perhaps even, if temp == null, return -1 ?
        }
    
        if(temp==NULL)
        {
            printf("there are less than %d elements in list\n",index);
            return -1;
        }
        r=(struct Contact*)malloc(sizeof(struct Contact));
            strcpy(r->last_name,lastname);
        strcpy(r->first_name,firstname);
        r->id = id;
        r->balance = balance;
        r->next=temp->next;
        temp->next=r;
    }
        return index;

}

int main()
{
    struct Contact contact1, contact2;

    head=(struct Contact*)malloc(sizeof(struct Contact));
    strcpy(head->last_name, "head");
    strcpy(head->first_name, "head");
    head->id = 100;
    head->balance = 1000;
    head->next = &contact1;
  
    strcpy(contact1.last_name, "Kimmo"),
    strcpy(contact1.first_name, "Mie");
    contact1.id = 1;
    contact1.balance = 100;
    contact1.next = &contact2;
    
    strcpy(contact2.last_name, "Vigdfg");
    strcpy(contact2.first_name, "sdfs");
    contact2.id = 2;
    contact2.balance = 200;
    contact2.next = NULL;
    
    int result = insertAtIndex("Mie", "mies", 3, 300, 1);
    result = insertAtIndex("Mie", "mies", 3, 300, 2);
    result = insertAtIndex("Mie", "mies", 3, 300, 3);
    result = insertAtIndex("Mie", "mies", 3, 300, 4);
    result = insertAtIndex("Mie", "mies", 3, 300, 5);
    result = insertAtIndex("Mie", "mies", 3, 300, 2);
    result = insertAtIndex("Mie", "mies", 3, 300, 7);
    result = insertAtIndex("Mie", "mies", 3, 300, 8);
    result = insertAtIndex("Mie", "mies", 3, 300, 1);
    result = insertAtIndex("Mie", "mies", 3, 300, 1);
    // notice index 100
    result = insertAtIndex("Mie", "mies", 3, 300, 100);
    result = insertAtIndex("Mie", "mies", 3, 300, 1);
    result = insertAtIndex("Mie", "mies", 3, 300, 1);
    result = insertAtIndex("Mie", "mies", 3, 300, 1);
    result = insertAtIndex("Mie", "mies", 3, 300, 14);
    result = insertAtIndex("Mie", "mies", 3, 300, 1);
    result = insertAtIndex("Mie", "mies", 3, 300, 1);
    result = insertAtIndex("Mie", "mies", 3, 300, 1);
    result = insertAtIndex("Mie", "mies", 3, 300, 1);
    result = insertAtIndex("Mie", "mies", 3, 300, 17);
        
    return 0;
}

I don't know what's the problem in your program, but in mine it was your for loop in your function. Your loop tries to dereference a null pointer if given a high enough index (yes, I had to use gdb for this revelation). I added a simple check to see if temp is null to prevent this. I don't know if it works, but it doesn't crash.

Mt570 · #3 28-Sep-2009, 20:04

Ok thanks, I got it working

Mexican Bob · #4 28-Sep-2009, 22:10

Quote:

Originally Posted by Mt570

Ok thanks, I got it working

Just because it works, doesn't mean its right.

For example:

CPP / C++ / C Code:

int insertAtIndex(char * lastname, char * firstname, int id, float balance, int index)

One would expect that these arguments would be passed to a function that creates (constructs) a new node instance, not an "insert node" function.

Something like a "createNode" function that takes the above list of arguments would be what I'd expect from a robust API.

One should think that "insertAt" would take a List instance, a Node instance AND the index, which should be unsigned.

Here is the "right" insertAt function declaration (return type assumes that you want to return the index of the inserted node):

CPP / C++ / C Code:

size_t insertAt(LIST* p_list, NODE* p_node, const size_t zero_based_index);

This implementation DECOUPLES the "list management" from the contents of a node. This is extremely important. It makes your list functions support content of ANY LIST and not just the particular set of data that you're working with for this "kind" of list.

List management functions SHOULD WORK ON NODES. Nothing else. Even list sort functions should ONLY work on NODES. List compare functions should use a node "less than" implementation that is a function pointer used by the list compare/sort routines.

Again, just in case anyone missed it, node data should NOT be a part of any list management function. The next and (when applicable) previous node pointers of a node are not "node data" members. They are a part of the Node type.

CPP / C++ / C Code:

typedef struct tagNode
{
    void*           data;
    struct tagNode* next;
} NODE;

typedef struct tagList
{
    NODE*           head;
} LIST;

Any "list" function that works on node data is probably a bad idea. The notion of a "list" is that it manages nodes. The list may contain a practically unlimited number of nodes that may contain any kind of data. This bears repeating. Nodes may contain any kind of data. Therefore, it would be absolutely foolish to suggest that a "list insert node at some index" function would know anything at all about the data contained in a node.

Yes, there is more work to be done in creating a "generic list" and a "generic node" such that any kind of data may be stored in a node and that the same exact list management functions will work on nodes regardless of what data they contain. However, the obvious benefit is that once it is written, debugged and thoroughly tested, it will ALWAYS WORK for you for the rest of your programming life. You won't ever need to reimplement a new "insertAt" function because somebody decided that they wanted to add another data point to the node(s).

Hopefully, this points out how ridiculous it is to tightly couple data details to generic data storage and manipulation functions. It is incredibly common to find these blended together in a mass of confusion by self-described "programmers" who will fight to the death over the premise that "because it works, it must be right."

MxB

Mt570 · #5 28-Sep-2009, 22:25

This was an assignment for a 200 level programming class, I had to follow the instructions to get full points, so while you're way is better or the right way, I needed to do it this way regardless. But thanks for the insight.

Mexican Bob · #6 28-Sep-2009, 23:32

Quote:

Originally Posted by Mt570

This was an assignment for a 200 level programming class, I had to follow the instructions to get full points, so while you're [sic] way is better or the right way, I needed to do it this way regardless. But thanks for the insight.

You may want to question the value proposition you're getting for your education expenditures if the "instructions" were to implement the function as you've indicated in your code.

You may have heard the cliche that says that practice makes perfect? Let me tell you that you can practice the wrong thing forever any never even modestly approach perfection. Of course, some cliches are absolutely correct. Those who can do... comes to mind

Had the assignment been mine, I would have completed it correctly and incorrectly offering a written justification for the two submissions. Who knows? Perhaps someday the content would have improved?

MxB

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Str_Misaligned in Double Link List	Peter_APIIT	C Programming Language	1	29-Feb-2008 21:50
Airport Log program using 3D linked List : problem reading from file	batrsau	C Programming Language	11	29-Feb-2008 08:44
Linked list: differing results on same code.	Howard_L	C Programming Language	17	29-Jun-2007 00:36
search linked list	itsmecathys	C++ Forum	20	18-Apr-2005 02:34

Help with inserting into a linked list

Re: Help with inserting into a linked list

Re: Help with inserting into a linked list

Re: Help with inserting into a linked list

Re: Help with inserting into a linked list

Re: Help with inserting into a linked list