Data Structures

Front 1

Array

Back 1

- Fixed-sized

- indexed

- contiguous structures whose elements are all of the same type, and whose elements can be accessed in constant time given their indices.

Front 2

Vectors

Back 2

- Also known as "growable arrays" or ArrayLists.

- they're objects that are backed by a fixed-size array, and that they resize themselves as necessary.

Front 3

Linked List

Back 3

Lists made of nodes that contain a data item and a pointer/reference to the next (and possibly previous) node.

Front 4

Hashtable

Back 4

- Amortized constant-time to access data

- map keys to values, and are backed by a real array in memory, with some form of collision handling for values that hash to the same location.

Example:

- used for fast data lookup - symbol table for compilers, database indexing, caches,Unique data representation.

Front 5

Trees

Back 5

Data structures that consist of nodes with optional data elements and one or more child pointers/references, and possibly parent pointers, representing a heirarchical or ordered set of data elements.

Front 6

Graphs

Back 6

Represent arbitrary relationships between members of any data set, represented as networks of nodes and edges.

Examples:

- Connections/relations in social networking sites, Routing ,networks of communication, data organization etc.

Front 7

Heap

Back 7

- Specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the heap.

Example:

- Dynamic memory allocation in lisp

- Order statistics: The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array.

- Sorting Algorithm

Front 8

Application areas of Stacks

Back 8

- compilers, operating systems, handling of program memory (nested function calls)

Front 9

Stacks

Back 9

- First In Last Out (FILO).

- Insertions and removals from "top" position only

Front 10

Queue

Back 10

- First In First Out (FIFO).

- Insertions at the "end" of the queue, and removals from the "front" of the queue.

- two primary operations: enqueue and dequeue

Front 11

Application areas ofQueue

Back 11

Include print job scheduling, operating systems (process scheduling).

Front 12

Abstract Data Type

Back 12

- An abstract data type is a specification (or interface) for how to interact with a sort of data structure which doesn’t make any statements about how the data structure works.

Front 13

Examples of Abstract Data Type

Back 13

- List can be described in terms of an abstract data type (we can insert into it, get the nth element, delete an element, etc.), while a linked list is an implementation of that abstract data type (it implements the specified behavior by structuring the data as either an empty list or a pairing of a data element and another linked list).

- an abstract stack can be implemented by a linked list or by an array (which are concrete data types).

- Examples :

Priority queue : a shorthand way of describing a particular interface and behavior, and says nothing about the underlying implementation. ( a heap would be a data structure)

Front 14

What describe an abstract data structure?

Back 14

- Give the relationship between the objects being stored, and

- Specify the operations which are to be optimized with respect to time and/or space.

Front 15

Priority_queue

Back 15

Its a specialized complete binary tree where the keys must satisfy the heap property - the key at each node is at least as great as the keys storedat its children.

2i + 1 and 2i + 2.

- Use a heap when you care about the K largest and smallest elements -

- Compute the k largest (use a min-heap) and the k smallest (use a max-heap)

- Insertion : O(logn) -

- Lookup for the max(or min) element: O(1)

- Delete the max(or min) element : O(logn)

- Searching for arbitraty keys : O(n)