LAD Block 5.1: Design and implementation of data structures

• Number of elements
• divided by 
• size of table

• The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.
• When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

ADT is to an interface (what it does) what a data structure is to a class (how it does it).

A few examples:

• ADT: List
• DS: ArrayList, LinkedList...

• ADT: Map
• DS: HashMap, TreeMap...

• We may not say
• "linked list  stack"
• but we do say
• "stack using a linked list"
• where stack is the ADT and
• linked list is the 'implementation'.

You cannot call the implementation (i.e. say linked list) same as stack because the data structure(linked list)  has a set of operations(DeleteNode() ,InsertNode() )  completely independent of the ADT(Stack) that is going to use them to implement itself(i.e. implementing operations  like push(),pop()...). Implementation of an ADT doesn't make any reference to how a Data Structure is implemented.

• So a 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).

We could implement the same list abstract data type in many other ways, for example with an array or binary tree.

Set is Abstract Data Structure.

• No duplicate items.
• No orders of the Items.

Use: rather than retrieving a specific element from a set, one typically tests a value for membership in a set.

In mathematics, a finite set is a set that has a finite number of elements.

• Informally, a finite set is a set which one could in principle count and finish counting.
• For example,{2,4,6,8,10} is a finite set with five elements.
• The number of elements of a finite set is a natural number (a non-negative integer).

• A set that is not finite is called infinite.
• For example, the set of all positive integers is infinite:  {1,2,3,...}

One may define the operations of the algebra of sets:

• Union(S,T): Allt i S och allt i T
• returns the union of sets S&T.

• Intersection(S,T): Allt som finns i bådeS&T
• Returns the intersection of sets S and T.

• Difference(S,T): Allt i S som inte finns i T
• Returns the difference of sets S and T.

• Subset(S,T): Finns allt i S även i T?
• A predicate that tests whether the set S is a subset of set T.

• 1.Linear data structures
•  Arrays
•  Lists

• 2 Trees
•  Binary trees
•  Trees
•  Heaps

3 Hashes

4 Graphs

• Fixed length: Once an array is created, we cannot change its size.
• So consider using arrays when the numbers of elements are known and fixed.
• Otherwise, you should consider using another dynamic container such as ArrayList.

• Fast access: It’s very fast to access any elements in an array (by index of the elements) in constant time: accessing the 1st element takes same time as accessing the last element.
• So performance is another factor when choosing arrays.

• In Java, the position of an element is specified by index which is zero-based.
• That means the first element is at index 0, the second element at index 1, and so on.

An array itself is actually an object.

ADT

• As the name implies, lists can be used to store a list of elements.
• However, unlike in traditional arrays, lists can expand and shrink, and are stored dynamically in memory.

Represents a countable number of ordered values, where the same value may occur more than once.

• An instance of a list is a computer representation of the mathematical concept of a finite sequence;
• the (potentially) infinite analog of a list is a stream.

A hash table is a hash map and a DS.

• A Hash table/map can map keys to values.
• A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure.

• Everything in the hash table is part of a pair -- there is a key and a value.
• You put in and get out data by specifying the key you are operating on.

not good when sorting is needed or when you want to iterate through all the values

ADT

Map is an interface in java and its concrete implementations are called HashMaps and Hashtables.

A map is a data structure and its majorly used for fast look ups or searching data. It stores data in the form of key and value pairs where every key is unique. Each key here maps to a value and hence the name map !

• Key         :       Value
• John        :         1
• Peter       :         2  

The next time when I try inserting John as the key with say 3 as the value then it would override the previously inserted pair for John

• Hence after the third insert the map would still contain 2 pairs with 3 as John's value.
• A map data structure stores data in key/value pairs, and in the strict definition, each key is unique.

• Stack is an abstract data type that serves as a collection of elements, with two principal operations:
• push, which adds an element to the collection,
• and
• pop, which removes the most recently added element that was not yet removed. The order in which elements come off a stack gives rise to its alternative name, LIFO (for last in, first out) like a stack of bricks. 
• A stack is a limited access data structure - elements can be added and removed from the stack only at the top.

• Application :
• -To reverse a word. You push a given word to stack - letter by letter - and then pop letters from the stack.

• -An "undo" mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.
• Undo/Redo stacks in Excel or Word.

A tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—

A tree simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

• A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root. For example,
• looking at a tree as a whole, one can talk about "the parent node" of a given node, but in general as a data structure a given node only contains the list of its children, but does not contain a reference to its parent (if any).

1) One reason to use trees might be because you want to store information that naturally forms a hierarchy. For example, the file system on a computer

• A graph data structure consists of a finite set of vertices or nodes or points, together with :a set of unordered pairs of these vertices for an undirected graph or 
• :a set of ordered pairs for a directed graph.

• These pairs are known as edges, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph.
• The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.
• A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).

Priority queue dequeue happens according to some ordering (priority) comparison not the enqueue order.

For instance you might store timed events in one where you want to pull out the soonest event first and query for its scheduled time so you can sleep until that point in time.

Priority queues are often implemented using heaps.

A queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order of a First-In-First-Out (FIFO) data structure. Matkö.

They have dynamic capacity.

It is not true that items need to be copied towards the head of the queue.

a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it.

In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.While priority queues are often implemented with heaps, they are conceptually distinct from heaps.

A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.