Pointers for struct and `for`

Question

I know something about pointers, but I'm trying to check my knowledge on a sample. Can somebody check if my code is good? I don't think that I should use pointers in these structs.

The second question is: Can I use a for loop like this?

for(DLList* i=first; i!=0; i=i->next)

Is it correct?

struct Node
{
    int id;
    int dist;
    Node* prev;
    vector<Edge*> edges;
};

struct Edge
{
    int length;
    Node* to;
};

struct DLList
{
    DLList *next;
    DLList *prev;
    Node* val;
};


struct DList
{
    DLList *first,*last;

    DList()
    {
        first = 0; 
        last = 0;
    }

    DLList* add(Node* n)
    {
        DLList *newNode = new DLList;
        if(first == 0)
        {
            newNode->val = n;
            newNode->next = 0;
            newNode->prev=0;
            first =  newNode;
            last = newNode;     
        }
        else
        {
            newNode->val = n;
            newNode->next = 0;
            newNode->prev=last;
            last = newNode;
            last->next=newNode;
        }
        return last;
    }

    void removeFirst()
    {
        if(first!=0)
        {
            first = first->next;
            if(first != 0)
            {
                first->prev = 0;        
            }   
        }
    }

    void remove(DLList* e)
    {
        if(e==0)
        {
            return;
        }
        else if(e==first)
        {   
            removeFirst();
        }
        else if(e==last)
        {
            last = last->prev;
            last -> next = 0;
        }
        else
        {
            e->prev->next = e->next;
            e->next->prev = e->prev;
        }
    }

    void remove(Node* n)
    {
        if(first == 0)
        {
            return;     
        }
        if(n==first->val)
        {
            removeFirst();
        }
        else if(n==last->val)
        {
            last = last->prev;
            last->next = 0; 
        }
        else
        {
            for(DLList* i=first; i!=0; i=i->next)
            {
                if(n==i->val)
                {   
                    i->prev->next = i->next;
                    i->next->prev = i->prev;
                    break;
                }       
            }   
        }
    }

    bool isEmpty()
    {
        return first == 0;
    } 

};

Answer 1

I'm assuming that this is basically a pointer exercise rather than a real piece of code that you're planning to use. If it's the latter, please reconsider -- there are STL containers that do this better and safer. As to your question about the for loop, there's nothing wrong with that if you're using pointers. In fact it's a pretty common idiom in C.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. I don't know that you're doing that, but the use of vector in the definition of Node suggests it.

Use nullptr

Every instance of 0 in your code would probably more correctly be encoded as nullptr as defined in C++11. If you're using an older compiler, you can use NULL instead which will more clearly indicate to readers of your code that these are pointers.

Reconsider the interface

If this is a pointer exercise, that's fine, but if you actually intend to use this for something, you should probably reconsider the interface. Specifically, passing around raw pointers is not generally a good idea in C++. Better would be to use unique_ptr (C++11) or auto_ptr (C++03).

Also the version of remove() that takes a linked list node pointer as an argument is a very dangerous thing to have in an interface. Knowledge of a node's structure would be better encapsulated within the class and not revealed as part of the interface.

Use better names

Having DLList as the name of a class implementing a doubly-linked list makes sense, but having that actually be the name of an individual node in such a list does not. Instead of DList and DLList, it would be much easier to interpret your code if they were named DLList and DLListNode. Also the function add suggests that the node is added to the end, but the code actually prepends this to the list which is, at best, confusing.

Simplify remove(Node* n)

The remove(Node *n) is more complex than it needs to be. It could be rewritten as:

void remove(Node* n)
{
    for(DLListNode* i=first; i!=nullptr; i=i->next)
    {
        if(n==i->val)
        {   
            i->prev->next = i->next;
            i->next->prev = i->prev;
            break;
        }       
    }   
}

Note that this still has a bug just like the original. What happens if i->prev or i->next are null pointers? You should handle those cases.

A similar simplification could be done for the other remove functions.

Don't leak memory

Your program uses new but not delete which is a surefire recipe for memory leaks.

Be explicit about whether your container owns contained objects

It's not clear (because there are not comments) whether the contained Node objects should be destroyed or not when either of the two remove functions is called.

Define a destructor

Because you have a constructor, you really should define a destructor as well. See the note above about leaking memory.

Consider using an anchor node

Much of the special-case checking for null pointers in your code would disappear if you defined an anchor or head node in the constructor. In that case, there would always be one node and you wouldn't have to check for null pointers quite as often.

Answer 2

I would start by rethinking the basic idea here. What sort of collection do you really want? Are you trying to create a way to store key/value pairs, or are you trying to create a sequence? Right now you have some pieces of both, but doesn't seem to me to be designed to do either particularly well. If it's going to be a sequence, you probably want things like the ability to add to the beginning, end, or an arbitrary point in between (and the same with deleting). If you want key/value pairs, then you want to specify a insertion of a key/value, deletion of a key, and a policy about whether duplicate keys are supported or not.

To maximize versatility, I'd at least consider supporting iterators, with a begin, end, cbegin, cend (etc.) to get iterators to look at the collection. This isn't much work, and immediately lets the collection work with all the standard iterators as well as range-based for loops.

As far as the code itself goes, I think first I'd turn the doubly-linked list class into a template--there's no particular reason to write the code specifically to store one type. It can store pretty much arbitrary types just as well.

Next, I'd reorganize the code a little. As far as I can see, your DLList is really just a node in a DList. That being the case, I'd organize the code more like:

template <class T>
class DList {

    class Node {
        Node *prev;
        Node *next;
        T value;
    };
    // ...
    Node *first;
    Node *last;
};

This way, the rest of the world doesn't even need to know that such a thing as a node in the linked list exists at all. To the rest of the world, it's just a collection where it can store items, retrieve items, etc.

Then, the rest of the code in DList pretty much needs to be rewritten to work in terms of T rather than explicitly referring to a Node.

One other point: as shown above, I'd generally prefer to see each object defined separately. This is particularly true in the case of pointers and references (such as first and last, in this case). Especially for those unfamiliar with C and C++, it's easy to mistake something like: T* first, last; as meaning that first and last are both pointers to a T (which is not the case). Moving the white-space like T *first, last; can help a little, but it's still pretty easy to misinterpret. Defining each object separately eliminates most possibility of misinterpretation.