Doubly Linked List

[johnv24]

So I have an online C++ class and its really getting the best of me right now. I understand completely how doubly linked lists work. My whole problem is just implementing it. I only have a book for reference and the book doesn't even cover it in depth.

Here is the code. All I was looking for was what I'd have to do with the code to finsih converting the insert and remove functions to doubly linked. I've worked a little on them and Im still confused. In order for it to be double every node has to have 2 pointers. So when I add/remove a node I need to reset the points on the nodes before and after.

Insert

void linkedList::add(string s){
    node *n = new node();
    n->name = s;
    n->next = NULL;
    
    // take care of empty list case
    if(empty()){
        top = n;
        
    // take care of node belongs at beginning case
    } else if(getTop()->name > s){
        n->next = getTop();
        setTop(n);
    
    // take care of inorder and end insert
    }else{
        
        // insert in order case
        node *curr = getTop(), *prev = curr;
        
        while(curr != NULL){
            if(curr->name > s)break;
            prev = curr;
            curr = curr->next;
        }
        
        if(curr != NULL){ // search found insert point
            n->next = curr;
            prev->next = n;
        }
        
        // take care of end of list insertion
        else if(curr == NULL){// search did not find insert point
            prev->next = n;
        }
    }
}

Remove

// can not call this method "delete" - "delete" is a reserved keyword.
void linkedList::remove(string s){
    bool found = false;
    node *curr = getTop(), *prev=NULL;
    
    while(curr != NULL){
        // match found, delete
        if(curr->name == s){
            found = true;		
            
            // found at top
            if(prev == NULL){
                node *temp = getTop();
                setTop(curr->next);
                delete(temp);
                
                // found in list - not top
            }else{
                prev->next = curr->next;
                delete(curr);
            }
        }
        
        // not found, advance pointers
        if(!found){
            prev = curr;
            curr = curr->next;
        }
        
        // found, exit loop
        else curr = NULL;
	}
    
    if(found)cout << "Deleted " << s << endl;
    else cout << s << " Not Found "<< endl;
}

Definitions

class node{  
public:
    string name; 
    node *next;
    node *prev;
};

class linkedList{
public:
    linkedList():top(NULL){}	
    bool empty(){return top == NULL;}	
    node *getTop(){return top;}	
    void setTop(node *n){top = n;}	
    void add(string);	
    int menu();	
    void remove(string);	
    ~linkedList();
    void reversePrint();
    friend ostream& operator << (ostream&, const linkedList&); // default output is in-order print.
private:
    node *top;
    node *end; // to be used for reverse print and implemented by students
};

[LB]

You create the new node, get the before and after from the old node, point the new node to the before and after, and point the before and after to the new node. Which part of that sentence are you struggling with?

[johnv24]

// insert in order case
        node *curr = getTop(), *prev = curr;

        while(curr != NULL){
            if(curr->name > s)break;
            prev = curr;
            curr = curr->next;
        }
        
        if(curr != NULL){ // search found insert point
            n->next = curr;
            prev->next = n;
        }

Okay so what is all happening in this? I am finding exactly where to put the new node and setting the previous pointer to point to the new one and the new one to point to the next one.

Now for a doubly linked list I need a point that both points to the old one and the new one. But isn't that the same as prev? I'm just really confused on everything.

[doug4]

It is a good idea to draw a diagram of the list. Show the elements of the list and their pointers. Then show the new element and it's pointers. Then start crossing out pointer and drawing new ones as a node is added. Write down what happens when, and you have the algorithm for your function.

[nathan10]

I am learning linked lists too and just wrote my first doubly linked list this weekend. I was only able to write it with inserting a new node at the start of the list. I am still working on inserting at the end of the list and in the middle of the list.

When I read the OP's code, I could only completely follow the definitions section. I did not try to follow the remove section and could not follow much of the insert section.

My understanding of the doubly linked lists is that there are 4 pointers to deal with; the OP calls them next, prev, top, and end. When a node is inserted these 4 pointers are affected.

That is what I can't follow in the OP's insert code, how those 4 pointers are clearly identified. When inserting at the top of the list, if the list is empty, the pointers are top and end must now point to the new node instead of being null, while prev must point to the top and next point to the end. If the list is not empty, the pointer end doesn't change; it still points to the last node in the list. The pointer top points to a new first node. The pointer prev of the old first node has to now point to the new first node. Its next pointer doesn't change and still points to the now third node in the list. The new prev pointer, of the new first node, will still point to the top. Its pointer next must point to the new second node. Et cetera.

I am trying to apply that logic to inserting at the end of the list and in the middle of the list. Wish me luck!