Resources for setting up Jupyter and linked lists

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

Videos

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

Other videos:

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

Readings

Spark Notes

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.

from Wikimedia Commons

from Wikimedia Commons

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

  1. Classes (documentation)
  2. Constructors in classes >> def __init__(self, x, y)
  3. 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

Node 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 [1] 
    ## 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" [2]
        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

##[1] https://www.tutorialspoint.com/python/python_classes_objects.htm
##[2] http://stackoverflow.com/questions/68282/why-do-you-need-explicitly-have-the-self-argument-into-a-python-method

Linked List

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()