0

The following implementation for insert() function that inserts input into a hash table namely first each of which elements are pointers to a linked list works well.

// takes the number to be inputted. aslo calculates the right position to insert into
void insert(int input)
{
        // calculate which position to insert into
        int index = hash_function(input);

        node* new = malloc(sizeof(node));
        new->val = input;

        // insertion in case of empty list
        if (first[index] == NULL)
        {
                first[index] = new;
                new->next = NULL;
                traverse(index);
                return;
        }

        // if list not empty, insert at front
        else
        {
                // in case number already exists at head of list

                if (first[index]->val == input)
                {
                        traverse(index);
                        return;
                }

                new->next = first[index];
                first[index] = new;
                traverse(index);
                return;
        }

        return;
}

However, what I'm trying to do is to write functions that take, as argument, the head pointer to one of these linked lists to make the code reusable.

So when I try to write the following (code is incomplete yet), it doesn't work

void insert(int n, node* first)
{
        node* new = malloc(sizeof(node));
        new->val = n;

        node* ptr = first;
        node* pred_ptr = NULL;

        // insertion in case of empty list
        if (first == NULL)
        {
                first = new;
                new->next = NULL;
                traverse(first);
                return;
        }

        // insertion at start of list
        if (new->val < first->val)
        {
                new->next = first;
                first = new;
                traverse(first);
                return;
        }

        // insertion in middle of list
        while (ptr->next != NULL)
        {
                if (ptr->val > n)
                {
                        // insert number here
                        new->next = ptr;
                        pred_ptr->next = new;
                        traverse(first);
                        return;
                }
                else
                {
                        pred_ptr = ptr;
                        ptr = ptr->next;
                }
        }

        // insertion at end of list
        if (ptr->next == NULL)
        {
                // number is at absolute end
                if (ptr->val < n)
                {
                        ptr->next = new;
                        new->next = NULL;
                        traverse(first);
                        return;
                }
                // number is just before end
                else
                {
                        new->next = ptr;
                        pred_ptr->next = new;
                        traverse(first);
                        return;
                }
        }
}

Basically, when I try to insert the following values in turn

1, 12, 21, 42

I get 1 and 21 hashed to 1, so they're inserted into the linked list whose head pointer is stored at index 1 in the array. Similarly, 12 and 42 are hashed to 2 and get inserted into the linked list whose head pointer is stored at index 2.

However, if I insert 1 then 21, the lastly inserted value (i.e., 21) is not inserted. Why is that possible?

2
  • Sorry for not noticing that you don't care about sorting your list! I tested your code out with a simple program and it works as expected! You may compile and run this pastebin.com/rwCypXJJ
    – kzidane
    Jul 6 '14 at 19:04
  • Kareem, the links i posted worked. There is another implementation that doesn't work. Just read my question again please. Jul 6 '14 at 19:23
1

When you pass a variable to a function, a copy of that variable is actually passed, not the original variable itself. Similarly, when you pass head[index] to insert(), a copy of that pointer is created and can be referred to as first. When you then initialize first, you initialize the copy (head[index] is never initialized).

To solve this problem, you may pass the address of head[index]. For that purpose, you'll need to change the signature of insert() to be as follows

void insert(int n, node **first)

And to pass the address of head[index] like that

insert(n, &head[index]);

Then dereference that pointer within insert()

// create a temporary node
node *temp = malloc(sizeof(node));
temp -> val = n;

// first insertion
if (*first == NULL)
{
    *first = temp;
}
// insert at the beginning of the list
else
{
    temp -> next = *first;
    *first = temp;
}

If, on the other hand, you care about the list being sorted, you may have something like

// first insertion
if (*first == NULL)
{
    *first = temp;
}
else
{
    // create a previous node
    node *prev = NULL;
    // create a current node
    node *curr = *first;

    // iterate over the list
    while (curr != NULL && curr -> val < n)
    {
        // update pointers
        prev = curr;
        curr = curr -> next;

        // if the end of the list is reached
        if (curr == NULL)
        {
            break;
        }
    }

    // insert at the beginning
    if (prev == NULL)
    {
        temp -> next = *first;
        *first = temp;
    }
    // insert at the middle or at the end
    else
    {
        temp -> next = curr;
        prev -> next = temp;
    }
}
2
  • The last part is to insert it at the front of the list! I am not inserting in sorted order. Jul 6 '14 at 18:41
  • @user1400 edited the answer!
    – kzidane
    Jul 7 '14 at 0:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .