Originally posted on myblog

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:  

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}

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