article

overview - data-structures

WHAT

  1. ] GOAL PAPER - data structures for dummies - an attempt at gaining a better understanding of data structures and their use.
  2. ] define: data structure
    1. ] a computer science construct, a data structure defines a formal method for storing data to best acheive a particular results (ex fast searching).
    2. ] there are several different types of data structures, 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,
    3. *wik] a particular way of organizing data in a computer so that it can be used efficiently.  Data structures can implement one or more particular abstract data types, which are the means of specifying the contract of operations and their complexity. In comparison, a data structure is a concrete implementation of the contract provided by an ADT.

WHY

  1. ] a particular way of organizing data in a computer so that it can be used efficiently.
  2. ] 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.

WHEN

  1. ] you get the google interview, your standing in front of the whiteboard, in front of the interview panel, they ask
    1. ]  can you implement an example of a {linked list} in <insert programming language>,

WHERE

  1. ] @ your apps codebase
  2. ] @ google interview

EXAMPLE(S)

  1. ] primitive data types
    1. ] integer
    2. ] float
    3. ] char
    4. ]
  2. ] composite data types
    1. *] Array -
      1. ] a collection of related data elements, contiguous  may be a fixed size or expandable(dynamic), each element is accessed by its numeric index 
    2. ] Records (also called tuples or structs or class)
      1. ] 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.
      2. ] DISTINCT: record (data only) and class (data + code that operates on that data, template to create object) 
    3. *] object 
      1. ] contains data fields, like a record, and also contains program code fragments for accessing or modifying those fields.
      2. ] Data structures not containing code, like those above, are called plain old data structures.
      3. ] DISTINCT: instances of a class
    4. ] union
      1. ] 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 record, 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.
    5. ] tagged union (also called a variant, variant record, discriminated union, or disjoint union)
      1. ] contains an additional field indicating its current type, for enhanced type safety.
  3. ] abstract data types
    1. *] Array - a collection of related data elements, accessed by their index
    2. ] Container -
    3. >] Map/Associative array/Dictionary  - Map (aka dictionary) are key/value pairs. Give a map a key and it will return the associated value4.
    4. ] Multimap -
    5. ] List -
    6. ] Set is an abstract data structure ] that can store specific values, without any particular order, 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".
    7. ] Multiset/Bag -
    8. ] Priority queue -
    9. >] Queue - 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 First-In-First-Out (FIFO) data structure. 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 peek or front operation is also entered, returning the value of the front element without dequeuing it. A queue is an example of a linear data structure, or more abstractly a sequential collection.
      1. ] Queues provide services in computer science, transport, and operations research 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 buffer
    10. ] Double-ended queue 
    11. ] Stack - LIFO, can only be accessed from the top, most common ops are push(add item), pop(remove item)
      1. cc] stack VS heap in memory allocation
    12. ] String -
    13. ] Tree -  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.
    14. ] Graph -
  4. ] linear data structure -
    1. ] Array - stores a number of elements in a specific order. They are accessed using an integer (index) 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.
  5. ] linear data structure - lists
    1. *] list-linked
      1. ]
    2. ] list-linked-double
    3. ] list-array
    4. ] list-self-organizing
    5. ] list-skipped
    6. ] list-unrolled
    7. ] vlist
    8. ] xorList-linked
    9. ] list double connected edge
    10. ] zipper
    11. ] list-difference
    12. ] list-free
  6. >] hashes hash table (also called a dictionary or map)
    1. ] is a more flexible variation on a record, in which name-value pairs can be added and deleted freely.
    2. ] http://en.wikipedia.org/wiki/Hash_table 
    3. ] http://blog.bodurov.com/Performance-SortedList-SortedDictionary-Dictionary-Hashtable/ 
  7. >] Graphs are linked abstract data structures composed of nodes. ] Each node contains a value and also one or more pointers to other nodes. ] Graphs can be used to represent networks,
    1. ] Graph
    2. ] Adjecency List
    3. ] Adjecency Matrix
    4. ] Graph Structured Stack
    5. ] Scene Graph
    6. ] Binary decision diagram
    7. ] Zero-suppressed decision diagram
    8. ] And-inverter graph
    9. ] Directed graph 
    10. ] Directed acyclic graph 
    11. ] Propositional directed acyclic graph 
    12. ] Multigraph
    13. ] Hypergraph 
  8. >] Trees are linked abstract data structures composed of nodes. ] Each node contains a value and also one or more pointers to other nodes. ] trees are generally used for sorting and searching, having their nodes arranged in some relative order based on their values.
    1. *] Binary tree - *] binary search tree -
    2. ] B-Trees -
    3. ] Heaps -
    4. ] Tries - 
    5. ] Multiway-Trees -
    6. +] RedBlack Trees -
    7. ] Space-Partitioning-Trees -
    8. ] Application-Specific-Trees -
  9. ] other
    1. ] Lightmap -
    2. ] Winged edge -
    3. ] Doubly connected edge list 
    4. ] Quad-edge 
    5. ] Routing table 
    6. ] Symbol table 
  10. ] REFERENCE
    1. ] http://en.wikipedia.org/wiki/Data_structures -
    2. ] http://en.wikipedia.org/wiki/List_of_data_structures - more complete listing of the different data structures,
    3. ] http://en.wikipedia.org/wiki/Book:Data_structures 
    4. ] Search data structure - a comparison of the costs of using different data structures to perform a search operation on a data set
    5. ] http://stackoverflow.com/questions/7423401/whats-the-difference-between-the-data-structure-tree-and-graph 
    6. ] http://www.sjbaker.org/wiki/index.php?title=A_Short_Guide_to_Data_Structures 
    7. ] http://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap 

 

TEST

  1. ] define: What is a data structure?
  2. ] list 5 different data structures
  3. ] compare and contrast 2 of the 5 different data structures that you listed ( ex Array VS linked list)
  4. ]
  5. ]
Details Photos Edit more

Details

ID: 2599

NAME: overview-data-structures

DESCRIPTION: Overview of the Contents of this book -

AUTHOR: article.author/s

EDITOR: article.editor/s

PUBLISHER: article.publisher/s

STATUS: Write

PRIORITY: -5

OWNER ID: 75

Content Photos Edit more

photos

page_photo

actions

Email Email-Owner SMS and