The following resources are for the first meeting of the algorithms and data structures study group. For a full list of the study group activities, see the main blog post.
Setting up Jupyter
- Steps to install Jupyter notebook on your personal computer
- Using the anaconda version is really easy because it installs all of the scientific computing libraries you need with it
Resources for Linked Lists
I selected the following video as our main prompt for two reasons: 1) the visuals are clear, 2) there is an example of a linked list being implemented in python, and - I lied, there are three reasons - 3) the video maker's name is Joe James.
- coursera video (which also summarizes an abstract data type well)
- youtube query - if you find one you like better, let me know and I"ll add it to this post. If you make your own, let me know, I'll add it too.
A linked list is a data structure. Unlike an array that has to have one block of memory that isn't cut up, a linked list contains pointers from each piece of data to the next in memory so it can be scattered around. The wikipedia link has a really nice overview.
Potentially the most important concept to get here (for going forward at a conceptual level) is the "node." Each node consists of one data element and a pointer to the next data element. The node is a fundamental concept because it is built on to get to trees and graphs. Both abstract data types are important for geographic information science. Trees are used across various data access methods (see R-Tree for example), and graphs and their respective algorithms are the basis of all road networks, among other things.
The diagram below shows how a linked list stores data and a pointer to the next piece of data.
Note: the developers (Newell, Shaw, Simon) were all big time names in CS and artificial intelligence. Simon in particular is widely known across the cognitive sciences and won a Nobel Prize in Economics.
[02-15-17] Meeting Recap
More resources we discovered:
- Python documentation on classes
- Very clearly laid out blog post from Code Fellows (thanks Josh!)
- Code Fellows also referenced the book Problem Solving with Algorithms and Data Structures by Miller and Ranum
We met in Social Sciences 423 for a little over an hour. We watched the above video, and then implemented the node class, broke it, and discussed it. Then we started implementing the list class and started breaking it, but ran out of time to discuss it.
In addition to discussion the data structure, we also talked about general object oriented programming skills. Some of the things that we discussed were
- Classes (documentation)
- Constructors in classes >> def __init__(self, x, y)
- Why the linked list adds new nodes to beginning and not the end (From Josh: "hint: much more efficient... which is what our discussion was getting at")
[02-23-17] Meeting Recap
We met in the Brown Room in Social sciences. We completed implementing the linked lists from scratch and then started to implement the integrate function.
Implementation in Python
Jupyter notebook implementation. The following provides the node class and the linked list class
The following node class is a an object that holds (1) data and (2) a pointer to the next node.
class Node(object): ## Constructor: see  ## specifies the components of an object ## (the stuff to put in a box) def __init__(self, d, n = None): ## single underscore v double underscore in Python ## double = only used in this class ## (totally private variable or function) self.data = d self.next_node = n def get_next(self): ## great stackoverflow explaining use of "self"  return self.next_node def set_next(self, n): self.next_node = n def get_data(self): return self.data def set_data(self, d): self.data = d def __str__(self): print self.data print self.next_node ## https://www.tutorialspoint.com/python/python_classes_objects.htm ## http://stackoverflow.com/questions/68282/why-do-you-need-explicitly-have-the-self-argument-into-a-python-method
The linked list uses the node class, and connects a group of nodes with methods.
class LinkedList(object): def __init__(self, r = None): self.root = r self.size = 0 def get_size(self): return self.size def get_root(self): return self.root def add(self, d): ## the add function takes in data; ## it creates a new node; ## it then puts this data into a node; ## and appends the node to end of the linked list new_node = Node(d, self.root) self.root = new_node self.size += 1 ## the way this list works is it adds itself to the beginning ## and makes itself the root ## and adds itself as the root ## then it increments the list's size by 1 def remove(self, d): ## start by setting the root node as the first placeholder ## set the previous node to node because presumably the root is #1 this_node = self.root prev_node = None ## while this_node is true ## evaluate this_nodes data, if it matches ## and there is a previous node, set the previous node's ## next node to this_node's next node ## otherwise, just change the root if there isn't a previous node while this_node: if this_node.get_data() == d: if prev_node: prev_node.set_next(this_node.get_next()) else: self.root = this_node ## if this conditional was met, then the size ## will be one less and an object was found; return true self.size -= 1 return True else: ## if the previous conditional wasn't met, grab the next node ## and repeat the process prev_node = this_node this_node = this_node.get_next() ## if the while loop breaks with this_node = FALSE, ## then the data element did not exist in the list return false def find(self, d): this_node = self.root while this_node: if this_node.get_data() == d: ## if it matches, return data return d else: ## if nothing found, move onto the next node this_node = this_node.get_next() return None def reverse(self): #reverses the order of the linked list this_node = self.root reverse = LinkedList() while this_node: #starts with last node added (adds to front of list) reverse.add(this_node.get_data()) this_node = this_node.get_next() return reverse def integrate(self): ## returns the integral of the linked list this_node = self.root integrated = LinkedList() value = 0 while this_node: value = value + this_node.get_data() integrated.add(value) this_node = this_node.get_next() return integrated def print_data(self): this_node = self.root while this_node: print this_node.get_data() this_node = this_node.get_next()