1.4.2 Data Structures

Question 1

What are the main differences between arrays and
lists?

Answer 1

• Lists can store data non-contiguously whereas arrays store data in order.
• Lists can store data of more than one data type.

Question 2

What is a linked list?

Answer 2

A dynamic data structure that is used to hold an ordered set of items that are not stored in contiguous locations.

Question 3

What is a pre-order traversal?

Answer 3

Traversal algorithm in which you traverse the root node, followed by the left subtree then the right subtree.

Question 4

What is in-order traversal?

Answer 4

Traversal algorithm in which you traverse the left subtree, the root node, then the right subtree.

Question 5

What is post-order traversal?

Answer 5

Traversal algorithm in which you traverse the left subtree, the right subtree followed by the root node.

Question 6

How to add data to a linked list?

Answer 6

1. Check if the linked list is full
2. Create a node and insert data into it
3. Find between what 2 nodes the data should be inserted
4. Make the previous node point to the current node
5. Make the current node point to the next node

Question 7

How to delete data from a linked list?

Answer 7

1. Check if the linked list is empty
2. Find the node to delete
3. Set the pointer of the previous node to point to the next node (node ahead of the node to be deleted)

Question 8

How to traverse a linked list?

Answer 8

1. Check if the linked list is empty
2. Start at the node the start pointer is pointing to
3. Output the item
4. Follow the pointer to the next item
5. Repeat from 3 till end of list is reached

Question 9

How to add data to a queue?

Answer 9

1. Check if the queue is full
2. Create a new node
3. Insert it into the tail pointer position
4. Increment the tail pointer`

Question 10

How to remove data from a queue?

Answer 10

1. Check if the queue is empty
2. Output node pointed by the head pointer
3. Increment the head pointer

Question 11

How to add data to a stack?

Answer 11

1. Check if the stack is full
2. Create a new node
3. Insert it into the pointer position
4. Increment the pointer

Question 12

How to remove data from a stack?

Answer 12

1. Check if the stack is empty
2. Output node in pointer position
3. Decrement pointer

Question 13

How to add data to a binary tree?

Answer 13

1. Check if there’s free memory for a new node
2. Create a new node and insert data into it
3. If tree is empty
   a. New node becomes the first item
4. If tree is not empty
   a. Start at root node
   b. If the new node is before current node, follow left pointer
   c. If the new node is after current node, follow right pointer
   d. Repeat from step 4b until leaf node is reached
   e. If new node is placed before current node, set left pointer to be the new node
   f. If new node is placed before current node, set right pointer to be the new node