Boston University

There are other basic data structures that are not defined in the Python standard library. These include:

- Linked List
- Stack
- Queue
- Tree
- Heap
- Graph

Other Basic Data Structures

A linked list is composed of a chain of objects known as nodes. Each node contains a value and a pointer to the next node in the chain. The first node in a list is known as the head. The last element in the list points to null (indicating the end of the list).

Example implementation of a Node class:
```python
class Node:
    def __init__(self, value, next = None):
        self.value = value
        self.next = next
```

The following example is a Linked List class that creates a single head node:
```python
class LinkedList:
    def __init__(self):
        self.head = None
```

The following snippet creates a linked list with 3 elements:
```python
my_linked_list = LinkedList()                   # create a LinkedList object
my_linked_list.head = Node("Jon")         # sets the head's value to "Jon"
element2 = Node("Sarah")                    # create a Node with value "Sarah"
element3 = Node("Matt")                     # create a Node with value "Matt"
my_linked_list.head.next = element2     # sets the head's next element to element2
element2.next = element3                    # sets element2's next element to element3
```

Linked List

A stack is a data structure that stores items in a "last in, first out" (LIFO) manner. New elements are added to and removed from the end of a stack. When an item is added to a stack, the operation is known as a "push". When an item is removed from a stack, the operation is known as a "pop".

A simple stack can easily be implemented in Python using the List built-in data structure.

```python
stack = []  # empty stack using the List structure.

stack.append(23)
stack.append(98)
stack.append(5)

element1 = stack.pop()   # pops 5 from the stack and sets the value of element1 to 5
element2 = stack.pop()  # pops 98 from the stack and sets the value of element2 to 98
```

Stack

A queue is a data structure that stores elements in a "first in, first out" (FIFO) manner. The least recently added item is the first element to be removed. An element is enqueued when it is added to the queue. An element is dequeued when it is removed from the queue.

A queue can be implemented using the collections module and deque class.

```python
from collections import deque

queue = deque()   # Initialize queue structure

# Enqueues the elements 20, 73 and 32
queue.append(20)
queue.append(73)
queue.append(32)

# Queue now contains [20, 73, 32]
print(queue)

# Dequeue 20
queue.popLeft()

# Queue now contains [73, 32]
print(queue)

Queue

A tree is an abstract data structure that represents a hierarchical tree. A tree contains a root which is connected to subtrees through linked nodes. The tree data structure is inherently recursive, since a node's subtree is also a tree in and of itself.
A node that has a subtree is the "parent" node of the subtree. The nodes within the subtree of the parent node are called "child" nodes. Child nodes that have the same parent are known as "sibling" nodes.

There are many types of tree data structures. A few of them include:
- Binary Tree (Binary Search Tree)
     1. AVL Tree
     2. Red-Black Tree
     3. Splay Tree
     4. Treap
- B-Tree
- N-ary Tree

Tree

Binary Tree Data Structure 

https://opendatastructures.org/ods-python/14_2_B_Trees.html

B - Tree Data Structure 

https://www.ics.uci.edu/~brgallar/week6_3.html

N - Ary Tree Data Structure 

A heap is a data structure that represents a complete binary tree where each interior node is either greater than or less than its leaf node depending on the type of heap.  

For Min- Heap, the root node key must be less than or equal to all of its children for any given subtree in the heap. For Max- Heap, the root node key must be greater than or equal to all of its children for a given subtree in the heap. 

Heap

https://www.section.io/engineering-education/heap-data-structure-python/

Heap Data Structure 

A graph is a data structure that is made up of nodes (vertices) and are connected by arcs (edges). Graphs are most commonly used to represent a network of information. An example of a graph structure is a map of a city. The blocks or buildings represent nodes. These nodes are connected by roads that represent edges. 

Graphs may be weighted or unweighted. Weighted graphs have a numerical value attached to each individual edge. This means that different edges may have different magnitudes. Unweighted graphs do not have weights related to each edge.

Graphs may also be directed or undirected. Directed graphs mean that each edge has a certain direction. As a result, these edges represent a one-way relationship since edges can only be traverse in one direction. On the other hand, undirected graphs mean that each edge has no direction. Therefore, these edges represent a two-way relationship since edges can be traversed in both directions.

Learn Before

Related