Write a linked list class called LinkedList
. Remember, a singly linked list is made up of nodes each of which contain a value and a pointer. The first node is called the "head node".
Here are the required methods:
__init__(self, head)
where head
is the value of the head node. You could make the head node an attribute.__len__(self)
: Returns the number of elements in the linked list.__getitem__(self, index)
returns the value of the node corresponding to index
. Include checks to make sure that index
is not out of range and that the user is not trying to index and empty list.__repr__(self)
returns LinkedList(head_node)
.insert_front(self, element)
inserts a new node with value element
at the beginning of the list.insert_back(self, element)
inserts a new node with value element
at the end of the list.Note: An alternative implementation is to create a Node
class. You are not required to make a Node
class but you may if you prefer that implementation. Please don't steal that implementation from the online forums. I've seen those too.
A binary search tree is a binary tree with the invariant that for any particular node the left child is smaller and the right child is larger. Create the class BinaryTree
with the following specifications:
__init__(self)
: Constructor takes no additional arguments
insert(self, val)
: This method will insert val
into the tree
(Optional) remove(self, val)
: This will remove val
from the tree.
getValues(self. depth)
: Return a list of the entire row of nodes at the specified depth with None
at the index if there is no value in the tree. The length of the list should therefore be $2^{\text{depth}}$.
Here is a sample output:
bt = BinaryTree()
arr = [20, 10, 17, 14, 3, 0]
for i in arr:
bt.insert(i)
print("Height of binary tree is {}.\n".format(len(bt)))
for i in range(len(bt)):
print("Level {0} values: {1}".format(i, bt.getValues(i)))
Height of binary tree is 4.
Level 0 values: [20]
Level 1 values: [10, None]
Level 2 values: [3, 17, None, None]
Level 3 values: [0, None, 14, None, None, None, None, None]
Note that you do not need to format your output in this way. Nor are you required to implement a __len__
method to compute the height of the tree. I did this because it was convenient for illustration purposes. This example is simply meant to show you some output at each level of the tree.
Evaluate the members of your group for Milestone 1. Please follow the instructions in the provided survey. The survey can be found here: Milestone 1 Peer Evaluation.
Please take the Course Evaluation.