2

I have a template linkedList that I would like to dynamically create "head" pointers for...

I seem unable to get any syntax to work.. my best guess is:

linkedList<int>** ptr;
ptr = new (linkedList<int>*)[1];

But it doesn't work. I'm fairly new to C++ so any help is appreciated! Thanks!

1
  • 7
    Yo dawg, we heard you like pointers, so we pointed your pointer to a pointer so you can point to stuff while you point to stuff. Commented Mar 29, 2011 at 4:48

4 Answers 4

6

To get a pointer, do:

T* ptr = new T;

where T is your type.
For a pointer-to-pointer, do:

T** ptrptr = new T*;

allocating the space for one pointer, which still needs to be filled like the first method:

*ptrptr = new T;

Now you got a valid pointer-to-pointer.

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

1 Comment

I get cast/assignment errors with my object when I try the code as suggested above.. Do I need to create a constructor for T* in the definition of class T?
1

Is there some reason you are not using std::list? (or std::forward_list)

Check out the header files for std::list, or your nearest C++ book, or in fact cppreference.com

Your linked list class template should have a function to return the head of the list. Look at std::list::begin() in your compiler's c++ library. The std::list::iterator type is a pointer to whatever goes in the list. (ie T*)

3 Comments

My data structures class doesn't allow the use of std, sadly.
Using STL data structures would defeat the purpose of a data structures class - in using STL, you do not learn of the implementation of various structures.
@RageD: The homework tag wasn't present when I answered, although I suspected. For that reason I specifically call out studying the code. Surely studying a reference interface for a linked list template is a valuable way to spend your time in a data structures class.
1

Though I'm not sure pointer array is really needed for your linked list, as for just new construct, the following form will be compiled.

ptr = new (linkedList<int>*[1]);

EDIT:
This allocates pointer array:

linkedList<int>** ptr = new (linkedList<int>*[1]);

This allocates array:

linkedList<int>* ptr = new linkedList<int>[1];

This allocates one element:

linkedList<int>* ptr = new linkedList<int>;

2 Comments

This seems exactly like what I need, but g++ in cygwin complains: error: cannot convert 'linkedList<int>**' to 'linkedList<int>*' in assignment. All I need is a "new" NULL pointer to insert into the AVL Tree. The array notation was just my best guess. Is something along the lines of ptr = new (linkedList<int>*); possible? I tried it, it's not.. but is there anything similar? Thanks!
As far as I see the error, the type of ptr and new expression seem to be mismatched. Please see the edited answer.
0

Normally the head of a linked list would look something like:

node<int> *head = NULL;

When you want to create and insert a node, you'd use something like:

insert(node<int> *&list, int value) { 
// insert new node containing `value` at head of `list`.

    node<int> *temp = new node(value);

    temp->next = list;
    list=temp;
}

You could use this something like:

node<int> *list = NULL;

for (int i=0; i<10; i++)
    insert(list, i);

Of course, unless this is for homework (or something on that order), you should stop working on this immediately, and just std::list (or boost::slist, if you want a singly-linked list).

Edit: I'm adding more detail mentioned by the OP in comment. For the moment, the avl_tree::insert does not attempt to maintain balance. It's just a plain-jane un-balanced insert, but it should be adequate to demonstrate what we care about at the moment.

template <class T>
struct linked_list { 
    node *head;

    void insert(T v) {
        node<T> *n = new node(v, head);
        head = n;
    }

    linked_list() : head(NULL) {}

    template <class T>
    struct node { 
        node *next;
        T data;

        node(T const &v, node *n=NULL) : data(v), next(n) {}
    };
};

template <class keyType, class dataType>
class avl_tree { 
    struct node {
        node *left, *right;
        char balance;
        keyType key;
        dataType data;

        node(keyType const &k, dataType const &d) 
            : left(NULL), right(NULL), balance(0), key(k), data(d)
        { }

        bool operator<(node const &other) { 
            return key < other.key;
        }
    } *root;

    bool insert(node const *new_node, node *&tree) { 
        if (tree == NULL) {
            tree = new_node;
            return true;
        }
        else if (*new_node < *tree)
            return insert(new_node, tree->left);
        else if (*new_node > *tree)
            return insert(new_node, tree->right);
        else // new_node == tree
            return false; // couldn't insert -- already present.
    }

public:

    avl_tree() : root(NULL) {}

    void insert(keyType const &key, dataType const &data) { 
        node *temp = new node(key, data);
        insert(temp, root);
    }
};

3 Comments

Yes, this is for an assignment. The idea is that I have an AVL Tree with ItemType linkedList<int>*, representing the head of a linked list. I am trying to insert nodes onto the AVL Tree, each with its own new linkedList<int>* head. I am not allowed modify the AVL Tree source code, so I have to somehow start and maintain a linked list for each AVL Tree node. Since I am populating my AVL Tree from within a while loop, however, my pointers are either deleted (if defined within the loop) because of scope, or I only have one pointer, which is set to be the head of every AVL node.
The linked list being built into an AVL tree node shouldn't really change much (if anything).
The main problem is that I have to declare the AVL Tree in the form AVL< string, linkedList<int>* > myTree;. So I cannot program a concrete node into the AVL Tree. I'm left guessing at how to use AVL Tree bool insert(string,linkedList<int>*) to in essence achieve the same effect.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.