Data structure except the reported one

Linked List

is one of the fundamental data structures, and can be used to implement other data structures. It consists of a sequence of nodes, each containing arbitrary data fields and one or two references ("links") pointing to the next and/or previous nodes. The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk, allowing the list of items to be traversed in a different order.

How it access

If you have read books on memory then you would have come across a concept similar to linked lists. All these books usually explain one method for remembering the names of random objects in order. For example, your friend might read out the following list to you just once:
Sheep, carpet, bottle, cigar, tent
and throw a challenge. The challenge is that after a few minutes you should be able to recollect the five names in the same order. Not a big deal, right? Try it with 20 and you’ll realize the difficulty. Memory experts suggest that we associate each object with the next one in the list; or in other words create a link between every neighbouring object. In our case we might say, “A sheep was born on a carpet, the carpet was rolled into a bottle, the bottle smoked a cigar, the cigar was resting in a tent!” The idea is to form comical associations between two objects since these associations are retained in our memory longer. The beauty of this technique is that if your friend names any object from the list, you will be able to say what is the next object in the list (irrespective of the object’s position in the list).

Actual structuring

To aid in the understanding of the linked list concept, let's write a little program which will simulate a linked list. The program should do the following:
Store a set of integers.
It should be possible to delete a particular element.
Permit insertion of a new node (element).
Deletion of a particular node.
A way to display the entire contents of the list.
Let's do this program the OOPs way. First of all we need to have an idea about how we are going to represent a single node of the linked list. The simplest way is to use a structure for a node.

struct node
{
int data;
node *next;
};
'data' is used to hold the data. In this case we are creating a linked list to store only integers (so 'data' is of type int). Every node contains a pointer to the next node. For this we create a pointer pointing to an object of type 'node'. Thus the pointer 'next' will contain the address of the next node.


How is data kept

A data structure is simply a way of organizing data and we have organized data in our shopping list as well. From what we’ve learnt so far we would categorize this as an array perhaps. The information isn’t sorted and we simply keep increasing the list when we think of more things to buy. But the problem with arrays is that they are fixed. You can’t keep on increasing their size as and when you feel like it. So we have a better data structure called a vector to serve this purpose.

"Defined ITS 116"

Kind of Data structure

Definition of Stack

• A stack is a data structure that allows items to be added and removed from one end. That's why it's also described as a LIFO stack. Last In First Out. A stack can be directly compared to some real-life objects. For example, a stack of trays. Trays are only added and removed from the top. A stack of exercise books can also be used as another analogy. Students only take away or pass up exercise books from the top.

Definition of Dictionary

• An abstract data type storing items, or values. A value is accessed by an associated key. Basic operations are new, insert, find and delete.
  Formal Definition: The operations new(), insert(k, v, D), and find(k, D) may be defined with axiomatic semantics as follows.
  new() returns a dictionary
  find(k, insert(k, v, D)) = v
  find(k, insert(j, v, D)) = find(k, D) if k ≠ j

where k and j are keys, v is a value, and D is a dictionary.

Definition of Bag

• An unordered collection of values that may have duplicates.
  Formal Definition: A bag has a single query function, numberIn(v, B), which tells how many copies of an element are in the bag, and two modifier functions, add(v, B) and remove(v, B). These may be defined with axiomatic semantics as follows.
  new() returns a bag
  numberIn(v, new()) = 0
  numberIn(v, add(v, B)) = 1 + numberIn(v, B)
  numberIn(v, add(u, B)) = numberIn(v, B) if v ≠ u
  remove(v, new()) = new()
  remove(v, add(v, B)) = B
  remove(v, add(u, B)) = add(u, remove(v, B)) if v ≠ u
• where B is a bag and u and v are elements.

Definition of Set

• An unordered collection of values where each value occurs at most once. A group of elements with three properties: (1) all elements belong to a universe, (2) either each element is a member of the set or it is not, and (3) the elements are unordered.
  Formal Definition: As an abstract data type, a set has a single query function, isIn(v, S), which tells whether an element is a member of the set or not, and two modifier functions, add(v, S) and remove(v, S). These may be defined with axiomatic semantics as follows.
  new() returns a set
  isIn(v, new()) = false
  isIn(v, add(v, S)) = true
  isIn(v, add(u, S)) = isIn(v , S) if v ≠ u
  remove(v, new()) = new()
  remove(v, add(v, S)) = remove(v, S)
  remove(v, add(u, S)) = add(u, remove(v, S)) if v ≠ u
• where S is a set and u and v are elements.

Definition of Graph

• In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes (also called vertices) and a set of edges that establish relationships (connections) between the nodes. The graph ADT follows directly from the graph concept from mathematics.
  Informally, G=(V,E) consists of vertices, the elements of V, which are connected by edges, the elements of E. Formally, a graph, G, is defined as an ordered pair, G=(V,E), where V is a set (usually finite) and E is a set consisting of two element subsets of V.

Definition of Buffer

• In computing, a buffer is a region of memory used to temporarily hold data while it is being moved from one place to another. Typically, the data is stored in a buffer as it is retrieved from an input device (such as a keyboard) or just before it is sent to an output device (such as a printer). However, a buffer may be used when moving data between processes within a computer. This is comparable to buffers in telecommunication. Buffers can be implemented in either hardware or software, but the vast majority of buffers are implemented in software. Buffers are typically used when there is a difference between the rate at which data is received and the rate at which it can be processed, or in the case that these rates are variable, for example in a printer spooler.

Definition of Hash Table

• In computer science, a hash table, or a hash map, is a data structure that associates keys with values.
• The primary operation that hash functions support efficiently is a lookup: given a key (e.g., a person's name), find the corresponding value (e.g., that person's telephone number). It works by transforming the key using a hash function into a hash, a number that is used as an index in an array to locate the desired location ("bucket") where the values should be.
  In most cases the hash function is deliberately chosen to have pseudo-random properties, so that small changes of key gives a large and apparently random effect (although of course reproducible effect) on the hash returned. Because of this random effect in some cases the calculated index can be the same for two different keys (a "collision"); different hash table designs handle this issue in different ways.

Definition of Skip List

• A skip list is a probabilistic data structure, based on multiple parallel, sorted linked lists, with efficiency comparable to a binary search tree (order log n average time for most operations).
  Underlying the skip list is an augmentation of an ordered linked list with additional forward links, added in a randomized way with a geometric/negative binomial distribution [1], so that a search in the list may quickly skip parts of the list (hence the name). Insert, search and delete operations are performed in logarithmic randomized time.

Definition of Bitboard

• A bitboard, often used for boardgames such as chess, checkers and othello, is a specialization of the bitset data structure, where each bit represents a game position or state, designed for optimization of speed and/or memory or disk use in mass calculations. Bits in the same bitboard relate to each other in the rules of the game often forming a game position when taken together. Other bitboards are commonly used as masks to transform or answer queries about positions. The "game" may be any game-like system where information is tightly packed in a structured form with "rules" affecting how the individual units or pieces relate.

Definition of Priority Queue

A priority queue is an abstract data type in computer programming that supports the following three operations:

• InsertWithPriority: add an element to the queue with an associated priority
• GetNext: remove the element from the queue that has the highest priority, and return it (also known as "PopElement(Off)", or "GetMinimum")
  PeekAtNext (optional): look at the element with highest priority without removing it