4 way linked list

[GuitarMan]

I deleted the prev pointers and made the lists one way lists. That' s why i needed to use more for loops, to access a node before the n node.

[cire]

That' s why i needed to use more for loops, to access a node before the n node.

Two loops are sufficient for doubly or singly linked lists.

Revisiting the utility function contains presented in an earlier post to reflect the changes you've made and to make it more useful in a singly linked list:

    // returns a prev/current node pair where first is the previous node and current
    // is the node that contains the ID, if any.  If the second node is null, the list doesn't contain
    // the id

    std::pair<Hnode*, Hnode*> contains(int ID) const       // utility function
    {
        std::pair<Hnode*, Hnode*> nodes = { nullptr, first };

        while (nodes.second && nodes.second->FieldID != ID)
        {
            nodes.first = nodes.second;
            nodes.second = nodes.second->next;
        }

        return nodes;
    }

Note: 1 loop above.

Which leads us to:

    void DeleteField(int GivenField)
    {
        Hnode* node;
        Hnode* prev;

        // unpacks the pair into prev/node.
        std::tie(prev, node) = contains(GivenField);

        if (node)
        {
            while (node->down)
            {
                Vnode* vn = node->down;
                node->down = node->down->lower;
                delete vn;
            }

            if (prev)
                prev->next = node->next;
            else
                first = node->next;

            delete node;
        }
    }

Note: 1 additional loop for a total of 2 loops.

You may need to #include utility for std::pair and tuple for std::tie.

This code is untested.

[GuitarMan]

I might need to write the function manualy then, becouse we're not allowed to use any includes except for fstream and iostream, but i guess i got the idea. I will try it out.

[dhayden]

I still think it's much easier to think of this as TWO data structures. Actually it's 4:
- A single point in a list.
- A list of points.
- A single Field in the list
- A list of Fields.

If you think of it like this then you'll have nearly identical methods for manipulating the two lists. As you find bugs in one, you can fix the other, almost in your sleep.

Dealing with linked lists is much MUCH easier if your find() doesn't return a pointer to a node, but rather returns a pointer to the link that points to the node. In other words, it returns a pointer to head, or a pointer to the previous node's next pointer. If you do this, then adding and deleting become almost trivial because you never have to worry about a special case for adding or deleting at the head of the list

In C++, it's better to return a reference to the link rather than a pointer. So suppose you have

class PointID {
public:
    PointID(int _id) : id(_id) {}
    int id;
    PointID *next;              // owned by this
};

class PointList {
public:
    // Find the PointID node with the give ID and return a reference
    // to the pointer to the node (i.e. a ref to head or a PointID::next
    // pointer.  If the node isn't found then return a ref to the last
    // link in the list (again, head or a a PointID::next)
    PointID * &findNode(int id);
    ...

The findNode is :

PointID * &PointList::findNode(int id)
{
    PointID **headOrNext;
    PointID *p;
    for (headOrNext = &head; p = *headOrNext; headOrNext = &p->next) {
        if (p->id == id) {
            break;
        }
    }
    return *headOrNext;
}

Now deleting becomes really east:

bool PointList::del(int id)
{
    PointID* &link = findNode(id);
    if (link) {
        PointID *node = link;
        link = link->next;      // unlink node from the list
        delete node;
        return true;
    }
    return false;
}