Delete pointer in two lists

Question

I have an array of linked list , each index of array holds linked list.

Beside that, I have another linked list , that hold nodes in exact order I inputted them.

So for example. My array has 500 indexes. I input one node on index 1 and one node on index 2. When I print linked list on index 1 it will print only one node. However when I print the linked list that holds the exact order that node were inputted in , it will print both of them in order I inputted them.

I have implemented this using this code

class CHash{

public:
    CHash(){
        for( int i = 0; i < 500 ;i++){
            holder[i] = NULL;
        }
        first = NULL;
        last  = NULL;
    };
    void insert( string key , string value ){
        size_t num = index(key);
        Node *tmp;
        if( holder[num] == NULL ){
            tmp = new Node(key , value , NULL);
            holder[num] = tmp;
        }else{
            tmp = new Node(key, value , holder[num]);
            holder[num] = tmp;
        }
        if( first == NULL){
            tmp -> nextNode = NULL;
            tmp -> prevNode = NULL;
            first = tmp;
            last  = tmp;
        }else{
            tmp -> prevNode = last;
            last -> nextNode = tmp;
            last = tmp;
        }
    }
    void Print( size_t number ){
        Node *tmp = holder[number];
        while( tmp!= NULL){
            cout << tmp -> value << endl;
            tmp = tmp -> next;
        }
    }
    void PrintAll(){
        Node *tmp = first;
        while( tmp != NULL){
            cout << tmp -> value << endl;
            tmp = tmp -> nextNode;
        }
    }
    size_t index( string name ){
        return name.length();
    }
    void de(string val){
        size_t num = index(val);
        if( holder[num] == NULL){
            return;
        }
         Node *tmp = holder[num];
         Node *help;
         Node *help1;
        while( tmp != NULL){
            if( tmp -> key == val){
                Node *temp = tmp;
                if( tmp -> prevNode != NULL)
                    help = tmp -> prevNode;
                else
                          help = NULL;
                if( tmp -> nextNode != NULL)
                    help1 = tmp -> nextNode;
                else
                          help1 = NULL;
                if( tmp -> next != NULL){
                    tmp = tmp -> next;
                    tmp -> nextNode = help1;
                    tmp -> prevNode = help;
                }
                else
                    tmp = NULL;

                delete temp;
                return ;
            }
            tmp = tmp -> next;
        }
    }

It works , what troubles me is the de method. It should find the node with key same as argument and delete it. This delete should be reflected in both linked list. I have been trying to figure this out for a while but it always throw seg fault.

Example of usage.

 CHash one;
    one.insert("two","cauko");
    one.insert("tuk","hello");
    one.insert("three","hrello");
    one.Print(3) // should print "hello" , "cauko"
    one.PrintAll() // should print "cauko" , "hello" , "hrello"
    one.de("tuk");
    one.Print(3); // should print only "cauko"
    one.PrintAll(); // should print "cauko" , "hrello"

Where did I make a mistake?

Imagine if you had a large code base, and wanted to search for all instances of `de`. What I'm saying is that you should give your functions a little bit more of a descriptive name. — PaulMcKenzie, May 23 '16 at 18:00
Why not use `std::list` instead of all of this linked list code? Or at the very least, create a working standalone linked list class without hash table code. Once it works, *then* you use that working, debugged, linked list class in your larger hash table program. BTW, I don't see an array of linked list -- I would have expected `LinkedList allLists[5];`' or something like that -- that is an array of linked lists. — PaulMcKenzie, May 23 '16 at 18:05
` if( holder[num] == NULL ){ tmp = new Node(key , value , NULL); holder[num] = tmp; }else{ tmp = new Node(key, value , holder[num]); holder[num] = tmp; }`. Redundant code much? — kfsone, May 23 '16 at 18:18

coyotte508 · Answer 1 · 2016-05-23T18:51:39.597

You should give a more explicit name to the de function, add comments, create more functions for individual tasks like finding the node for a specific value and give a fully compilable code.

The code below for de assumes that the linked list using ->next doesn't have a corresponding prev, as no information is given on this subject.

void deleteVal(string val){
    size_t num = index(val);
    if( holder[num] == NULL){
        return;
    }

    /* Find the key first */
    Node* tmp = holder[num];
    Node *prev = NULL;
    while (tmp != NULL) {
        if (tmp->key == val) {
            break;
        }
        prev = tmp;
        tmp = tmp->next;
    }

    if (tmp->key != val) {
        //key not found
        return;
    }

    /* remove the element from the global linked list */
    if (tmp->prevNode) {
        tmp->prevNode->nextNode = tmp->nextNode;
    }
    if (tmp->nextNode) {
        tmp->nextNode->prevNode = tmp->prevNode;
    }

    if (first == tmp) {
        first = tmp->nextNode;
    }
    if (last == tmp) {
        last = tmp->prevNode;
    }

    /* Now remove the element from the linked list corresponding to index */
    if (holder[num] == tmp) {
        holder[num] = tmp->next;
    } else {
        prev->next = tmp->next;
    }
//uncomment if the ->prev member exists in your class
//     if (tmp->next) tmp->next->prev = tmp->prev;
    /* Delete. */
    delete tmp; //maybe tmp->next = tmp->nextNode = NULL before depending on your destructor
}

The main problem was that you were mixing the two linked lists here in your code:

            if( tmp -> next != NULL){
                tmp = tmp -> next;
                tmp -> nextNode = help1;
                tmp -> prevNode = help;
            }

The two linked lists have nothing to do with each other.

Thanks , this does not throw seg fault , but code that demonstrate usage of it. using printAll after delete prints the first value twice. — Darlyn, May 23 '16 at 18:36
I edited to add updating of `first` and `last` if needed. To help any further I'd need to have a whole code compilable (full file for `CHash` and `Node`) — coyotte508, May 23 '16 at 18:47

score 1 · Answer 2 · edited May 23 '17 at 11:45

I have an array of linked list , each index of array holds linked list.

Beside that, I have another linked list , that hold nodes in exact order I inputted them.

You shouldn't have nodes shared between these linked lists, unless you're using something like

struct Node {
    // ...
    std::shared_ptr<Node> prev_node;
    std::shared_ptr<Node> next_node;
};

Also have a look at What is the Rule of Three.

score 1 · Answer 3 · answered May 23 '16 at 18:11

You are trying to manage two interwoven linked lists, and you are shredding them both. You must master simpler exercises before you attempt something this complex.

Specifically, the problem is here:

if( tmp -> next != NULL){
  tmp = tmp -> next;
  tmp -> nextNode = help1;
  tmp -> prevNode = help;
}
else
tmp = NULL;

You completely neglect the node whose next points to tmp. And instead of connecting two nodes to each other by means of help and help1 (your variable names are dreadful), you are connecting them both to an unrelated node.

Delete pointer in two lists

3 Answers3