# Linked lists & Binary Trees

Linked Lists and Binary Trees are an essecial part of programming. As these data structures make our code run a lot faster and gives us more capabilities. The best example of this would be an autocomplete function, in which you put in the first few letters of a word, and are given a suggestion as to what word it thinks you might be typing. If this was done with a regular array of letters as opposed to a Binary Tree, then the run time would be unbarible. You would be waiting a long time for a suggestion that not only might be wrong, but will take away from the rest of your computers efficiency. As a coder, we love efficiency! So lets waste no time on introductions and jump right into how to build one, and how they work!

Linked Lists and Binary Trees are made up of one very important element known as a Node. A Node is kinda like a bucket that holds our information inside of it, along with instructions as how to get to it’s next destination. Linked List and Binary Trees are not built in functions of python, unlike dictionaries and arrays. So we will have to build our own using class objects.

`#!python3#Node exampleclass Node():    def __init__(self, data):       self.data = data       self.pointer = Nonenode1 = Node('1')`

Nodes can contain multiple pointers, and in a Double Linked List require directions for both the next node and before it. We can set those directions to assign the order of our Linked List as seen below. The code below goes over how to build a Double Linked List and some of it’s basic methods.

`#!python3#Double Linked list exampleclass Node():    def __init__(self, data):      self.data = data      self.next = None      self.previous = Noneclass double_ll(object):   def __init__(self):     self.head = None     self.tail = None   # creates our linked list methods   def append(self, item):     # creates a node to add to the END of our list     new_node = Node(item)     # Check if this linked list is empty     if self.head is None:       # Assign head to new node       self.head = new_node       # sets previous to none, as it is the beggining of the list                      new_node.previous = None     # Otherwise set previous as tail & insert new node after tail      else:       new_node.previous = self.tail       self.tail.next = new_node     # Update tail to new node regardless     self.tail = new_node    def prepend(self, item):      # Create a new node to add to the BEGINNING of our list      new_node = Node(item)      if self.head is None: # if empty make head new node        self.head = new_node        self.tail = new_node      else: # otherwise set new node to head        new_node.next = self.head        new_node.previous = None        self.head = new_node    def delete_from_tail(self):      # Delete the last item in the linked list      current = self.head      # Searches for the end of our double linked list      while current != None:        if current.next == self.tail:          break      # focus on the node right before the tail      current = current.next      """you can't really delete items in a linked list so we remove access to it completely, and therefore have removed it from the list"""      current.next = None      current.previous = None      self.tail = current    def delete_from_head(self):      second = self.head.next      second.previous = None      self.head = sencond    """ And becuase we have created a double link list, we can traverse through it forwards and backwards! """    def forward_print(self):      current = self.head      while current != None:        print(current.data)        current = current.next    def backward_print(self):      current = self.tail      while current != None:        print(current.data)        current = current.previous`

Despit Double Linked Lists being a bit more work to make, they can be very useful! Learning how to create Linked Lists can help you create stacks and queues for recursive functions. “But Anthony!”, I hear you asking, “what’s the difference between a Single Linked List and a Double?”. Simply put, a Single Linked List has only one direction it’s going in, while a Double Linked List goes both ways. I drew a demonstration below (sorry for the sloppy handwriting).

The circles represent our nodes, that are holding ints as data. The node.next defines the next node’s objects id in our list, which helps our list find it’s way to our second node -which is holding the data of 2. A node.previous is added, as to go the other direction in our Double Linked List. Just as the tail points to None, so will our node.previous when at the beginning of the list.

The second reason I explained a Double ll, rather than a Single, is because we can use two different directions to our advantage -when creating a Binary Tree. There is no .next or .previous attribute. However, there is a .left and .right attribute. We will use these in order to build our tree, and give or nodes instructions on where we would like it to go. So grab some tea and take a deep breath before jumping into our next large section of code.

`#!python3# Binary Tree Exampleclass Node:   def __init__(self, data):     self.data = data     # left and right attributes     self.left = None     self.right = None# creating our nodesnode1 = Node(4)node2 = Node(2)node3 = Node(6)node4 = Node(1)node5 = Node(3)node6 = Node(5)# building our treeroot = node1node1.left = node2node1.right = node3node2.left = node4node2.right = node5node3.left = node6# search the treedef search(node, target):  if node is None: # checks if there are no items left to search    return None  elif node.data == target: # checks if the node is our target    return node  elif node.data < target: # go right    return search(node.right, target)  else: # go left    return search(node.left, target)"""The function will recursively calls itself and check if the value is higher or lower then what we are looking for. For example, we call the function looking for 5. The funcion will figure out that our root node(node1.data == 4) is too small, and therefore go right as a result. Then when it reads our node3.data, it will determine that it is less than 6, and go left as a result. Finally finding 5, and returning the result."""result = search(root, 5)# now lets insert a new node into our treenode7 = Node(7)def insert(node, new_node):  if new_node.data > node.data:    # put new child on right if space    if node.right is None:      node.right = new_node      return    # otherwise keep looking    else:      insert(node.right, new_node)  if new_node.data < node.data:    # put new child on the left if space    if node.left is None:      node.left = new_node      return    # otherwise keep looking    else:      insert(node.left, new_node)"""Here we created a Node with the value of 7. This function will recursively call itself until it finds an open spot for 7 -that makes sense in the database. Simularly to our search funtion, it will check -if it cannot find an empty space for our node- if our node's value/data belongs on the left or right side based on how big it is. You can choose any node to try and insert to, but for this example we have used the root node to cycle threw the entire tree."""insert(root, node7)insert(root, Node(8))def delete(node, target):  result = search(node, target - 1)  if result.left == target:    result.left = None  elif result.right == target:    result.right = None  # does a second search to try and find a parent node  result = search(node, target + 1)  if result.left == target:    result.left = None  elif result.right == target:    result.right = None  # else, we print a not found response  else:    print(f"Could not find {target} in Tree.")"""Here we take advantage of our search function in order to find the previous node. Becuase we are trying to delete 8, we have to look for the node with a value of 7. Note that if we were looking for 5, we would have to look for the parenting node, with a value of 6. As well, this example only works for integer based binary trees."""delete(root, 8)# Finally we can print our tree out.def in_order_traversal(node):  if node is not None:    #traverse    in_order_traversal(node.left)    print(node.data)    in_order_traversal(node.right)   else:    return Nonein_order_traversal(root)`

And this is what our Tree should look like after it is all said and done. (apologies again for the bad handwriting)

And now a pretty picture to relax your eyes!

I know looking at so much text and code can be sore for eyes. Please comment on any questions you might have, and if there’s anything I can do to improve this explanation! But most importantly, happy coding, and have a great day!

--

--

## More from Anthony S. Protho

I code to create. I code to be challenged. I code for Fun. Software Engineer, New Grad

Love podcasts or audiobooks? Learn on the go with our new app.

## Anthony S. Protho

I code to create. I code to be challenged. I code for Fun. Software Engineer, New Grad