First Encounter with Data Structures
Singular Linked List
Basics
A singular linked list provides constant time insertion and deletion. These changes occur through Nodes that contain a value and a link/pointer to another node.
Problem
Because the values are not indexed; it is hard to find an individual value. You must traverse the list, by following the pointer nodes until they reach your destination or the of the list. If you need easy access to individual nodes you will lose your time complexity savings.
Example Use
Your grocery list that you expect to add and remove items from
Key Functions
Finding the head and tail — allows you to find the beginning and the end of the linked list.
Adding to tail — adds a node at the end of your list.
Remove the head — removes the first element from your linked list
Contains — check if your linked list contains a certain value.
Further Examples
http://www.thatjsdude.com/interview/linkedList.html
Doubly Linked Lists Differences
A Doubly Linked List also contains a pointer to the next element in the list also contains a pointer to the previous element in the list. This additional pointer makes it easier to remove elements from the list. The reason Singly Linked Lists are preferred is because you use extra memory storing two pointers even though you should not frequently need to traverse your list.
Tree Data Structures
Basics
Tree Data Structures are a series of nodes with parent and child nodes. The first node is called the Root, and the rest are children of the Root node. A node that has a parent but no children is called a Leaf node. Walking the tree is when you go up or down the tree using parent or child nodes respectively. The two types of searches are Depth First & Breadth First. The former requires you to go to the bottom of one set of child nodes before analyzing a different path. Breadth First requires you to look at every node that’s the same distance from the root before proceeding further down the tree.
The height of a node is how many nodes it is away from the Root node. The height of the tree is the farthest distance from the Root node to a Leaf node.
Uses
Possible uses for trees would be mapping your family tree or an organization’s hierarchy
Key Functions
children — array containing subtrees
addChild — takes a value and adds it as a child node of an existing node
contains — checks a node and its descendants to see if a value is contained within any of them.
Binary Search Tree
Use
A Binary Search Tree or BST is the most useful tree structure because each node has at most two child nodes. An example usage, is deciding mentor /mentee relationships to ensure no mentor has more than two mentees.
Traversal Types
Pre-Order — Start at the root and work your down the tree from left to right
In-Order — Start at the bottom of the left node chain then move towards the right node chain
Post-Order-Start at the bottom of each node chain then work backwards
Graphs
Basics
In a graph data structure the nodes are referred to as vertices and are connected in some way. Edges(pairs) form when two nodes connect. Degrees are the number of edges a node has. A connected graph means there is a path between every single pair of vertices. If every vertice is directly connected every other vertice it is called a Complete graph.
Types
Undirected — The Edges are unordered because you can traverse between vertices
Directed — The Edges are ordered because a connection only allows you to travel one way. Two vertices can have two edges allowing you to traverse between more easily.
Uses
A graph is useful for mapping flight routes. If a flight route exists between two cities, then they would have an edge. You could also use it to map the connections between websites.
Key Functions
General Node Functions— Add, Remove, Contains
forEachNode- Do something to each node
Edge Function — Add, Remove, Has Edge(tests if two nodes are connected)
Set
Basics
Sets contain unique unordered values. At its simplest form, a Set is an array. You may often see it represented as circles i.e. a Venn Diagram. It is best though to use objects, not arrays to allow for the least time complex operations.
Uses
Randomly choosing what to wear from your closet of clothes(assuming you are not Mark Zuckerberg).
Key Functions
General — Add & Remove
Intersection — The values two sets share
Difference — The values they don’t share
Union — Assumes there is an intersection and returns all unique values
Hashing Table
Basics
Hash tables require a key and value to work. This key value pair forms a tuple that is an array containing the two. The Hash Table’s hashing function takes the key and determines at what index to insert the tuple . There can be multiple tuples at one index allowing for easy storage.
Uses
A Hashing Table can be used to store a constant changing contact list. Information is connected to an individual then stored away.
Key Functions
Insert — Adds a tuple into the Hash Table
Remove — Removes a tuple from the Hash Table
Retrieve — Retrieves a tuple given a certain key.
Sources
All
- Hack Reactor Materials
Linked List
- http://www.i-programmer.info/programming/javascript/5328-javascript-data-structures-the-li…
- http://en.wikipedia.org/wiki/Linked_list
- http://blog.millermedeiros.com/linked-lists/
Trees
- https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&cad=rja&uact=8&ved=0CCwQFj…
- http://www.i-programmer.info/babbages-bag/477-trees.html?start=2
- http://www.geeksforgeeks.org/data-structures/#BinaryTree
- https://en.wikipedia.org/wiki/Tree_traversal
Graphs
- https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-graphs-and-their-data-structures-section-1/
- https://www.youtube.com/watch?v=vfCo5A4HGKc
