[Travelsonic]

So, for my class, we were given the following header for a doubly linked list, and asked to implement some functions which I will post a bit later, when I reach the point where I am asking for help. For now I wanna focus on the list, node definitions given to us:

Quote

struct NodeType
{
ListInfo info;
NodeType* next;
NodeType* prev;
};

typedef NodeType *NodePtr;
typedef NodePtr List;

Now, here's my problem. Last time I did data structures, I used C++, with classes. I didn't touch structs... in fact, at the college I was enrolled in at the time, the only time I touched structs was in a beginning programming class, and it was for like 1 assignment, before even learning about pointers., nor did I alias any with typedefs, so this for me has been a bit confusing as hell so far as how to work backwards, look at how I need to handle the List object, and the underlying node. Specifically, I'm not sure I am doing it right Also, it's been a couple of years since I really did anything C++.

So... NodeType is a pointer to a NodeType.... and List is typedefed as a NodePtr, so... I can treat the List object as a pointer to a NodeType?

This post has been edited by Travelsonic: 13 October 2016 - 11:04 PM

[SupperTails66]

In C++, the only difference between a class and a struct is that, until you make an explicit public:/private:/protected: declaration, every member of a class is private by default and every member of a struct is public by default. Or at least that's how it's explained in Programming Principles and Practices Using C++; if there's some further technical distinction, someone better versed in the language than I am can tell you, but it's probably not relevant to your needs anyway.

Your interpretation of the typedefs is correct (assuming you meant to say "NodePtr is a pointer to a NodeType"). The terminology here seems a bit strange to me -- without seeing the rest of the code, I'm not sure why you would typedef NodePtr to List. It probably makes more sense in context.

[Travelsonic]

The rest of the header includes the definitions of the functions we need to implement.

Quote

typedef NodeType *NodePtr;
typedef NodePtr List;

//initialize the list with the header pointing at itself
void initializeList(List *listPtr);

//return true if the only element on the list is the header
//otherwise return false
bool isEmpty(const List list);

//Remover all elements including the header from the list
//se the List to null
void clearList(List *listPtr);

//Add the value to the front of the list
void pushFront(const List list, ListInfo value);

//Add the value to the back of the list
void pushBack(const List list, ListInfo value);

//Remove and return the value at the front of the list
ListInfo popFront(const List list);

//Remove and return the value at the back of the list
ListInfo popBack(const List list);

//Return true if the value appears in the list,
//otherwise return false
bool findInList(const List list, ListInfo value);

Now, here's another problem: I noticed that the functions taking in a pointer to a List are taking in a pointer. This shows how long it has been since last doing C++, but wouldn't I still be passing by value, creating a copy of,it, rather than modifying the original? Wouldn't I need to add the address-of operator so it is actually being passed by reference? IF so, I am gonna hit a brick wall quickly, as my prof. seems to not want ANY changes to the declarations for the functions we are going to be implementing. Then again, part of me feels like I am missing something, a trick so to speak that would let me get away with not explicitly using the address-of operator, or I am just a grade-a dumbass. >_<

This post has been edited by Travelsonic: 14 October 2016 - 01:41 PM

[Morph]

Travelsonic, on 13 October 2016 - 11:03 PM, said:

So... NodeType is a pointer to a NodeType.... and List is typedefed as a NodePtr, so... I can treat the List object as a pointer to a NodeType?

NodePtr is of type NodeType*, and List is the same as NodePtr. I still get confused by typedefs sometimes, which is why I now prefer using.

SupperTails66, on 14 October 2016 - 03:27 AM, said:

if there's some further technical distinction, someone better versed in the language than I am can tell you, but it's probably not relevant to your needs anyway.

Pretty much. They'll both perform this job functionally the same as far as usage goes. Once compiled though, a class will have a vtable, whereas a struct typically won't. But that doesn't really matter here.

Travelsonic, on 14 October 2016 - 07:00 AM, said:

Now, here's another problem: I noticed that the functions taking in a pointer to a List are taking in a pointer. This shows how long it has been since last doing C++, but wouldn't I still be passing by value, creating a copy of,it, rather than modifying the original? Wouldn't I need to add the address-of operator so it is actually being passed by reference? IF so, I am gonna hit a brick wall quickly, as my prof. seems to not want ANY changes to the declarations for the functions we are going to be implementing. Then again, part of me feels like I am missing something, a trick so to speak that would let me get away with not explicitly using the address-of operator, or I am just a grade-a dumbass. >_<

So you're confused by the functions that take List*? The functions that take in List* (where List is NodeType*, meaning List* is NodeType**) do so in order to change where your NodeType* is pointing. So if you have a List variable, you would in fact need to pass it in using &. This will give the function a pointer to your pointer. POINTERS EVERYWHERE!

In case my explanation wasn't clear, I'll use clearList as an example. Here's what our (fake) definition of clearList looks like.

Quote

void clearList(List* list)
{
    // Clear all the data that needs to be cleared...

    ...

    // Now we can change the value of list to null by dereferencing it. (nullptr == 0)
    *list = nullptr;
}

This is effectively the same as taking in a pointer to say, an int, and changing its value by *value = 1234. The only difference is that our value is yet another pointer.
Now let's put it to use:

Quote

// (nullptr == 0)
List myList = nullptr;

// Initialize our list
initializeList(&myList);

// Our pointer, myList, is now a valid pointer, so we can add some data.

...

// Now our list has data in it, but we're done using it and want to clear it.
// We pass in a pointer to our list (pointer to a NodeType pointer) so that clearList can change the
// value of our pointer to nullptr, as all of its data has been freed.
clearList(&myList);

