Common Data Structures

July 29, 2019  

1.) Arrays - A collection of elements identified by an index or a key

example:

ex_arr = [1, 'string', 3, 'four']
print(ex_arr[3])

Answer:


four

2.) Linked Lists - A collection of data elements, called nodes that contain reference to the next node in the list and holds whatever data the application needs

example:


Linked list example

the Node class

class Node(object):
def init(self, val):
self.val = val
self.next = None

def get_data(self):
    return self.val

def set_data(self, val):
    self.val = val

def get_next(self):
    return self.next

def set_next(self, next):
    self.next = next

the LinkedList class

class LinkedList(object):
def init(self, head=None):
self.head = head
self.count = 0

def get_count(self):
    return self.count

def insert(self, data):
    new_node = Node(data)
    new_node.set_next(self.head)
    self.head = new_node
    self.count += 1

def find(self, val):
    item = self.head
    while (item != None):
        if item.get_data() == val:
            return item
        else:
            item = item.get_next()
    return None

def deleteAt(self, idx):
    if idx > self.count:
        return
    if self.head == None:
        return
    else:
        tempIdx = 0
        node = self.head
        while tempIdx < idx-1:
            node = node.get_next()
            tempIdx += 1
        node.set_next(node.get_next().get_next())
        self.count -= 1

def dump_list(self):
    tempnode = self.head
    while (tempnode != None):
        print("Node: ", tempnode.get_data())
        tempnode = tempnode.get_next()

create a linked list and insert some items

itemlist = LinkedList()
itemlist.insert(38)
itemlist.insert(49)
itemlist.insert(13)
itemlist.insert(15)

itemlist.dump_list()

exercise the list

print(“Item count: “, itemlist.get_count())
print(“Finding item: “, itemlist.find(13))
print(“Finding item: “, itemlist.find(78))

delete an item

itemlist.deleteAt(3)
print(“Item count: “, itemlist.get_count())
print(“Finding item: “, itemlist.find(38))
itemlist.dump_list()

Answer:


Node: 15
Node: 13
Node: 49
Node: 38
Item count: 4
Finding item: <main.Node object at 0x106568990>
Finding item: None
Item count: 3
Finding item: None
Node: 15
Node: 13
Node: 49

3.) Stacks and Queues

  • Stacks is a collection of operation that supports push and pop operations. The last item pushed is the first one popped.

example:


# create a new empty stack
stack = []

# push items onto the stack
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)

# print the stack contents
print(stack)

# pop an item off the stack
x = stack.pop()
print(x)
print(stack)

Answer:

[1, 2, 3, 4]
4
[1, 2, 3]
  • Queue is a collection that supports adding and removing items. It operates on a first in first out method.

example:

from collections import deque

# create a new empty deque object that will function as a queue
queue = deque()

# add some items to the queue
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)

# print the queue contents
print(queue)

# pop an item off the front of the queue
x = queue.popleft()
print(x)
print(queue)

Answer:

deque([1, 2, 3, 4])
1
deque([2, 3, 4])

4.) Hash Tables (Dictionary)

  • A data structure that maps keys to its associated values
    Benefits:
  • Key-to-value maps are unique
  • Hash tables are very fast
  • For small datasets, arrays are usually more efficient
  • Hash tables don’t order entries in a predictable way

example:


# demonstrate hashtable usage


# create a hashtable all at once
items1 = dict({"key1": 1, "key2": 2, "key3": "three"})
print(items1)


# create a hashtable progressively
items2 = {}
items2["key1"] = 1
items2["key2"] = 2
items2["key3"] = 3
print(items2)

# replace an item
items2["key2"] = "two"
print(items2)

# iterate the keys and values in the dictionary
for key, value in items2.items():
    print("key: ", key, " value: ", value)

Answer:

{'key1': 1, 'key2': 2, 'key3': 'three'}
{'key1': 1, 'key2': 2, 'key3': 3}
{'key1': 1, 'key2': 'two', 'key3': 3}
key:  key1  value:  1
key:  key2  value:  two
key:  key3  value:  3

Real World Examples:

1.) Hash Tables

Filter out duplicate items


define a set of items that we want to reduce duplicates

items = [“apple”, “pear”, “orange”, “banana”, “apple”,
“orange”, “apple”, “pear”, “banana”, “orange”,
“apple”, “kiwi”, “pear”, “apple”, “orange”]

create a hashtable to perform a filter

filter = dict()

loop over each item and add to the hashtable

for item in items:
filter[item] = 0

create a set from the resulting keys in the hashtable

result = set(filter.keys())
print(result)

output:


{‘kiwi’, ‘apple’, ‘pear’, ‘orange’, ‘banana’}

Find a maximum value


declare a list of values to operate on

items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53]

def find_max(items):
# breaking condition: last item in list? return it
if len(items) == 1:
return items[0]

# otherwise get the first item and call function
# again to operate on the rest of the list
op1 = items[0]
print(op1)
op2 = find_max(items[1:])
print(op2)

# perform the comparison when we're down to just two
if op1 > op2:
    return op1
else:
    return op2

test the function

print(find_max(items))

output:


6
20
8
19
56
23
87
41
49
53
53
53
87
87
87
87
87
87
87

# define a set of items that we want to count
items = ["apple", "pear", "orange", "banana", "apple",
         "orange", "apple", "pear", "banana", "orange",
         "apple", "kiwi", "pear", "apple", "orange"]

# create a hashtable object to hold the items and counts
counter = dict()

# iterate over each item and increment the count for each one
for item in items:
    if item in counter.keys():
        counter[item] += 1
    else:
        counter[item] = 1

# print the results
print(counter)

output:


{‘apple’: 5, ‘pear’: 3, ‘orange’: 4, ‘banana’: 2, ‘kiwi’: 1}

Buy me a beer Buy me a beer