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
examples:
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.
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]
- 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:
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
Counting Items
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}
Top comments (4)
Thanks your article was very insightful
Very useful article. Is very practical to review concepts and get the mind fresh instead of just use one of these data structures. Thanks for sharing.
Some comments may only be visible to logged-in visitors. Sign in to view all comments.