Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

SEM 6_COMPE 260 > MOD 3_ZYBOOKS 4_LISTS > Flashcards

MOD 3_ZYBOOKS 4_LISTS Flashcards

(100 cards)

Start Studying
1
Q

What is a list?

A

A list is a common ADT for holding ordered data, having operations like append a data item, remove a data item, search whether a data item exists, and print the list.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

For a given list item, after “Append 7”, “Append 9”, and “Append 5”, then “Print” will print…?

And “Search 8” would…?

A

Print (7, 9, 5) in that order

Would indicate item not found.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

VIEW: Some common operations for a list ADT.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

For lists, what do the following operations do?

1) Append(list, x)
2) Prepend(list, x)
3) InsertAfter(list, w, x)
4) Remove(list, x)
5) Search(list, x)

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

For lists, what do the following operations do?

1) Print(list)
2) PrintReverse(list)
3) Sort(list)
4) IsEmpty(list)
5) GetLength(list)

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is an array-based list?

A

An array-based list is a list ADT implemented using an array.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

T/F: An array-based list implementation will dynamically allocate the array as needed as the number of elements changes.

A

True.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How does an array-based list allocate size initially?

A

Initially, the array-based list implementation allocates a fixed size array and uses a length variable to keep track of how many array elements are in use. The list starts with a default allocation size, greater than or equal to 1. A default size of 1 to 10 is common.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

For an array-based list, what happens if an item is added when the allocation size equals the list length?

A

An array-based list must be resized if an item is added when the allocation size equals the list length. A new array is allocated with a length greater than the existing array. Allocating the new array with twice the current length is a common approach. The existing array elements are then copied to the new array, which becomes the list’s storage array.

Because all existing elements must be copied from 1 array to another, the resize operation has a runtime complexity of O(N).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What does the Prepend operation do for an array-based list?

A

The Prepend operation for an array-based list inserts a new item at the start of the list. First, if the allocation size equals the list length, the array is resized. Then all existing array elements are moved up by 1 position, and the new item is inserted at the list start, or index 0. Because all existing array elements must be moved up by 1, the prepend operation has a runtime complexity of O(N).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What does the InsertAfter operation do for an array-based list?

A

The InsertAfter operation for an array-based list inserts a new item after a specified index. Ex: If the contents of numbersList is: 5, 8, 2, ArrayListInsertAfter(numbersList, 1, 7) produces: 5, 8, 7, 2. First, if the allocation size equals the list length, the array is resized. Next, all elements in the array residing after the specified index are moved up by 1 position. Then, the new item is inserted at index (specified index + 1) in the list’s array. The InsertAfter operation has a best case runtime complexity of O(1) and a worst case runtime complexity of O(N).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does the Search operation do for an array-based list?

A

Given a key, the search operation returns the index for the first element whose data matches that key, or -1 if not found.

Both the search and remove operations have a worst case runtime complexity of O(N).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What does the Remove-at operation do for an array-based list?

A

Given the index of an item in an array-based list, the remove-at operation removes the item at that index. When removing an item at index X, each item after index X is moved down by 1 position.

Both the search and remove operations have a worst case runtime complexity of O(N).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What syntax is used for a class’s destructor function?

How is it implemented?

A

The syntax for a class’s destructor function is similar to a class’s constructor function, but with a “~” (called a “tilde” character) prepended to the function name.
A destructor has no parameters and no return value. So the LinkedListNode and LinkedList class destructors are declared as ~LinkedListNode(); and ~LinkedList();, respectively.

The LinkedList class destructor is implemented to free each node in the list. The LinkedListNode destructor is not required, but is implemented below to display a message when a node’s destructor is called. Using delete to free a dynamically allocated LinkedListNode or LinkedList will call the object’s destructor.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

C++’s vector type is implemented using an ____-based data structure

A

array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

VIEW: ArrayList class: declaration of private members and constructor.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

VIEW: Append() and Resize() functions.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

For array-based lists (classes), what do Append() and Resize() do?

A

Append() is implemented by inserting the new item at the index equal to the array’s current length. If the array is filled all the way to the allocation size, then the array is doubled in size first.

