CS Week 7 - Linked Lists

Question 1

pointer

Answer 1

a variable that contains a memory address

Question 2

Dynamically allocated array

Answer 2

an array whose size can change during runtime

Question 3

when a vector is created

Answer 3

–The class internally dynamically allocates an array with an initial size
–If the number of elements added to the vector exceeds the capacity, class with dynamically allocate a new array with an increased size
–Contents of the array are copied into the new larger array
–Each time the internal array is dynamically allocated, array’s location in memory will change
–Vector class uses a pointer to store the memory location of the internal array

Question 4

Vector insert/erase performance problem

Answer 4

For a vector with thousands of elements, a single call to insert() or erase() can require thousands of instructions and cause the program to run very slowly

Question 5

Linked list

Answer 5

consists of items that contain both data and a pointer - a link- to the next list item

Question 6

this pointer

Answer 6

when a class member function is called on an object, a pointer to the object is automatically passed to the member function as an implicit parameter

• Enables access to an object’s data members within the object’s class member functions

-A data member can be accessed using this and the member access operator for a pointer ->

-This pointer clearly indicated that an objects data member is being accessed, which is needed if a member function’s parameter has the same variable name as the data member

this-> dataMember

Question 7

Singly-linked list

Answer 7

a data structure for implementing a list ADT, where each node has data and a pointer to the next node

Question 8

head

Answer 8

singly-linked list’s first node

Question 9

tail

Answer 9

singly-linked list’s last node

Question 10

positional list

Answer 10

a list where elements contain pointers to the next and/or previous elements in the list

Question 11

null

Answer 11

a special value indicating a pointer points to nothing

Question 12

Append

Answer 12

inserts the new node after the list’s tail node

Appending to empty list: if list’s head pointer is null(empty), algorithm points the list’s head and tail pointers to the new node

Append to non-empty list: if the list’s head pointer is not null (not empty), algorithm points the tail node’s next pointer and the list’s tail pointer to the new node

Question 13

Prepend

Answer 13

inserts the new node before the list’s head node

Prepend to empty list-if the list’s head pointer is null (empty), algorithm points the list’s head and tail pointers to the new node

Prepend to non-empty list- if the list’s head pointer is not null (not empty), algorithm points the new node’s next pointer to the head node, and then points the list’s head pointer to the new node

Question 14

InsertAfter

Answer 14

inserts the new node after a provided existing list node

curNode is a pointer to an existing list node, but can be null when inserting into an empty list

Insert as list’s first node- if the list’s head pointer is null, algorithm points the list’s head and tail pointers to the new node

Insert after the list’s tail node- if the list’s head pointer is not null and curNode points to the list’s tail node, algorithm points the tail node’s next pointer and the list’s tail pointer to the new node

Insert in middle of list- if the list’s head pointer is not null and curNode does not point to the list’s tail node, algorithm points the new node’s next pointer to curNode’s next node, and then points curNode’s next pointer to the new node

Question 15

RemoveAfter

Answer 15

removes the node after the specified list node

Exiting node must be specified because each node in a singly-linked list only maintains a pointer to the next node

curNode parameter - existing node

Remove list’s head node- (special case) if curNode is null, algorithm points sucNode to the head node’s next node, and points the list’s head pointer to sucNode. If sucNode is null, the only list node was removed, so the list’s tail pointer is pointed to null (indicating list is now empty)

Remove node after curNode- if curNode’s next pointer is not null (a node after curNode exists), algorithm points sucNode to the node after curNode’s next node. Then curNode’s next pointer is pointed to sucNode. If sucNode is null, the list’s tail node was removed, so algorithm points the list’s tail pointer to curNode (the new tail node)

Question 16

Destructor

Answer 16

a special class member function that is called automatically when a variable of that class type is destroyed

Question 17

When a destructor is called

Answer 17

Using the delete operator on an object allocated with the new operator calls the destructor, in previous example

For an object that is not declared by reference or by pointer, the object’s destructor is called automatically when the object goes out of scope

Question 18

copy constructor

Answer 18

a constructor that is automatically called when an object of the class type is passed by value to a function and when an object is initialized by copying another object during declaration

Called with a single pass-by-reference argument of the class type, representing an original object to be copied to the newly-created object

MyClass (const MyClass& orgiObject);

use to not delete data twice

Question 19

deep copy

Answer 19

copy constructor makes a copy of all data members (including pointers)

Question 20

memberwise copy

Answer 20

opies each member using assignment: newObj.member1 = origObj.member1

happens if no copy constructor defined

Question 21

shallow copy

Answer 21

creating a copy of an object by copying only the data member’s values

Question 22

overloading the assignment operator

Answer 22

Implementation of the assignment operator iterates through each member of the source object

Each non-pointer member is copied directly from source member to destination member

For each pointer member, new memory is allocated, the source’s referenced data is copied to the new memory, and a pointer to the new member is assigned as the destination member

Question 23

destructor

Answer 23

a class member that is automatically called when an object of the class is destroyed, such as when the object goes out of scope or is explicitly destroyed as in delete someObj;

Question 24

copy constructor

Answer 24

another version of a constructor that can be called with a single pass by reference argument

Automatically called when an object is passed by value to a function, such as the function someFunction(MyClass localObject) and the call someFunction(anotherObj)

Automatically called when an object is initialized when declared such as MyClass classObj1 = classObj2;

Automatically called when an object is initialized when allocated “new” as in newObjPtr = new MyClass(classObj2);

Question 25

copy assignment operator

Answer 25

the assignment operator “=” can be overloaded for a class via a member function, known as the copy assignment operator

Overloads the built-in function “operator=”

The member function having a reference parameter of the class type and returning a reference to the class type

Question 26

rule of three

Answer 26

describes a practice that if a programmer explicitly defines any one of those three special member function, then the programmer should explicitly define all three

Question 27

the big three

Answer 27

destructor, copy constructor, copy assignment operator

Question 28

look over notebook and google doc