# 4 Common Data Structures

·

5 min read

Originally posted on my blog

# 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 a reference to the next node in the list and holds whatever data the application needs

### 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 operations that supports push and pop operations. The last item pushed is the first one popped.

### 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]
``````
• A Stack is a collection of operations that supports push and pop operations. The last item pushed is the first one popped.

### 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:

#### 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:

### 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'
}
``````

### 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}
``````