Topic 5 (Linked lists, Binary Trees) Flashcards
3 types of linked lists
- Single linked
- Double linked
- Circular linked
What are linked lists composed of?
Header, pointer, node, tail
What does each node contain? (does not apply to doubly linked list)
- An information field (the data itself)
- Pointer (Points to the memory address of the next node in the LinkedList)
How to draw single linked list
- Draw nodes in order, each node should have 2 sections: Data, and a black dot (will be used for pointers)
- Draw the first pointer pointing to the first node from the left side, make sure it also has a circle and write “First” underneath it.
- In the last node, there is no pointer, rather replace the dot section with the word “null”
- Draw the other pointers going from one node to the next (left to right) and make sure to connect the base of the pointer to the dot of the node it is originating from.
Circular linked list what is it
It’s basically the same as a single linked list except the tail points back to first node
Doubly linked list
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
The head is synonymous to which Collections method?
.getNext()
Accesses the first node
Traversing linked list how it works for each list
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
How to add a node into a linked list
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.
Root node in a binary tree
The node at the top
Parent and child rules in a binary tree
Each parent can only have 2 children
How to build a binary tree with a list of numbers
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
Deleting nodes from a binary tree
Delete the node, then just make the connections between parent and child of the remaining nodes still make sense according to binary tree rules
On this whole condition checking thing in binary trees we always base it off the what?
Parent node, whether that be the root node or a subset of leaves
Trick for doing pre order traversal binary tree
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.
Trick for doing in order traversal binary tree
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.
Trick for doing post order traversal binary tree
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)
1 pro and 1 con of a binary tree
- Efficient searching and sorting (algorithm essentially halves the remaining trees every time)
- Needs to be “balanced”
2 examples of where circular linked lists are used
- 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
Difference between dynamic and static data structure
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.