// myList is now null, pointing nowhere. Any further attempts to access it will cause a runtime exception.

[SupperTails66]

Whoops, ninja'd. Here's what I wrote before I saw the previous post, in case it helps:

First, this is actually C code. I'm guessing you'll be asked to do an object-oriented rewrite of this into a "proper" List class in a future assignment.

Remember, List has been typedefed to a pointer; List* is actually a pointer to a pointer (specifically, it's the same as writing NodeType**). That means you're altering the pointer to the List, not the nodes themselves. For example:

void func(List* list) {
  list = NULL;
}

List lst;
initializeList(lst);
List samelst = lst;
func(lst);               // lst is now NULL, but the list data is intact
                         // and can be accessed through samelst

The name of the List typedef somewhat obscures this; personally I would have called it "ListPtr", but perhaps the idea is to maintain consistency if you do rewrite this in C++ later.

This post has been edited by SupperTails66: 14 October 2016 - 01:56 PM

[Morph]

Much cleaner than my example!

[Black Squirrel]

What's the goal here - to make your own linked list, or to familiarise yourself with typedefs? Or maybe just pointers?

Because if it's the former, the first thing I'd do is completely ignore all the typedefs until the very end, because they're not helping anyone in this context (the idea of writing "List list" at any point sounds like really bad news to me). Or rename the typedefs so that they're not horrible - whatever floats your boat.

I think the jist of everything pointer related has already been explained, and structs are basically classes where everything is public.


(alternatively use the standard list, and when someone asks, claim it's faster and better than anything you can make and it's already been widely adopted )

[Travelsonic]

Black Squirrel, on 14 October 2016 - 03:24 PM, said:

(alternatively use the standard list, and when someone asks, claim it's faster and better than anything you can make and it's already been widely adopted /> )

Can't - have to implement the functions given to us.

[flamewing]

SupperTails66, on 14 October 2016 - 03:27 AM, said:

if there's some further technical distinction, someone better versed in the language than I am can tell you, but it's probably not relevant to your needs anyway.

There is nothing else, that is literally all of the differences between class and struct in c++.

Morph, on 14 October 2016 - 01:38 PM, said:

Pretty much. They'll both perform this job functionally the same as far as usage goes. Once compiled though, a class will have a vtable, whereas a struct typically won't.

The class has a vtable if and only if it has virtual member functions, or inherits from a base class or struct that has virtual member functions. Likewise for struct.

[Morph]

flamewing, on 14 October 2016 - 08:46 PM, said:

The class has a vtable if and only if it has virtual member functions, or inherits from a base class or struct that has virtual member functions. Likewise for struct.

Oh right, duh. It even says it right in the article I linked. As for structs, I guess I never thought to use virtual functions in structs in any of my programs (that I've disassembled out of curiosity, at least).

[Travelsonic]

So I have made a hell of a lot of progress.

I think.

But now, I am stuck here, with this function to implement:

Quote

//Remove and return the value at the front of the list
ListInfo popFront(const List list);

(and, conversely, the popBack function) because of the use of the const qualifier for the parameter. Remember, it has been a few years since I touched this stuff. I am obviously supposed to modify the list so I pop off the node, but the fact that the list is being passed as a const is throwing me off a little.

[Travelsonic]

Pardon the double post... god, I feel dumb, it seems maybe the use of const is so we are forced to utilize pointers...? I thought I'd be able to go through a pointer referencing the original list, but I KNOW I am doing something wrong. I am ready to pull my hair out of my head.
For example, PushFront, here is what I tried to throw together, not working right (no seg faults luckily).

Quote

void pushFront(const List list, ListInfo value){

if(!list){return;}
const NodeType * listPtr = list; // I thought I would be able to go through
NodeType * newHead = new NodeType;
newHead->info = value;
newHead->next = list;
listPtr = newHead;

}

So far as the node not actually appearing to be inserted properly. Again, been easily 2 1/2 years at LEAST since I last did this, not as if I am freshly trying to learn C/C++. :P

So, I did a little thing in my function to dump addresses - seems my problem is not changing what IS the head, as that address is being changed correctly, but setting the next node in that new head to be what WAS previously the head. Ugh.

This post has been edited by Travelsonic: 18 October 2016 - 10:10 AM

[Morph]

If I understand your code correctly, you were trying to change the value of the "list" parameter (the location that it points to). Is that right? If so, it seems like you don't have the hang of pointers yet. I don't blame you; it can be pretty confusing. Let me try to explain what your code is doing:

Quote

    const NodeType * listPtr = list; // I thought I would be able to go through 

Your variable here, listPtr, is a local variable. By assigning it to the value of "list", what you're doing is: "listPtr, you now point to the same data that list does".

Quote

    NodeType * newHead = new NodeType;
    newHead->info = value;
    newHead->next = list;

This is all fine so far.

Quote

    listPtr = newHead;

Here however, you're doing the same thing you did in the first quote. "listPtr, you now point to the same data that newHead does." This will not modify the original pointer or the data it points to in any way. That being said, the data that is pointed at by a const pointer cannot be modified using that const pointer (at least, in MSVC++ 2015) (e.g: it points to constant data or should be treated as such; therefore it cannot be changed). I also don't know what the ListInfo type is, so I don't know whether or not it would have anything useful in it for this situation.

[Travelsonic]

ListInfo is typedef'd from an int type.

This post has been edited by Travelsonic: 19 October 2016 - 12:21 AM

[Travelsonic]

I am confused as to what the hell I should do - seeing I can't change the parameters for the functions the prof. gave us (wants us to keep it all as-is)/the parameter is const.

This post has been edited by Travelsonic: 19 October 2016 - 12:22 AM