Empty/Full Linked List

Question

So for my first question. I'm working on a project and I need my constructor to create an empty linked list. Would this be correct?

// member variables
private:
   node* headptr;
   size_type howmany;

//constructor
SuperList::SuperList(){
    headptr = NULL; //does this create an empty list?
    howmany = 0; //counts how many nodes are in the list
}

Second question. I need to create a isEmpty() function and a isFull() function. For the isEmpty() function I just see if howmany == 0, right? But to check if list is FULL how would I do that? For normal arrays there is a CAPACITY, but there is no capacity given for linked lists.

    //these are the specifications I was given for the isFull function

    Effect: Determines if this list is full
    Precondition:  NONE
    Postcondition:  this object is unchanged
    Returns:  true if it is not possible to allocate any more memory, false otherwise

    bool SuperList::isFull() const

First question: Looks ok. Second question: a normal linked list can´t be full (except for full computer RAM, int overflowing etc.). What do you think you want to check? — deviantfan
– deviantfan, Commented Sep 21, 2014 at 23:39
Well, you edit is pretty clear. true if you can´t allocate. And you should probably check the int too. — deviantfan
– deviantfan, Commented Sep 21, 2014 at 23:40
Also in the postcondition it uses the term object instead of list. Is that a typo or does it actually mean object? — flowinwind
– flowinwind, Commented Sep 21, 2014 at 23:41
You could say the list is full when the number of elements equals std::numeric_limits<size_type>::max() ? I would not bother — Neil Kirk
– Neil Kirk, Commented Sep 21, 2014 at 23:48
Making an empty list is really easy: void* list = nullptr. It's when you want to be able to add stuff to it that it gets [more] complicated. — Lightness Races in Orbit
– Lightness Races in Orbit, Commented Sep 21, 2014 at 23:53

bwinata · Accepted Answer · 2014-11-05 05:05:34Z

2

First question:

This is fine. Although, you probably want to add a node to keep track of the tail.

Second question

isEmpty() can either be done by checking if how_many is zero or simply by checking if headptr == NULL.
isFull() depends if you really want to set a limit to the length of the list. Generally speaking, lists can keep going only constrained by the amount of allocated memory available in the system. If your intent is to set a limit, then I would allow for the user to pass in a number through the constructor specifying their list size. From here you can simply use a counter to keep track...

answered Nov 5, 2014 at 5:05

bwinata

19111 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Empty/Full Linked List

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related