This is a repository where I implement various datastructures as a way of improving both my conceptual understanding of them while at the same time improving upon my Python skills. Datastructures are naturally very important in programming, they facilitate many algorithms such as the graph searches, DFS and BFS and are often used practically. In this repo I implement, among other datastructures, the very common ones, Linked Lists, single and double linked, binary search trees, graphs, stacks, queues .. and more datastructures will come, no doubt! :) The writing of these datastructures is made in such a way that we are always testing and asserting that the datastructures behave in a way that we would want them to.

• The operating system: The operating system makes good use of a stack and of a heap as means of memory allocation. The problem, and famous website, Stack Overflow comes about when the stack upon which we allocate memory has been exceeded. Typically it occurs if we have an infinte recursive call with no base case. The heap is also a datastructure that our very own operating system makes use of.

• Competitive programming problem - Pairing Socks: Naturally there are many more practical usages of datastructures than just for competitive programming, overall they can be used to facilitate programming and to make a problem much easier. One example is the Kattis problem pairing socks (https://open.kattis.com/problems/pairingsocks). The problem is to pair socks where you can put them on an auxiliary pile (or stack). Naturally if we have access to a stack this problem really is no problem at all, as we can simulate the affect of pairing socks.

• Competitive programming problem - Where is my internet: This too is a Kattis problem where we get houses from 1..N and internet connections from 1 .. M. The problem is then to discern which houses has internet connections given that house 1 already has and all connected to it (https://open.kattis.com/problems/wheresmyinternet). Naturally these problems can be modelled with a graph and if we have access to one we can easily implement a solution. A solution could be to model a graph and from the first house make a search, either a BFS or a DFS, or another search for that matter. Every visited node we can save and so we can return the circuit of nodes all connected to house 1. The implementation of a BFS or DFS is conceptually hard to think about, I think, but with datastructures such as Stacks (for DFS) and Queues(for BFS) the nature in which we save neighboring nodes will create a DFS or BFS respectively.

Here follows a list of my current implementations of datastructures:

• Linked List: A datastructure where a node is defined as holding a reference to another node as well as holding a data value. This datastructure is like a chain where each link connects to another link. Right now there is one thing that can be improved upon, that I realized, and that is the time of insertion in the list. As it is implemented right now we traverse the entire list to get to the last element but this can be improved upon simply by storing the last element like we do with the bottom element, and so insertion can be made in constant time.

• Stack: A Stack is like a pile of dishes where we can only get to the top item. This datastructure is used to facilitate things like Depth First Searches and much more. This stack is implemented using a python list. Insertion is in constant time, basically it works like a normal list but with the exception that we can only pop the very last element, as such, the last element in will be the first element out (LIFO)

• Queue: A Queue is like the opposite of the stack, it works similarily in that we can only pop one element at a time but rather than the element on the top it is the element on the absolute bottum, the element that has been queing the longest. We can think of it conceptually as a queue to a tourist attraction, the people in the front have been standing the longest and when there is room for one more the person who was first in will be first out (FIFO). LIFO vs FIFO, that is stacks vs queues, can be used to implement things such as BFS and DFS. In my graph implementation I implement the DFS and BFS using a generic search function that takes a datastructure to store which neighbors to visit next. If that datastructure is a stack the search becomes DFS and if it is a queue the seach becomes BFS, naturally, as they are each other's opposites.

• Binary Search Tree: The binary search tree is a datastructure that starts of with a node and from that spans a tree that grows, if you so will, underground. It grows downwards. Every node in that tree has a right node and a left node, and a greater value than the root is stored to the right and a smaller to the left. This way of structuring data can be very fast, say you want to find an element 5, and the root is 2, we can look to the right to then find 8, and from that node we look to the left and maybe we find 5 already. The search traverses to the left and right of nodes, depending on if the searched for value is smaller or greater respectively. In a balanced search tree this is a very clver and efficient way of storing data as we can in worst case scenario find it in O(Log N) time, where the log is in base 2 specifically. However, when the tree is unbalanced, consider for instance the input of a sorted or reversed list, in that case the tree will be unbalanced and we will need to balance it out or it will be just as bad as a normal linked list.

• Trie: Trie is an interesting datastructure though presumably with a specialized use as compared to many other datastructures. Trie is a tree where every node has a list of children, and in our implementation we map that with a key, so that key can naturally be seen as an edge, if you so will. current_node.children_list[a] = new_node, means that from one node, we can traverse down an edge to a new node. The edges are letters and the nodes form networks of these letters as well as holding a truth value val. If val is set as true that means that the combination of edges down to that specific node is being stored. Say for instance we want the word "Rigged" and we traverse the tree. We can also insert the word "Rig" by setting the third node as being true. The Trie is a very compact datastructure in that way that is also quick, its good for keeping track of words efficiently.

• Graph: A graph is a datastructure with a network of nodes that are glued together by edges. A graph can be either directed or undirected. Directed means that one can access node2 from an edge emerging from node1, to node2. An undirected graph also makes it so that such a directed edge is symmetric, if one can go from node2 from node 1, one can also go back to node 1, from node 2. A graph is undirected by default as per the default value false for the parameter 'directed' below. One can also set this to be true when creating the graph, making it so the edges are non-symmetric. The datastructure can bind together a network of nodes and make typical graph searches such as DFS and BFS implemented by queues and stacks specifically. Moreover there is a function to see if the graph is of a tree structure, which means a non-cyclical graph where one can traverse from node x to node y in the graph using one specific path to do so.

• Hotdog: The hotdog is a datastructure without any seemingly useful utility as I can see right now, just a funny implementation of an idea. That idea is specifically to be a combination of a stack and a queue that is to have only the middle element being eligble for popping.

// All the best