## Table of contents

Programming languages provide data types that represent the most basic units of data from which all other data types can be constructed. These are known as primitive data types and in most languages include string, integer, float and Boolean. However, when dealing with real world problems we are often forced to create our own data types that fit a certain use case. These are known as user-defined data structures as they are not provided out of the box by a programming language and can be implemented in any language.

They most common user-defined data-types are:

- Arrays: Similar to Lists, but store single type of elements
- Linked Lists: Linear data structures that are linked with pointers
- Queues: Linear FIFO (First-In-First-Out) data structure
- Stack: Linear LIFO (Last-In-First-Out) Data structure
- Trees: Non-Linear data structures having a root and nodes
- Graphs: Store a collection of points or nodes along with edges

They can be classified as linear (arrays, linked lists, stacks, queues) or non-linear (trees, graphs).

# 1. Arrays

Are the easiest user defined data structure and in most languages they can be implemented by creating an instance of an already defined arrays class and using already defined methods to manipulate the data contained in array.

# 2. Linked Lists

Linked lists are linear Data Structures that are linked together via pointers rather than being stored sequentially. A linked list node is made up of data and a pointer named next which points to the address of the next node. A great explanation for this can be found here. A simple python implementation of a linked list node would be:

```
class Node:
def __init__(self, data):
self.data = data
self.next = None
```

# 3. Queues

A queue is a linear data structure based on the First-In-First-Out (FIFO) principle. The data that comes in first will be accessed/leave first. It is constructed using an array structure and includes actions that can be performed from both the head and tail ends of the Queue. Enqueue is adding an element to the queue while dequeue is removing an element. A real life example would be thinking of a queue to get lunch at the school cafeteria. The person at the front of the queue gets served first then leaves and the next person is served. Other students can join at the end of a queue.

A typical queue has the following characteristics:

Two ends:

- front - points to starting element
- rear - points to the last element

Two conditions:

- overflow - insertion into a queue that is full
- underflow - deletion from the empty queue

Operations:

- enqueue - inserting an element into the queue. It will be done at the rear.
- dequeue - deleting an element from the queue. It will be done at the front.

A video explanation can be found here.

A queue can be implemented as follows:

```
class Queue:
def __init__(self):
self.data = []
def length(self):
return len(self.data)
def enque(self, element):
if len(self.data) < 5:
return self.data.append(element)
else:
return "overflow"
def deque(self):
if len(self.data) == 0:
return "underflow"
else:
self.data.pop(0)
```

# 4. Stack

Stacks are linear data structures that work on the Last-In-First-Out (LIFO) principle. The data that is inserted last is the first to be accessed. It is constructed using an array structure and includes methods such as pushing (adding) elements, popping (deleting) elements. Accessing elements can only be done from the TOP of the stack.

The characteristics of a stack include:

Operations are:

- Push - inserting an element into the stack
- Pop - deleting an element from the stack

Conditions:

- overflow condition - occurs when we try to put one more element into a stack that already has the maximum number of elements.
- underflow condition - occurs when we try to delete an element from an empty stack.

A video explanation can be found here.

A Stack can be implemented as follows:

```
class Stack:
def __init__(self):
self.data =[]
def length(self):
return len(self.data)
def is_full(self):
if len(self.data) == 7:
return True
else:
return False
def push(self, element):
if len(self.data) < 7:
self.data.append(element)
else:
return "overflow"
def pop(self):
if len(self.data) == 0:
return "underflow"
else:
return self.data.pop()
```

# 5. Trees

Trees are non-linear Data Structures with a root and nodes. The root is the node from which the data comes, and the nodes are the other data points we have access to. The parent is the node that comes before the child. Each child has exactly one parent node. Trees with nodes that have exactly two children each are called binary trees. A tree must have levels to demonstrate the depth of information. The leaves are the final nodes in a chain. It is worth noting that trees generate a hierarchy structure. HTML DOM are the best example of a tree structure.

A video explanation can be found here.

A tree node can be implemented as follows:

```
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
```

A heap and hashtable are other noteworthy data-structures to look at.