Wednesday, December 12, 2012

Collection Framework: Missing concepts - 2

Introduction

In my last post, I outline a brief of heart of the collections in java. In this second part of the I am discussing it further. In the post focused on study of container with access point of view.

As we know Container is most commonly used datatype. Each of the datatype provides a uniform set of operations to manage container based on the their internal storage methods. Both object description and storage method in a container can be dynamically changed so that abstract operations can be exactly matched with the run time requirement for operational flexibility and performance.

So, A container data type is an interface to manage collection of objects. An instance of a container datatype is a container. Common data structure to implement container data types are :
  1.  List 
  2. Stack
  3. Queue
  4. Set
  5. Map
Each of the above data structure has unique operational an performance properties. All container data types support the same abstract set of operations
  1. Insert
  2. Delete
  3. Search 
  4. Iterate.

List

List is by far the most commonly used container datatype. It stores a list of objects of a given type. The stored objects can be accessed by index. Internally, the List is implemented using an array, ensuring that index-based access is very fast.
Lists are typically implemented either as linked lists (either singly or doubly linked) or as arrays, usually variable length or dynamic arrays.

Stack

A stack is a basic data structure, where insertion and deletion of items takes place at one end called top of the stack. This structure is used all throughout programming. The basic concept can be illustrated by thinking of your data as a stack of plates or books where you can only take the top item off the stack in order to remove things from it. The two operations applicable to all stacks are:
  • a push operation, in which a data item is placed at the location pointed to by the stack pointer, and the address in the stack pointer is adjusted by the size of the data item;
  • a pop or pull operation: a data item at the current location pointed to by the stack pointer is removed, and the stack pointer is adjusted by the size of the data item.
Stack data structure is  designed as a type of queue; they form Last-In-First-Out (LIFO) queues. 

Queue

In Queue data structure the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once an element is added, all elements that were added before have to be removed before the new element can be invoked.

Set

Set is an abstract data structure that can store certain values, without any particular order, and no repeated values

Map

Map is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

That is all for now.................

No comments:

Post a Comment