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

```four
```

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

```class LinkedList(object):
self.count = 0

def get_count(self):
return self.count

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

def find(self, val):
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
return
else:
tempIdx = 0
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):
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()
```

```Node:  15
Node:  13
Node:  49
Node:  38
Item count:  4
Finding item:  ```

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

```[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)
```

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

```{'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)
```

```{
'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

# otherwise get the first item and call function
# again to operate on the rest of the list
op1 = items
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))
```

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

## Conclusion:

Beginners have to get familiar with different kinds of data structures to survive the tech world. These are the four most common and most used data structures that senior developers reference to when developing softwares or applications.
```