Topic 5 (Linked lists, Binary Trees)

Question 1

3 types of linked lists

Answer 1

• Single linked
• Double linked
• Circular linked

Question 2

What are linked lists composed of?

Answer 2

Header, pointer, node, tail

Question 3

What does each node contain? (does not apply to doubly linked list)

Answer 3

• An information field (the data itself)
• Pointer (Points to the memory address of the next node in the LinkedList)

Question 4

How to draw single linked list

Answer 4

Draw the nodes out (info field + pointers)
Draw the head (first pointer that points to the first node)
- Draw the tail (last pointer that points to null from the last node)

Question 5

Circular linked list what is it

Answer 5

It’s basically the same as a single linked list except the tail points back to first node

Question 6

Doubly linked list

Answer 6

Each node contains 3 components.

Previous, Information Field, Next

You can move back and forth in the list

Otherwise, it is the same as a single linked list

Question 7

The head is synonymous to which Collections method?

Answer 7

.getNext()

Accesses the first node

Question 8

Traversing linked list how it works for each list

Answer 8

Singled linked list:
You can only move forward and it ends at the last node

Circular linked list:
You can only move forward however the list repeats itself

Doubly linked list:
You can move forward and backward however the list can end

Question 9

How to add a node into a linked list

Answer 9

Find the 2 nodes where you want to enter the new node between. Imagine a sandwich.

The node on the left should now point to the new node’s memory address and the the new node points to the memory address of the node on the right.

Question 10

Root node in a binary tree

Answer 10

The node at the top

Question 11

Parent and child rules in a binary tree

Answer 11

Each parent can only have 2 children

Question 12

How to build a binary tree with a list of numbers

Answer 12

First number in list becomes the root node, then if the next number is bigger than the root, it turns into a right child, if it’s less it it turns into a left child. Then, from here you know

Question 13

Deleting nodes from a binary tree

Answer 13

Delete the node, then just make the connections between parent and child of the remaining nodes still make sense according to binary tree rules

Question 14

On this whole condition checking thing in binary trees we always base it off the what?

Answer 14

Parent node, whether that be the root node or a subset of leaves

Question 15

Trick for doing pre order traversal binary tree

Answer 15

Draw a line with a ball pointing to the left from each node.

e.g.
🔴–7

Now, start at the top left node based on the line and traverse through the binary tree whilst sticking to the top left rule.

Question 16

Trick for doing in order traversal binary tree

Answer 16

Draw a line with a ball pointing down from each node.

e.g.
7
I
🔴

Now, start at the top left node based on the line and traverse through the binary tree whilst sticking to the top left rule.

Question 17

Trick for doing post order traversal binary tree

Answer 17

Draw a line with a ball pointing to the right from each node

e.g.
7–🔴

Follow the top left rule but do not skip any nodes (so you kinda have to go under and around the tree)

Question 18

1 pro and 1 con of a binary tree

Answer 18

• Efficient searching and sorting (algorithm essentially halves the remaining trees every time)
• Needs to be “balanced”

Question 19

2 examples of where circular linked lists are used

Answer 19

• A media playlist that repeats endlessly
• When multiple applications are running in a PC. A circular linked list is used to go through each application in use in a circular order and given an equal share in processing power

Question 20

Difference between dynamic and static data structure

Answer 20

Static data structures are allocated at compile-time with a fixed size, while dynamic data structures are allocated at runtime and can change in size.