DATA STRUCTURES


A data structure organizes related data in a computer so that it can be used efficiently. 
Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, graphs are used to represent connections on social websites (such as Twitter, Facebook), trees are used to represent hierarchical data, such as files and folders in a filesystem, queues can be used to create task schedulers, compiler implementations usually use hash tables to look up identifiers, binary trees are used in searching algorithms, etc.

Usually, choosing the correct data structure is key to designing an efficient algorithm.

Some of the most common data structures are:
 - Array
 - Linked List
 - Stack, Queue
 - Graph, Tree
 - Hash Table

Some data structures can be used to create others, for example, linked lists can be used to create stacks and queues.

"Each data structure has a set of operations that can be performed on the data it stores. We select a data structure based on the operations required to implement an algorithm."

Array

Array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. An array is stored so that the position of each element can be computed from its index tuple by a mathematical formula. The simplest type of data structure is a linear array, also called one-dimensional array.

For example, an array of 10 32-bit integer variables, with indices 0 through 9, may be stored as 10 words at memory addresses 2000, 2004, 2008, ... 2036, so that the element with index i has the address 2000 + 4 × i.

Linked List 

The linked list data structure is often used to implement other data structures.
A linked list is a sequence of nodes where each node stores its own data and a pointer (address) to the location of the next node.
One node links to another forming what can be thought of as a linked chain:

The last item in the list has a link to NULL, indicating the end of the chain.

Advantages:
Although a linked list is similar to an array, it is not restricted to a declared number of elements. Additionally, unlike an array which stores data contiguously in memory or on disk, a linked list can easily insert or remove elements without reallocation or reorganization of the entire structure because the data items need not be stored contiguously.

Linked List Drawbacks:
1) Random access is not allowed. We must access nodes sequentially starting from the first one. Therefore, we cannot do a binary search on a linked list.
2) Extra memory space for a link is required for each element of the list.

"Linked lists are generally used as the fundamental building block for implementing data structures such as stacks, queues, trees, and graphs."
Next >>  1 2 3 4




Latest


EmoticonEmoticon