Resize() works by first creating a new array of the indicated size and then copying all the items in the current array to the new array. The arrayData data member is then reassigned with the new array and the allocation size is updated.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

For array-based lists (classes), what do the Prepend() and InsertAfter() functions do?

A

The Prepend() function shifts the entire contents of the array one index to the right. Shifting is accomplished by copying the last item to the next index, then copying the second-to-last item to the index previously occupied by the last index, and so on until the first item is copied to index 1.

To do the shifting, the loop must use the indices in reverse order, from the last item down to the first item. Ex: If a list’s length is 5, then the loop shifts by accessing indices 5, 4, 3, 2, 1, in that order. Since a new item is added to the list, the array is first checked to see if space is available, and resized if not.

The InsertAfter() function operates similarly to Prepend(). Items are shifted one space to the right, but only down to the provided index plus 1. All items from the given index down to 0 are not shifted, creating an empty space for the new item to be inserted into.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

VIEW: Prepend() and InsertAfter() functions.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

For array-based lists (classes), what do the Search() and RemoveAt() functions do?

A

The Search() function takes a target item as a parameter and then tests each item in the list, from index zero up to index arrayListLength - 1, for equality with the target item. The function returns the index where the first matching item is found, or -1 if no matching item exists in the array. The Search() function does not change the list’s length or the internal array’s allocation size.

RemoveAt() removes the item at the specified index by shifting the array items. The items from the parameter index plus 1 are shifted to the left by one index, up to the final item in the array. The RemoveAt() function decreases the list’s length (assuming the specified index is valid in the current list), but does not change the internal array’s allocation size.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

VIEW: Search() and RemoveAt() functions.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is a singly-linked list?

A

A singly-linked list is a data structure for implementing a list ADT, where each node has data and a pointer to the next node. The list structure typically has pointers to the list’s first node and last node.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

A singly-linked list’s first node is called the ____, and the last node the ____.

A

