edit-article

Article Name:

Article Description:

Chapter ID/Name:

Status:

Add Photo:

Owner ID:

Content: use HTML Edit Content

<h1 style="text-align: center;">overview&nbsp;- data-structures</h1>
<h2>WHAT</h2>
<ol>
<li>] GOAL PAPER - data structures for dummies - an attempt at gaining a better understanding of data structures and their use.</li>
<li>] define: data structure</li>
<ol>
<li>] a computer science construct, a data structure defines a formal method for storing data to best acheive a particular results (ex fast searching).</li>
<li>] there are several different types of data structures,&nbsp;some of the main types included Lists, Graphs, Trees. Each of the main types include have many subtypes (aka variants), ex Trees hav B-Trees,</li>
<li>*wik] a particular way of organizing data in a computer so that it can be used efficiently.&nbsp; Data structures can implement one or more particular <a title="Abstract data type" href="http://en.wikipedia.org/wiki/Abstract_data_type" target="_blank">abstract data types</a>, which are the means of specifying the contract of operations and their <a title="Computational complexity theory" href="http://en.wikipedia.org/wiki/Computational_complexity_theory" target="_blank">complexity</a>. In comparison, a data structure is a concrete implementation of the contract provided by an ADT.</li>
</ol></ol>
<h2>WHY</h2>
<ol>
<li>]&nbsp;a particular way of organizing data in a computer so that it can be used efficiently.</li>
<li>] usage of the the correct type of data structures can result in alogrithms that perform orders of magnitude more efficiently than where improper data structures were used.</li>
</ol>
<h2>WHEN</h2>
<ol>
<li>] you get the google interview, your standing in front of the whiteboard, in front of the interview panel, they ask</li>
<ol>
<li>]&nbsp; can you implement an example of a {linked list} in &lt;insert programming language&gt;,</li>
</ol></ol>
<h2>WHERE</h2>
<ol>
<li>] @ your apps codebase</li>
<li>] @ google interview</li>
</ol>
<h2>EXAMPLE(S)</h2>
<ol>
<li>] primitive data types</li>
<ol>
<li>] integer</li>
<li>] float</li>
<li>] char</li>
<li>]</li>
</ol>
<li>] composite data types</li>
<ol>
<li>*] <a href="/view/article?id=2598" target="_blank">Array</a> -</li>
<ol>
<li>] a collection of related data elements, contiguous&nbsp; may be a fixed size or expandable(dynamic),&nbsp;each element is accessed by its numeric index&nbsp;</li>
</ol>
<li>] <a title="Record (computer science)" href="http://en.wikipedia.org/wiki/Record_(computer_science)">Records</a> (also called tuples or structs or class)</li>
<ol>
<li>] are among the simplest data structures. A record is a value that contains other values, typically in fixed number and sequence and typically indexed by names. The elements of records are usually called fields or members.</li>
<li>] DISTINCT: record (data only) and class (data&nbsp;+ code that operates on that data, template to create object)&nbsp;</li>
</ol>
<li>*] <a title="Object (computer science)" href="http://en.wikipedia.org/wiki/Object_(computer_science)">object</a>&nbsp;</li>
<ol>
<li>] contains data fields, like a record, and also contains program code fragments for accessing or modifying those fields.</li>
<li>] Data structures not containing code, like those above, are called <a title="Plain old data structure" href="http://en.wikipedia.org/wiki/Plain_old_data_structure">plain old data structures</a>.</li>
<li>] DISTINCT: instances of a class</li>
</ol>
<li>] <a class="mw-redirect" title="Union (computer science)" href="http://en.wikipedia.org/wiki/Union_(computer_science)">union</a></li>
<ol>
<li>] type specifies which of a number of permitted primitive types may be stored in its instances, e.g. "float or long integer". Contrast with a <a title="Record (computer science)" href="http://en.wikipedia.org/wiki/Record_(computer_science)">record</a>, which could be defined to contain a float and an integer; whereas, in a union, there is only one value at a time. Enough space is allocated to contain the widest member datatype.</li>
</ol>
<li>] <a title="Tagged union" href="http://en.wikipedia.org/wiki/Tagged_union">tagged union</a> (also called a <a title="Variant type" href="http://en.wikipedia.org/wiki/Variant_type">variant</a>, variant record, discriminated union, or disjoint union)</li>
<ol>
<li>] contains an additional field indicating its current type, for enhanced type safety.</li>
</ol></ol>
<li>] abstract data types</li>
<ol>
<li>*] <a href="/view/article?id=2598" target="_blank">Array</a>&nbsp;- a collection of related data elements, accessed by their index</li>
<li>] Container -</li>
<li>&gt;] <a title="Associative array" href="http://en.wikipedia.org/wiki/Associative_array" target="_blank">Map/Associative array/Dictionary</a>&nbsp; - Map (aka dictionary) are key/value pairs. Give a map a key and it will return the associated value4. </li>
<li>] <a title="Multimap" href="http://en.wikipedia.org/wiki/Multimap" target="_blank">Multimap</a>&nbsp;-</li>
<li>] <a title="List (abstract data type)" href="http://en.wikipedia.org/wiki/List_(abstract_data_type)" target="_blank">List</a>&nbsp;-</li>
<li>] <a title="Set (abstract data type)" href="http://en.wikipedia.org/wiki/Set_(abstract_data_type)" target="_blank">Set</a> is an <a class="mw-redirect" title="Abstract data structure" href="http://en.wikipedia.org/wiki/Abstract_data_structure">abstract data structure</a>&nbsp;] that can store specific values, without any particular <a title="Sequence" href="http://en.wikipedia.org/wiki/Sequence">order</a>, and with no repeated values. Values themselves are not retrieved from sets, rather one tests a value for membership to obtain a boolean "in" or "not in".</li>
<li>] <a title="Multiset (abstract data type)" href="http://en.wikipedia.org/wiki/Multiset_(abstract_data_type)" target="_blank">Multiset/Bag</a>&nbsp;-</li>
<li>] <a title="Priority queue" href="http://en.wikipedia.org/wiki/Priority_queue" target="_blank">Priority queue</a>&nbsp;-</li>
<li>&gt;] <a title="Queue (data structure)" href="http://en.wikipedia.org/wiki/Queue_(data_structure)" target="_blank">Queue</a>&nbsp;- FIFO the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a <a title="FIFO (computing and electronics)" href="http://en.wikipedia.org/wiki/FIFO_(computing_and_electronics)" target="_blank">First-In-First-Out (FIFO) data structure</a>. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. Often a <a title="Peek (data type operation)" href="http://en.wikipedia.org/wiki/Peek_(data_type_operation)">peek</a> or front operation is also entered, returning the value of the front element without dequeuing it. A queue is an example of a <a title="Linear data structure" href="http://en.wikipedia.org/wiki/Linear_data_structure" target="_blank">linear data structure</a>, or more abstractly a sequential collection.</li>
<ol>
<li>] Queues provide services in <a title="Computer science" href="http://en.wikipedia.org/wiki/Computer_science">computer science</a>, <a title="Transport" href="http://en.wikipedia.org/wiki/Transport">transport</a>, and <a title="Operations research" href="http://en.wikipedia.org/wiki/Operations_research">operations research</a> where various entities such as data, objects, persons, or events are stored and held to be processed later. In these contexts, the queue performs the function of a <a class="mw-redirect" title="Buffer (computer science)" href="http://en.wikipedia.org/wiki/Buffer_(computer_science)">buffer</a></li>
</ol>
<li>] <a title="Double-ended queue" href="http://en.wikipedia.org/wiki/Double-ended_queue">Double-ended queue</a>&nbsp;</li>
<li>] <a class="mw-redirect" title="Stack (data structure)" href="http://en.wikipedia.org/wiki/Stack_(data_structure)">Stack</a>&nbsp;- LIFO, can only&nbsp;be accessed from the top, most common ops are push(add item), pop(remove item)</li>
<ol>
<li>cc] stack VS heap in memory allocation</li>
</ol>
<li>] <a title="String (computer science)" href="http://en.wikipedia.org/wiki/String_(computer_science)">String</a>&nbsp;-</li>
<li>] <a class="mw-redirect" title="Tree (computer science)" href="http://en.wikipedia.org/wiki/Tree_(computer_science)">Tree</a>&nbsp;-&nbsp; recursive data structures consisting of nodes with children, a restricted form of a Graph(4), have direction (parent / child relationships) and don't contain cycles. They fit with in the category of Directed Acyclic Graphs (or a DAG). So Trees are DAGs with the restriction that a child can only have one parent.</li>
<li>] <a class="mw-redirect" title="Graph (data structure)" href="http://en.wikipedia.org/wiki/Graph_(data_structure)">Graph</a>&nbsp;-</li>
</ol>
<li>] linear data structure - </li>
<ol>
<li>] <a title="Array data structure" href="http://en.wikipedia.org/wiki/Array_data_structure">Array</a>&nbsp;- stores a number of elements in a specific order. They are accessed using an integer (index)&nbsp;to specify which element is required (although the elements may be of almost any type). Typical implementations allocate contiguous memory words for the elements of arrays (but this is not always a necessity). Arrays may be fixed-length or expandable.</li>
</ol>
<li>] linear data structure -&nbsp;lists <ol>
<li>*] <a href="/view/article?id=4469" target="_blank">list-linked</a></li>
<ol>
<li>]</li>
</ol>
<li>] list-linked-double</li>
<li>] list-array</li>
<li>] list-self-organizing</li>
<li>] list-skipped</li>
<li>] list-unrolled</li>
<li>] vlist</li>
<li>] xorList-linked</li>
<li>] list double connected edge</li>
<li>] zipper</li>
<li>] list-difference</li>
<li>] list-free</li>
</ol></li>
<li>&gt;] hashes <a title="Hash table" href="http://en.wikipedia.org/wiki/Hash_table">hash table</a> (also called a dictionary or <a class="mw-redirect" title="Map (computer science)" href="http://en.wikipedia.org/wiki/Map_(computer_science)">map</a>)</li>
<ol>
<li>] is a more flexible variation on a record, in which <a class="mw-redirect" title="Name-value pair" href="http://en.wikipedia.org/wiki/Name-value_pair">name-value pairs</a> can be added and deleted freely.</li>
<li>] <a href="http://en.wikipedia.org/wiki/Hash_table">http://en.wikipedia.org/wiki/Hash_table</a>&nbsp;</li>
<li>] <a href="http://blog.bodurov.com/Performance-SortedList-SortedDictionary-Dictionary-Hashtable/" target="_blank">http://blog.bodurov.com/Performance-SortedList-SortedDictionary-Dictionary-Hashtable/</a>&nbsp;</li>
</ol>
<li>&gt;] <a title="Graph (abstract data type)" href="http://en.wikipedia.org/wiki/Graph_(abstract_data_type)">Graphs</a> are <a title="Linked data structure" href="http://en.wikipedia.org/wiki/Linked_data_structure" target="_blank">linked</a>&nbsp;<a title="Abstract data type" href="http://en.wikipedia.org/wiki/Abstract_data_type">abstract data structures</a> composed of <a title="Node (computer science)" href="http://en.wikipedia.org/wiki/Node_(computer_science)">nodes</a>. ] Each node contains a value and also one or more <a title="Pointer (computer programming)" href="http://en.wikipedia.org/wiki/Pointer_(computer_programming)">pointers</a> to other nodes. ] Graphs can be used to represent networks,</li>
<ol>
<li>] Graph</li>
<li>] Adjecency List</li>
<li>] Adjecency Matrix</li>
<li>] Graph Structured Stack</li>
<li>] Scene Graph</li>
<li>] <a title="Binary decision diagram" href="http://en.wikipedia.org/wiki/Binary_decision_diagram" target="_blank">Binary decision diagram</a></li>
<li>] <a title="Zero-suppressed decision diagram" href="http://en.wikipedia.org/wiki/Zero-suppressed_decision_diagram" target="_blank">Zero-suppressed decision diagram</a></li>
<li>] <a title="And-inverter graph" href="http://en.wikipedia.org/wiki/And-inverter_graph" target="_blank">And-inverter graph</a></li>
<li>] <a title="Directed graph" href="http://en.wikipedia.org/wiki/Directed_graph" target="_blank">Directed graph</a>&nbsp;</li>
<li>] <a title="Directed acyclic graph" href="http://en.wikipedia.org/wiki/Directed_acyclic_graph" target="_blank">Directed acyclic graph</a>&nbsp;</li>
<li>] <a title="Propositional directed acyclic graph" href="http://en.wikipedia.org/wiki/Propositional_directed_acyclic_graph" target="_blank">Propositional directed acyclic graph</a>&nbsp;</li>
<li>] <a title="Multigraph" href="http://en.wikipedia.org/wiki/Multigraph" target="_blank">Multigraph</a></li>
<li>] <a title="Hypergraph" href="http://en.wikipedia.org/wiki/Hypergraph" target="_blank">Hypergraph</a>&nbsp;</li>
</ol>
<li>&gt;] <a title="Tree (data structure)" href="http://en.wikipedia.org/wiki/Tree_(data_structure)">Trees</a> are <a title="Linked data structure" href="http://en.wikipedia.org/wiki/Linked_data_structure" target="_blank">linked</a>&nbsp;<a title="Abstract data type" href="http://en.wikipedia.org/wiki/Abstract_data_type" target="_blank">abstract data structures</a> composed of <a title="Node (computer science)" href="http://en.wikipedia.org/wiki/Node_(computer_science)" target="_blank">nodes</a>. ] Each node contains a value and also one or more <a title="Pointer (computer programming)" href="http://en.wikipedia.org/wiki/Pointer_(computer_programming)" target="_blank">pointers</a> to other nodes. ] trees are generally used for <a title="Sorting algorithm" href="http://en.wikipedia.org/wiki/Sorting_algorithm" target="_blank">sorting</a> and <a title="Search algorithm" href="http://en.wikipedia.org/wiki/Search_algorithm" target="_blank">searching</a>, having their nodes arranged in some relative order based on their values.</li>
<ol>
<li>*] Binary tree - *] binary search tree -</li>
<li>] B-Trees -</li>
<li>] Heaps -</li>
<li>] Tries -&nbsp;</li>
<li>] Multiway-Trees&nbsp;-</li>
<li>+] RedBlack Trees -</li>
<li>] Space-Partitioning-Trees -</li>
<li>] Application-Specific-Trees -</li>
</ol>
<li>] other</li>
<ol>
<li>] <a title="Lightmap" href="http://en.wikipedia.org/wiki/Lightmap" target="_blank">Lightmap</a>&nbsp;-</li>
<li>] <a title="Winged edge" href="http://en.wikipedia.org/wiki/Winged_edge" target="_blank">Winged edge</a>&nbsp;-</li>
<li>] <a title="Doubly connected edge list" href="http://en.wikipedia.org/wiki/Doubly_connected_edge_list" target="_blank">Doubly connected edge list</a>&nbsp;</li>
<li>] <a title="Quad-edge" href="http://en.wikipedia.org/wiki/Quad-edge" target="_blank">Quad-edge</a>&nbsp;</li>
<li>] <a title="Routing table" href="http://en.wikipedia.org/wiki/Routing_table" target="_blank">Routing table</a>&nbsp;</li>
<li>] <a title="Symbol table" href="http://en.wikipedia.org/wiki/Symbol_table" target="_blank">Symbol table</a>&nbsp;</li>
</ol>
<li>] REFERENCE</li>
<ol>
<li>] <a href="http://en.wikipedia.org/wiki/Data_structures" target="_blank">http://en.wikipedia.org/wiki/Data_structures</a>&nbsp;-</li>
<li>] <a href="http://en.wikipedia.org/wiki/List_of_data_structures" target="_blank">http://en.wikipedia.org/wiki/List_of_data_structures</a>&nbsp;- more complete listing of the different data structures,</li>
<li>] <a href="http://en.wikipedia.org/wiki/Book:Data_structures" target="_blank">http://en.wikipedia.org/wiki/Book:Data_structures</a>&nbsp;</li>
<li>] <a title="Search data structure" href="http://en.wikipedia.org/wiki/Search_data_structure" target="_blank">Search data structure</a>&nbsp;- a comparison of the costs of using different data structures to perform a search operation on a data set</li>
<li>] <a href="http://stackoverflow.com/questions/7423401/whats-the-difference-between-the-data-structure-tree-and-graph">http://stackoverflow.com/questions/7423401/whats-the-difference-between-the-data-structure-tree-and-graph</a>&nbsp;</li>
<li>] <a href="http://www.sjbaker.org/wiki/index.php?title=A_Short_Guide_to_Data_Structures" target="_blank">http://www.sjbaker.org/wiki/index.php?title=A_Short_Guide_to_Data_Structures</a>&nbsp;</li>
<li>] <a href="http://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap">http://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap</a>&nbsp;</li>
</ol></ol>
&nbsp;
<hr />
TEST
<ol>
<li>] define: What is a data structure?</li>
<li>] list 5 different data structures</li>
<li>] compare and contrast 2 of the 5 different data structures that you listed ( ex Array VS linked list)</li>
<li>]</li>
<li>]</li>
</ol>