These are data structures programmers are expected to at least know about. While we don't implement them directly, they are the building blocks of many algorithms. Let's look at what they are, and how they work.
A stack is kind of like an Array, but more resembles a stack of things in real life. You can plop things onto them and pop things off and that's it. It's LIFO. Last in first out. It's the opposite of how you want to stock a restaurant. It's more like a stack of plates.
Let's look at a Stack implemented in Python
class myStack:
def __init__(self):
self.container = []
def isEmpty(self):
return self.container.size() == 0
def push(self, item):
self.container.append(item)
def pop(self):
return self.container.pop()
def size(self):
return len(self.container) Pretty strait forward. We can use and array, and just implement our own API for stack-things.
BUT WHY???
Arrays are flexible and that can be great! But what if you have important data that will always and forever be last in first out? If you actually want to restrict the manner in which thing go in and out to LIFO of your list, a stack might be the way to go.
Examples of good uses for Stacks:
- The back button going through your browser history
- Reversing a string
- Call stacks like the JavaScript call stack, which keeps track of functions which call functions, and the order of execution of nested function calls
It is more obvious what a queue is and why it would be used. The are FIFO, like a line for a movie. Uses of queues include:
- Background jobs like sending emails
- Delegating tasks to CPUs
- Almost anything that needs to be done in order
Let's look at a Stack implemented in Python
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)Linked Lists are actually the data structure that all of the above depend on! Woah.
They are how your list stays together! They consist of nodes, or specifically, objects in OO Programming languages.
These nodes generally have two attributes:
- One that holds data. This data can be a character, string, stack, queue, another object, or another linked list. It can be anything.
- A reference to another node, the "next" node, often in the form of the actual address in memory.
- In doubly linked list, they also have a reference to the "previous" node.
These nodes make up a Linked List which can be added to, or removed from
Let's look at an implementation of a Doubly Linked List in Python
class Node :
def __init__( self, data ) :
self.data = data
self.next = None
self.prev = None
class LinkedList :
def __init__( self ) :
self.head = None
def add( self, data ) :
node = Node( data )
if self.head == None :
self.head = node
else :
node.next = self.head
node.next.prev = node
self.head = node
def search(self, k):
p = self.head
if p is not None:
if p.data == k:
return p
while p.next is not None:
if p.data == k:
return p
p = p.next
return None
def remove( self, p ) :
tmp = p.prev
p.prev.next = p.next
p.prev = tmp 
Tries are important in IP Routing and Autocomplete. It's great for when you have partial data and want to narrow down what is missing.
These are a bit more complicated but can be implemented in <100 lines of code Check out this great article on implementing a trie in Python!