Lecture 5/20: Lecture 20 Q&A
Lecture 20 Questions and Answers (Exported from Zoom Q&A log)
Q: also loved the clip!
A1:
Q: please sing nick!
A1: not a chance!
Q: We can have a 106B sing-a-long instead of lecture
A1: Yeah!
A2: Only if we sing Thank U->Next by Array-ana Grande
Q: So no checks / check pluses anymore?
A1: No, all smoothed to Pass/NoPass and then qualitiative feedback
Q: Is there two more weekly assignments after this week?
A1: yes
Q: Will next week’s HW still be due on Friday even though we have memorial day on Monday?
A1: yes
Q: what exactly are the “next” pointers and how are they associated with 8 and 9?
A1: Node is a struct that has two fields, data (type int) and next (type Node *)
Q: Can you please explain what “new” means in this context?
A1: operator new requests memory space from the heap
Q: Why is the “nebulous” heap also called a heap like the ADT? Did they at one point have some relationship?
A1: No, it’s just computer scientists trying to confuse you. :-)
Q: When we say head = temp, does that mean head points to where temp points rather than pointing to temp?
A1: yes, it makes head and temp hold the same address, i.e. point to same Node, we call those two pointer variables aliases
Q: do you have to use delete on temp ?
A1: No, we plan on keeping that Node, it now the first entry in the linked list. You will see a delete coming up in pop, when we have a Node we are finished with
Q: Would head -> next -> next lead to the end of list?
A1: This would access the third Node in list
Q: why we can’t leave 7 there like we did in heap? In assignment when we dequeue the heap we can swap the node with the last child and modify the size by decreasing one, leaving the node in the memory
A1: Memory for the binary heap was allocated as an array, i.e. a bunch of N elemetns all in one continguous block of memory. We may only be using the first K of those N, the remainder is excess capacity we can use when needed. For a linked list, we allocate and deallocate each element individually
Q: do the stanford collection classes use arrays or linked lists or something else?
A1: Vector uses an array, Set/Map uses tree, Queue is linked list
Q: why, in order to push an element on a stack with a linked list, do you have to add it after the head? why couldn’t you make the stack be in the opposite order, so that you can push the last element on the stack by making the next pointer of the last element in the linked list point to it? wouldn’t this be easier?
A1: A linked list has assymetry in that you can easily add/remove from the front, but not same from back. While you can easily add to back (as Chris is doing right now for Queue), but to remove the lastmost element, you would need access to the penultimate element to set its next to nullptr and you cannot travel backwards in a linked list. If you started back at head, you could walk down to that element, but thats an O(n) operation
Q: what does the underscore in front of _front mean?
A1: It is a naming convention for the class member variables that reminds you that these varaibles belong to “this” object
Q: Delete temp accesses what temp points to correct?
A1: Yes, it marks the memory at that address as available to be recycled
Q: So every element of a linked list can be stored in many unrelated memory locations accross our memory but vectors can only be stored in big open memory spaces that are “in a row”?
A1: Eaxctly! The constraint that the elemetns are laid out in order (array) both a strength and a weakness — can immediately access the Kth by position, but in order to insert in front of Kth, have to shuffle all elements over
Q: Why this time there is no semicolon after the definition of the struct
A1: Oops! Semi-colon should be there. Sharp eyes!
Q: What does private: ListNode* _front do for us? What are the benefits of having this be our only private thing? I’m still confused
A1: The front pointer is sufficient to give us access to all the elements in the list, though we have to traverse to access them
Q: Don't we have to delete newNode or else it will be a memory leak? Might have missed something
A1: No we are going to hold onto that newNode, it is going to become a part of the linked list so we are not done with memory and do not want to deallocate it
Q: Or does it automatically get deleted due to scopes?
A1: Any memory that is explicitly allocated with new has to be explicitly deallocated with delete
Q: why is newNode not _newNode?
A1: We use the convention of naming our member varaibles with underscore, to remind us that this variable is a member variable of “this” object, newNode is not a member variable it is a local temporary
Q: Oh ok. I was referring to the pointer "newNode" but that wasn't created with the "new" and is not in the heap. so when it hits the curly bracket, that pointer gets automatically deleted right?
A1: The pointer variable goes out of scope, yes but that does not mean it calls delete on the address that the pointer
Q: how do we know that next refers to the values on the bottom
A1: The fields in a struct are accessed by name (i.e. curr->data accessed the int field drawn in top of Node diagram, curr->next accesses the Node *field draw in bottom)
Q: What is the disadvantage of using arrays (as we did in this homework) to design Queue?
A1: Arrays occupy contiguous memory so insert/remove requires shuffling elements over to make space. Remember in PQSortedArray how you had to do a lot of work to enqueue the element?
Q: where did we define next?
A1: In the struct definition from the very beginning of the field, next is the name of one of the two fields in a ListNode struct
Q: instead of traversing, can we use an extra pointer called _back always pointing the end of the list to add newNode to the end of linkedList?
A1: Yes, that is what Chris showed earlier when implementing Queue as linked list
Q: don’t we need a temp in order to remove 50
A1: we will need access to the element previous to 50, yes!
Q: do we need to clean the newNode in our memory?
A1: I don’t quite understand the question. For remove, we do need to delete the node that we are removing. is that the issue?
Q: Why is ListNode* curr not = newNode … in the previous example?
A1: In the remove example? Not sure of the context
Q: Why can we just write = _front?
A1: Where?
Q: oh sorry it is for the previous example. When we link the last node (50) with the 100, do we need to delink the original node that we created that originally links to 100?
A1: No, we just spliced around it from the 42 straight to the 100. The 50 will be deallocated and no longer a part of the list, it does not matter that is has link to the 100 that we are no longer using
Q: Just a general question: why does Stanford Library use dynamic memory to make these classes instead of using the stack? E.g. you could make a Vector using int myArray[] instead of int* myArray = new int[].
A1: That’s not necessarily true – things allocated on the stack inside of a function onluy live for as long as that function lives. If you want your backing data to be persist across many funciton calls, storing the data in dynamic memory is the only way to do so.
Q: Yes! In the remove example.
A1:
Q: Is assignment expected to be released Saturday afternoon or no specific time?
A1: live answered
Q: besides deleting temp, do we also need to delete curr?
A1: live answered
Q: So looking at Vectors, what happens if we make a Vector class that stores elements using the stack? Like int _elements[]. Where would we run into problems accessing _elements?
A1: live answered
Q: can you explain curr -> next = curr -> next -> next again?
A1: live answered
Q: also, do you only delete when you say new? like in this week’s assignment
A1: live answered
Q: Can you talk a little bit about adding to the front of the list?
A1: live answered