3 DYNAMIC DATA STRUCTURES

Question 1

What are dynamic data structures?

Answer 1

Dynamic data structures alter their structure as the data changes.

Question 2

How do dynamic data structures differ from static data structures?

Answer 2

Dynamic data structures can grow in size and adapt to changes, while static data structures have a fixed size.

Question 3

What is an example of a static data structure?

Answer 3

Array.

Question 4

What is an example of a dynamic data structure?

Answer 4

Linked list.

Question 5

What limitation do arrays have?

Answer 5

Their size and layout in memory are fixed at the time of creation.

Question 6

What must be done to extend an array’s size?

Answer 6

Create a new, larger array and copy the data from the old array.

Question 7

What is array doubling?

Answer 7

A strategy where the size of an array doubles whenever it is expanded.

Question 8

What is the cost of adding an element to a full array?

Answer 8

Allocate a new block of memory, copy the old values, and insert the new value.

Question 9

What happens when inserting an element in the middle of a full array?

Answer 9

Existing elements must be shifted to create space for the new value.

Question 10

What is a pointer?

Answer 10

A variable that stores the address in memory of another variable.

Question 11

What can a pointer indicate if it is not pointing to a valid memory location?

Answer 11

A null value (None, Nil, or 0).

Question 12

What is a linked list composed of?

Answer 12

A chain of nodes linked together by pointers.

Question 13

What are the two parts of a basic node in a linked list?

Answer 13

• Value of any type
• Pointer to the next node

Question 14

How do linked lists compare in memory usage to arrays?

Answer 14

Linked lists require more memory than arrays because they store pointers in addition to values.

Question 15

What does the null value at the end of a linked list indicate?

Answer 15

The end of the list.

Question 16

True or False: Arrays can easily insert new values in the middle.

Answer 16

False.

Question 17

What is the cost of using a fixed-size array in terms of operations?

Answer 17

Expensive operations for resizing and shifting elements.

Question 18

What analogy is used to describe the limitations of arrays?

Answer 18

A heated hotel buffet counter with a fixed number of slots.

Question 19

Fill in the blank: A linked list can be visualized as a series of ______ linked by pointers.

Answer 19

nodes

Question 20

What does each node in a linked list point to?

Answer 20

The next node in the list.

Question 21

What is the primary benefit of using dynamic data structures?

Answer 21

They can grow and adapt as new data is added.

Question 22

What is a linked list?

Answer 22

A data structure consisting of nodes that are linked via pointers.

Question 23

Why do linked lists require more memory than arrays?

Answer 23

Because they store both pointers and values, leading to a higher memory cost.

Question 24

How is the memory cost calculated for a linked list?

Answer 24

K × (M + N) bytes, where K is the number of nodes, N is the size of each value, and M is the size of each pointer.

Question 25

What is the head of a linked list?

Answer 25

The first node in the linked list that allows traversal of the list.

Question 26

What is the time complexity of accessing an element in a linked list?

Answer 26

O(n), as it requires iterating through nodes from the head.

Question 27

True or False: Linked lists allow for dynamic memory allocation.

Answer 27

True.

Question 28

What is the advantage of linked lists over arrays?

Answer 28

They allow for dynamic rearrangement of data without needing contiguous memory.

Question 29

What happens when inserting a new element into an array?

Answer 29

It may require reallocating memory and shifting elements.

Question 30

What is the process of inserting a new node at the front of a linked list?

Answer 30

Set the new node's next pointer to the current head and update the head pointer.

Question 31

Fill in the blank: Linked lists have a higher computing overhead than ______.

Answer 31

arrays.

Question 32

What is the code structure for inserting a node after a specific node in a linked list?

Answer 32

new_node.next = previous.next; previous.next = new_node.

Question 33

How do you delete a node from a linked list?

Answer 33

Adjust the previous node's pointer to skip the node to be deleted.

Question 34

What is the special case when deleting the first node in a linked list?

Answer 34

Update the head pointer to the next node.

Question 35

What should you do when the index for deletion or insertion is past the end of the list?

Answer 35

Return an error or handle it by appending to the end.

Question 36

What does the function LinkedListInsert do?

Answer 36

Inserts a new node at a specified index in the linked list.

Question 37

What is the main tradeoff when using linked lists?

Answer 37

Increased flexibility in data structure versus higher access overhead.

Question 38

What is the significance of the previous pointer during insertion in a linked list?

Answer 38

It allows updating the next pointer of the previous node to point to the new node.

Question 39

True or False: The nodes in a linked list must be stored in contiguous memory.

Answer 39

False.

Question 40

What happens to the next pointer of a deleted node in a linked list?

Answer 40

It is set to null to indicate it no longer has a next node.

Question 41

What is the time complexity for inserting an element into a linked list?

Answer 41

O(n) in the worst case due to traversal.

Question 42

What is the code structure for deleting a node at a specific index?

Answer 42

previous.next = current.next; current.next = null.

Question 43

Fill in the blank: Accessing an element in an array requires ______ lookup.

Answer 43

direct.

Question 44

What is the purpose of the count variable in linked list operations?

Answer 44

To track the position of the current node during traversal.

Question 45

What happens when the WHILE loop runs off the end of the list in the deletion function?

Answer 45

An error is thrown because there is nothing to delete.

Question 46

What does the function do with the removed node's next pointer?

Answer 46

Sets it to null to ensure consistency and allow memory management to free unused memory.

Question 47

How can we adapt the deletion code to use a node's value?

Answer 47

Update the loop condition to check for the first node with that value: WHILE current != null AND current.value != value.

Question 48

What is the primary advantage of linked lists?

Answer 48

They allow insertion or removal of elements without shifting other elements in memory.

Question 49

What is a doubly linked list?

Answer 49

A linked list that includes backward as well as forward pointers.

Question 50

What additional information does a doubly linked list store compared to a singly linked list?

Answer 50

Pointers to both the next and previous nodes.

Question 51

What is the structure of a DoublyLinkedListNode?

Answer 51

DoublyLinkedListNode { Type: Value, next: DoublyLinkedListNode, previous: DoublyLinkedListNode }.

Question 52

What advantage does a doubly linked list provide in terms of node access?

Answer 52

It allows access to the previous node without traversing the entire list.

Question 53

In what scenarios can arrays be used to store complex items?

Answer 53

When storing variable-size data like strings or composite data structures.

Question 54

How can arrays and pointers be combined to manage dynamic data?

Answer 54

Each array bin stores a pointer to the data of interest, allowing varying sizes.

Question 55

What is the main benefit of storing pointers in array bins?

Answer 55

It allows the data for each entry to vary in size and reside elsewhere in memory.

Question 56

What is the significance of using pointers in data structures?

Answer 56

They enable linking across blocks of memory and creating dynamically linked structures.

Question 57

What trade-offs should be considered when choosing data structures?

Answer 57

Flexibility, space requirements, efficiency of operations, and complexity.

Question 58

What are the two data structures that will be introduced in the next chapter?

Answer 58

Stacks and queues.

Question 59

Fill in the blank: A singly linked list can only traverse in _______.

Answer 59

one direction.

Question 60

True or False: The next pointers in a linked list can point to arbitrary blocks of data.

Answer 60

False.