Head, tail

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
A singly-linked list is a type of ____ list. Explain what this type of list is.
Positional A list where elements contain pointers to the next and/or previous elements in the list.
26
The name used to represent a pointer that points to nothing include? (Hint: 5 variations of the same word)
27
What does the Append operation do for a singly-linked list?
Given a new node, the Append operation for a singly-linked list inserts the new node after the list's tail node. Ex: ListAppend(numsList, node 45) appends node 45 to numsList. The notation "node 45" represents a pointer to a node with a data value of 45. This material does not discuss language-specific topics on object creation or memory allocation.
28
How does the Append algorithm differ if the list is empty vs not empty?
29
What does the Prepend operation do for a singly-linked list?
Given a new node, the Prepend operation for a singly-linked list inserts the new node before the list's head node.
30
How does the Prepend algorithm differ if the list is empty vs not empty?
31
What does the InsertAfter operation do for a singly-linked list?
Given a new node, the InsertAfter operation for a singly-linked list 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.
32
The InsertAfter algorithm considers which 3 insertion scenarios?
33
What does the RemoveAfter operation do for a singly-linked list?
Given a specified existing node in a singly-linked list, the RemoveAfter operation removes the node after the specified list node. The existing node must be specified because each node in a singly-linked list only maintains a pointer to the next node.
34
For the RemoveAfter operation, the existing node is specified with the curNode parameter. If this parameter is null, RemoveAfter removes the list's ____ node. Otherwise, the algorithm removes the node ____ curNode.
Head, after
35
VIEW: The RemoveAfter operation.
36
In C++, ____ are used for both the linked list and the nodes that comprise the list.
Classes
37
Each class has pointers to nodes: pointer to the ____ node for the Node class and pointers to the ____and____ nodes for the LinkedList class).
Next, head and tail
38
The Node class implements a list node with which two members? If the node has no next node, the next data member is ____.
1) Data value 2) Next node in the list. null
39
The LinkedList class implements the list data structure and has which two private data members?
1) Head 2) Tail (Which are assigned to nodes once the list is populated)
40
Initially the list has no nodes, so both data members are initially ____.
null
41
VIEW: Node class definition for a singly-linked class.
42
VIEW: LinkedList class definition for a singly-linked list.
43
What does the LinkedList class' Append() member function do? What parameter does it take?
The LinkedList class' Append() member function adds a node to the end of the linked list, making the node the tail of the list. Append() has one parameter, which is the new node to be appended to the list.
44
VIEW: LinkedList Append() function and function call.
45
What does the LinkedList class' Prepend() member function do? What parameter does it take?
The Prepend() member function adds a node to the beginning of a linked list, making the node the head of the list. The function's parameter is the new node to be prepended to the list.
46
VIEW: LinkedList Prepend() member function.
47
What does the LinkedList class' InsertAfter() member function do? What parameter does it take?
48
VIEW: LinkedList InsertAfter() member function.
49
What does the LinkedList class' RemoveAfter() member function do? What parameter does it take?
The RemoveAfter() member function has a currentNode parameter and removes currentNode's successor (the node after currentNode) from the list. If a successor exists, currentNode's next value is assigned with the successor node's next value, thus removing the successor node from the list. The removed node is deallocated.
50
The LinkedList class' RemoveAfter() can also be used to remove the list's head node by?
passing nullptr as the currentNode argument.
51
VIEW: LinkedList RemoveAfter() member function.
52
The LinkedList class eventually deallocates any node added to the list. The ____ function deallocates the removed node. Any nodes left in the list when the LinkedList is destroyed are freed in the LinkedList class ____.
RemoveAfter(), destructor
53
VIEW: LinkedList class destructor.
54
For LinkedList classes, what is a destructor? What happens when there is no destructor?
A destructor is a special class member function that is called automatically when a variable of that class type is destroyed. C++ class objects commonly use dynamically allocated data that is deallocated by the class's destructor. Ex: A linked list class dynamically allocates nodes when adding items to the list. Without a destructor, the link list's nodes are not deallocated. The linked list class destructor should be implemented to deallocate each node in the list.
55
VIEW: LinkedList nodes are not deallocated without a LinkedList class destructor.
56
What causes a memory leak to happen?
A memory leak occurs when a program that allocates memory loses the ability to access the allocated memory, typically due to failure to properly destroy/free dynamically allocated memory. A common error is failing to free allocated memory that is no longer used, resulting in a memory leak.
57
VIEW: The LinkedList class destructor, called when the list is deleted, frees all nodes.
58
What happens when using the delete operator on an object allocated with the new operator?
Using the delete operator on an object allocated with the new operator calls the destructor, as shown in the 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.
59
VIEW: Destructors are called automatically only for non-reference/pointer variables.
60
What happens when there is a memory leak?
A program's leaking memory becomes unusable, much like a water pipe might have water leaking out and becoming unusable. A memory leak may cause a program to occupy more and more memory as the program runs, which slows program runtime. Even worse, a memory leak can cause the program to fail if memory becomes completely full and the program is unable to allocate additional memory.
61
What is Garbage Collection?
62
What is a copy constructor? Give an example.
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. Ex: MyClass classObj2 = classObj1; or obj2Ptr = new MyClass(classObj1);
63
What causes a destructor to fail in freeing up memory?
Destructors are needed when destroying an object involves more work than simply freeing the object's memory. Such a need commonly arises when an object's data member, referred to as a sub-object, has allocated additional memory. Freeing the object's memory without also freeing the sub-object's memory results in a problem where the sub-object's memory is still allocated, but inaccessible, and thus can't be used again by the program.
64
What is a deep copy?
The copy constructor makes a new copy of all data members (including pointers), known as a deep copy.
65
What happens if the programmer doesn't define a copy constructor?
If the programmer doesn't define a copy constructor, then the compiler implicitly defines a constructor with statements that perform a memberwise copy, which simply copies each member using assignment: newObj.member1 = origObj.member1, newObj.member2 = origObj.member2, etc.
66
What is a shallow copy?
Creating a copy of an object by copying only the data members' values creates a shallow copy of the object.
67
Is it better to use a shallow copy vs a deep copy?
A shallow copy is fine for many classes, but typically a deep copy is desired for objects that have data members pointing to dynamically allocated memory.
68
How is a copy constructor called? What is its parameter?
The copy constructor can be called with a single pass-by-reference argument of the class type, representing an original object to be copied to the newly-created object.
69
How may a programmer define a copy constructor?
A programmer may define a copy constructor, typically having the form: MyClass(const MyClass& origObject);
70
VIEW: Copy constructor.
71
VIEW: Problem solved by creating a copy constructor that does a deep copy.
72
What is the default behavior of the assignment operator (=) for classes? Is the behavior optimal/desired?
73
VIEW: Basic assignment operation fails when pointer member involved.
74
What can be done to the assignment operator (=) to eliminate problems caused by a memberwise assignment during an object copy? What is a deep copy?
The assignment operator (=) can be overloaded to eliminate problems caused by a memberwise assignment during an object copy. The 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. Allocating and copying data for pointer members is known as a deep copy.
75
VIEW: Assignment operator performs a deep copy.
76
Classes have which 3 special member functions that are commonly implemented together?
77
What is the rule of three?
The rule of three describes a practice that if a programmer explicitly defines any one of those three special member functions (destructor, copy constructor, copy assignment operator), then the programmer should explicitly define all three. For this reason, those three special member functions are sometimes called the big three.
78
VIEW: Rule of three.
79
What happens if the programmer doesn't define a destructor or copy constructor or copy assignment operator?
80
VIEW: LinkedListNode and LinkedList classes.
81
What is a doubly-linked list? How is it structured?
A doubly-linked list is a data structure for implementing a list ADT, where each node has data, a pointer to the next node, and a pointer to the previous node. The list structure typically points to the first node and the last node. The doubly-linked list's first node is called the head, and the last node the tail.
82
For a doubly-linked list, how does the Append operation work? How does it behave with an empty vs non empty list?
83
For a doubly-linked list, how does the Prepend operation work? How does it behave with an empty vs non empty list?
84
For a doubly-linked list, how is the InsertAfter operation defined/written?
85
For a doubly-linked list, how does the InsertAfter operation work?
Given a new node, the InsertAfter operation for a doubly-linked list inserts the new node after a provided existing list node. curNode is a pointer to an existing list node.
86
What are the 3 scenarios that the InsertAfter operation considers?
87
For a doubly-linked list, how does the Remove operation work?
The Remove operation for a doubly-linked list removes a provided existing list node. curNode is a pointer to an existing list node. The algorithm first determines the node's successor (the next node) and predecessor (the previous node). The variable sucNode points to the node's successor, and the variable predNode points to the node's predecessor.
88
For a doubly-linked list, what are the 4 things the Remove operation checks to update each pointer? What happens when removing a node in the middle of the list? What happens when removing the only node in a list?
89
For a doubly-linked list, how is the Remove operation defined/written?
90
For doubly-linked lists, how are classes implemented for both the linked list and the nodes that comprise the list?
91
Write a node class definition for a doubly-linked node.
92
Write a LinkedList class definition for a doubly-linked list.
93
Write a definition for a LinkedList Append() member function using doubly-linked nodes.
94
Write a definition for a LinkedList Prepend() member function using doubly-linked nodes.
95
For doubly-linked lists, how is the InsertAfter() member function implemented? What parameters does it take? Which 3 nodes does it affect?
96
Write a definition for a LinkedList InsertAfter() member function using doubly-linked nodes.
97
For doubly-linked lists, how is the Remove() member function implemented? What parameters does it take? Which nodes does it affect?
98
Write a definition for a LinkedList Remove() member function using doubly-linked nodes.
99
Discuss the different ways that memory is managed with linked lists.
100
What is a circular linked list? Describe how a circular linked list is traversed.
A circular linked list is a linked list where the tail node's next pointer points to the head of the list, instead of null. A circular linked list can be used to represent repeating processes. Ex: Ocean water evaporates, forms clouds, rains down on land, and flows through rivers back into the ocean. The head of a circular linked list is often referred to as the start node. A traversal through a circular linked list is similar to traversal through a standard linked list, but must terminate after reaching the head node a second time, as opposed to terminating when reaching null.

SEM 6_COMPE 260 (11 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions