Thursday, May 12, 2011

Practical Implementation of Data Structures in Computers


Practical Usage of Data Structures in Computers

  1. Stack - any recursive call
  2. Queue, Circular Queue - all the FIFO algo use this
  3. Linked List, Doubly Linked list, Circular Linked list - all the RDBMS
  4. Tree, Binary Search Tree - Where searching is required. Memory is stored in B tree
  5. Graph - Google Maps

Data structure is a particular way of storing and organizing information in a computer so that it can be retrieved and used most productively.
Different kinds of data structures are meant for different kinds of applications, and some are highly specialized to specific tasks.
Data structures are important for the following reasons:
  1. Data structures are used in almost every program or software system.
  2. Specific data structures are essential ingredients of many efficient algorithms, and make possible the management of huge amounts of data, such as large integrated collection of databases.
  3. Some programming languages emphasize data structures, rather than algorithms, as the key organizing factor in software design.

Stack
Undo functions use this to pop most recent action off top of stack, then second most recent, etc.
Queue
Process Scheduling normally uses a queue (how processes or threads are accessed after the initial work varies though). A queue is often used to save a group of data in an organized structure so that it is easily accessed immediately when needed since its a FIFO (First in first out). However; when filling information into that queue when that queue is FULL the rest of the information is lost. To combat this circular queue is used, which overwrites the other elements so that recent data is NOT lost.
                           An example of this like you mentioned would be the queue of resources of a computer. Because a computer does not have infinite resources a queue has to be used in order to allocate resources to those that need it. For instance a process would request some resources and it would be thrown into the queue and be given a priority level, based on this information the OS would then make a decision how many resources it needs and how much time it will be given. In order to allow multiple processes to make use of this, any process that has processing that needs to be done will put in a request in that queue.
Tree
Directory traversal
Binary Search Tree
Searching quickly for a given element
Graph
Stores data so that you can think of it as a mathematical "plane" where the data is plotted. It is effective at representing (possibly) very complicated relationship between data, since (if you look at the image in the link) multiple "links" can exist between more than two pieces of data, as opposed to a linked list where you can only have a link to your left and to your right.
Hash Map
Searching for certain blocks of memory (i.e. when using many pointers) Hashing occurs when you have, say, an address book on your computer. It might use a hash map so that when you enter John Smith, his phone number and other information are available. This is because there is a hashing function that points to a certain location in memory when "John Smith" is entered. It would be a headache entering a memory address every time you wanted to access some simple information.
Linked List
Singly linked list offers movement in one direction between elements, doubly linked list offers movement back and forth between elements, and Circular linked list offers Circular navigation of similar objects (processes are one example) Use this when you want to be able to navigate between elements, because each element is linked to the next one and the one before it (for circular. noncircular linked lists have a beginning and an end). Imagine your web browser...you click "back" to go to the previous page, and you can click "forward" to go to the next. You can think of this as a linear linked list. A photo slide show that goes to the next or previous photo and then eventually starts at the beginning can be thought of as a circular linked list. (They're not necessarily implemented like that but it's a good way to visualize it)
A linked list has many applications that it’s not really possible to simplify it into one. For instance, you could link accounts (objects) through the queue of the nodes of an element in the linked list. In a linked list, a node has a previous and a next node, which effectively links all the elements together so that they can be traversed. Depending on the style of the linked list, this allows forward traversal backward traversal, or both directions. One thing to note is that a linked list can be dynamic in terms of size since all that needs to be done to add a new note is just attach it to the end of the list. However; in terms of performance the speed of that would be O (N) which means that the performance is heavily dependent on the size of the list.

Two data structures that are primarily used in a file cabinet are:-

1>Arrays

2>Link Lists

ARRAYS:-

Arrays are linear data structures consisting of a group of elements that are accessed by indexing. In most programming languages each element of array has the same data type and the array occupies a contiguous area of storage.

By data types we refer to integers, characters etc.

Integer arrays can be used to store numbers and similar numerical values.

Similarly character arrays can be used to store series of characters and so can be used to store names, address, and other strings.

So as a file cabinet consists of different files with variety of information, these arrays can be used to store variety of data.

Implementation of arrays is easy(can be implemented by several programming languages including C and C++)

We can also assign memory to arrays statically and dynamically.

Arrays are also used to implement mathematical vectors and matrices, as well as other kinds of rectangular tables. In early programming languages, these were often the applications that motivated having arrays.

Because of their performance characteristics, arrays are used to implement other data structures, such as heaps, hash tables, queues, deques, stacks, strings, lists etc .So am major tool to implement several other data structures.

 LINK LISTS:-

A 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. A linked list is a self-referential data type because it contains a pointer or link to another datum of the same type. Linked lists permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access. Several different types of linked list exist: singly-linked lists, doubly-linked lists, and circularly-linked lists.

Linked lists can be implemented in most languages. Languages such as Lisp and Scheme have the data structure built in, along with operations to access the linked list. Procedural or object-oriented languages such as C, C++, Java typically rely on mutable references to create linked lists.


Linked lists are used as a building block for many other data structures, such as stacks, Queues and their variations.

The "data" field of a node can be another linked list. By this device, one can construct many linked data structures with lists.


It is necessary to emulate these types of data structures as these are the basic data structure types and other compels data structures can be built from this.
These data structures are excellent means of storing and accessing data.

I would use this type of program in a typical project like a railway reservation project or a library system. Here we need to store a lot of data and need to frequently access these data. So these data structures can come handy.

No comments:

Post a Comment

Amazon Deals