Q: so we sign up through paperless?
A1: Correct
Q: should we submit something now or later?
A1: Now is good
Q: How do you sign up for it?
A1: The same way that you would normally sign up for IGs! :)
Q: is the meeting required?
A1: No, it is optional but highly recommended
Q: Will we get our exam back so we can review it before the meeting?
A1: Yes!
Q: What is the difference between a class and a struct
A1: live answered
A2: By default fields are public for struct, and by default fields are private for class. The rest is pretty much all same.
Q: When you declare and initiate an object with a new keyword, is there an default pointer created anywhere, or do you have to make one yourself?
A1: The new operator returns the address of the allocated memory, you store that address into a pointer variable that you declared
Q: So is "dt" a pointer here: Date dt = new Date(); or only here: Date* dt = new Date();
A1: What makes a variable a pointer is adding the asterisk to the declaration, so only the second is correct (the first would not compile)
A2: The first line of code would not be valid since the return type of the new keyword is always a pointer.
Q: Why wouldnât we have the âFrontâ of the queue be the left of the vector?
A1: live answered
A2: We could have done that, but then dequeue becomes O(n) and enqueue becomes O(1)
Q: What if we wrapped around and kept track of where the front and back were (expanding if necessary)?
A1: This could definitely be done, but gets complex
A2: That could work! The ring buffer queue from section does this
Q: Why are we using the ânewâ keyword for all the pointers? Is there a way to create a pointer to an int that is not on the heap?
A1: Not quite, the point of using a pointer is that it has a memory address which you can only get on the stack
A2: While there is technically a way to get a pointer pointing to an element on the stack, we steer clear of that in this class (you will see this come up in CS107)
A3: typo:On the heap
Q: why can it not be âint*â ?
A1: live answered
Q: Can you use linked lists to create a binary heap?
A1: live answered
Q: Are next and 6 the same data typ
e?
A1: The data field is int type, the next field is pointer type.
Q: Wouldnât it still be O(N) to go through from the head to the tail if we wanted the last element in the list?
A1: Correct
Q: Does the fact that you don't need contiguous memory give linked lists an advantage over arrays?
A1: live answered
A2: In some sense yes, given that we donât have to deal with the overhead of keeping meaningful values together in contiguous memory (the distributed memory style of linked lists also has its own downsides but those are beyond the scope of this class)
Q: how do you tell the front pointer to point to 7
A1: live answered
A2: the code to do this will be coming up later
Q: Now with a front pointer and a back pointer, the efficiency of enqueueing and dequeueing are both O(1) now?
A1: Correct!
Q: If we are changing the pointers n times why isnât it 0(n)?
A1: live answered
A2: You only have to reqire the pointers once for a given operation (enqueue/dequeue)
Q: Could the *front pointer still be an int?
A1: live answered
Q: why cant we use a front pointer in a normal queue
A1: live answered
A2: It depends on what you mean in a ânormal queueâ really â pointers only become relevant when we are directly building the queue from individual dynamically allocated blocks
Q: is node a struct
A1: live answered
Q: could you potentially make a linked list with nodes that contain both a "next" pointer and a "previous" pointer, so you could traverse both ways?
A1: Yes, you can!
A2: Yup, definitely possible
Q: We implemented RingBufferQueue in section. Would a LinkedList be more efficient/better than RingBufferQueue?
A1: live answered
A2: They both have O(1) enqueue/dequeue, so comparable runtimes for the major operations
A3: It would be a different style of implementation, both might have their benefits
Q: Is this how deques are implemented?
A1: live answered
A2: Yes, this would be a good way to implement a deque (would likely need a doubly linked list though)
Q: adding in the middle is O(n)?
A1: Yes, because of the need to traverse to the middle
Q: What if there are multiple elements with the same value? How would we know where to insert?
A1: live answered
A2: we donât really have nay constraints or ordering on the things include in the list right now so that would be possible
Q: Wouldnât a doubly linked list outperform the singly linked list here because we can immediately get the previous element? And then proceed to insert or enqueue?
A1: live answered
A2: Not really, you still have to traverse the list to find the thing to remove
Q: is there any way to know the size of the linked list or will you only be able to determine the size by traversing through the whole list?
A1: You could track a separate counter to avoid the need to count
Q: just to clarify, the name of the pointers are the integers and the âvalueâ is the int pointing to the ânextâ int?
A1: live answered
A2: the pointers are pointing to instances of the struct, which contains an integere value and a next pointer (pointing to another instance of the struct
Q: Is the fact that you can define a pointer to a struct you haven't defined within that struct because pointers are the same size internally regardless of the type they point to?
A1: live answered
Q: How does the ânewâ in Tower *head = new Tower; work?
A1: New allocates enough memory on the heap for a tower object, and returns the address to the beginning of this segment on memory
Q: Temp is on the heap?
A1: temp is a pointer variable on the stack, it holds the address of a memory location in the heap
Q: Are pointers always on the stack?
A1: The pointer variable is on the stack, but the address it holds is generally a location in the heap
Q: How does memory management work with linked lists? If we remove elements, do we have to be careful to free as needed?
A1: Yes, you should always free the memory that you allocate!
A2: Each new that allocates a piece of memory must be balanced by a delete to return it to be recycled
Q: can you create a tower on the stack by just declaring Tower with a variable name? ie do you need to free memory for structs
A1: You can declare a struct aas a local variable on stack (not: struct not struct pointer), All local variables are automatically deallocated when you leave the function, so this variable would not exist once function returns
Q: wait why isnt it temp->next = next.next?
A1: This would skip over the next tower and make tempâs next tower equal to the next tower of the next variable
Q: Oh wait nvm
Q: so head points to the newest station?
A1: Correct
Q: what part of the code changed where head is pointing to?
A1: head = createTower(âŚ)
A2: in main when he wrote head = ⌠this changes what head points to
Q: It doesn't matter if you attatch the star to the type or the variable name right?
A1: Correct
Q: with all this heap memory, how are we returning the memory?
A1: We have not done any deallocation yet!
Q: could you also add things to the tail of the linked list in a similar way?
A1: Yes, you could attach the cell to be ânextâ of the previous tail
Q: why canât we pass in head by reference and then set it equal to temp at the end of createTower()
A1: That could also work
Q: why do you put in a Tower* next parameter for createTower() if every time you call it, the next is always head?
A1: This makes it generalizable, so if he wanted to pass in something other than the head, he could
Q: like why is that parameter necessary
A1: Without that parameter, you would not know which list you are prepending onto
Q: Why do you check start instead of start->next?
A1: live answered
Q: Why do we have to use a temp pointer? Why canât we change the head directly? In the signal function, how does the recursive call ultimately pass a Tower rather than the next since we are pointing start->next?
A1: live answered
Q: when you remove a node at the end of a linked list, donât you have to find the previous node and set its pointer equal to nullptr? If so, isnât that O(n) because you have to traverse through to find that previous node?
A1: You are correct. If your list were double-linked, you could avoid the need to traverse
Q: can you pass a pointer by reference?
A1: Yes, you can
Q: Why is assigning a pointer called dereferecning?
A1: live answered
Q: Can you go over how the recursive call ultimately passes a Tower rather than the next since we are pointing start->next
A1: live answered
Q: in the code for IntQueue, are the pointers pointing from tail to head direction? (opposite of the diagrams earlier in the lecture)
A1: live answered
Q: in the signal function
Q: Why do you need the * next to createTower?
A1: That indictes that createTower returns a pointer
Q: for the check in with our section leader we are supposed to use the IG signup correct? And if there is nothing there yet there should be something soon?
A1: Correct
Q: in the current createTower, doesnât the code change the value pointed at by head? So if we already had the pointer where the function is called, why is it necessary to return head?
A1: live answered
Q: Where do we say what temp is?
A1: On line 19 Tower * temp = head
Q: this is unrelated to the lecture, but where will assessment grades be posted?
A1: live answered
Q: Can you explain line 22?
A1: live answered
Q: What is the purpose of temp in IntQueue::dequeue()?
A1: live answered
Q: why is line 27 not start -> next != nullptr?
A1: live answered
Q: Couldnât you just say _front = _front->next without creating temp?
A1: live answered
Q: what does line 19 do?
A1: live answered
Q: can u explain line 21 again
A1: live answered