Topic 5 (Linked lists, Binary Trees)

• Single linked • Double linked • Circular linked

Header, pointer, node, tail

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

• 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.

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

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

.getNext() Accesses the first node

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

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.

The node at the top

Each parent can only have 2 children

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

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

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

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.

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.

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)

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

• 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

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.