|
Posted: October 27, 2009, 10:53 PM |
|
Just messin' around with different data structures!
1. Linked List
A Linked List is a type of data structure where each piece of data is connected to the next piece of data in a list. Sort of like a series of train carts, where the front is connected to the cart behind it. It's a good alternative to arrays in the sense that it's dynamic, and allows memory to expand without having to resize the array storage. However, this also leaves it incredibly linear.
# LinkedList
# Linked implementation of a basic list
# Each node is connected to a reference to another node
class Node(object):
def __init__(self, data=0, nextNode=None):
self.data = data
self.next = nextNode
def getNext(self):
return self.next
def getData(self):
return self.data
def setNext(self, nextNode=None):
self.next = next
def setData(self, data=0):
self.data = data
def __str__(self):
return str(self.data)
class LinkedList(object):
def __init__(self, data):
self.start = Node(data)
self.count = 1
def addNode(self, data):
self.start = Node(data, self.start)
self.count+=1
def __str__(self):
current = self.start
temp = ""
i = 0
for x in range(self.count):
temp += "\n" + str((i+1)) + ": " + str(current)
current = current.getNext()
i+=1
return temp
test = LinkedList(5)
test.addNode(3)
test.addNode(15)
test.addNode(16)
test.addNode(1234)
print test
Resulting code:
1: 1234
2: 16
3: 15
4: 3
5: 5
2. Binary Tree
Continuing upon Linked Lists, this is a bit of an expansion. Instead of connecting to one piece of data, each data piece will be able to connect to two different types of data pieces. Think of a binary tree like a flow chart, where you have two options, and following one of those choices leads to a series of other choices.
# Binary Tree
# Similar to the linked list, except connects to parts
# Each junction either stores two other junctions, or no junctions
class Tree(object):
def __init__(self, data=0, left=None, right=None):
self.data = data
self.left = left
self.right = right
def getData(self):
return self.data
def getLeft(self):
return self.left
def getRight(self):
return self.right
def __str__(self):
return str(self.data)
def total(tree):
if tree is None:
return 0
return total(tree.left) + total(tree.right) + tree.data
tree1 = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, Tree(6), Tree(7)))
print "Total of the tree is " + str(total(tree1))
