×
☰ Menu

Various Types of Data Structures

 

(a) Arrays

A linear array is the simplest type of data structure, and it is usually the only one that is available in any programming language. An array is a group of elements that are all the same and are stored in contiguous memory locations as pairs of index and value. An array's size is always set ahead of time, and its parts are referred to by an index or subscript. So, an array is a group of variables with the same type of data and share a common name. The general form of a one-dimensional array is

 

Advantages and Limitations of array

Searching is faster as elements are in contiguous memory locations. The total number of elements must be known in advance. Inserting and Deletions are complex as it includes shifting the rest of the elements.

 

(b) Stack

A stack is an ordered list in which items are inserted and removed at only one end called the TOP. There are only two operations you can do with the stack, the 'Push' and the 'Pop' operations. The Pop operation retrieves a value from the stack and removes it from the stack after the Push operation inserts the value into the stack. A stack of plates arranged on a table is an example of a stack. This means that the last item to be added is the first item to be removed. Hence a stack is also called a Last-In-First-Out List or LIFO list. A graphical representation of a stack is shown below:

 

(c) Queue

A queue is an ordered list in which all insertions can take place at one end called the rear and all deletions take place at the other end called the front. The two operations that are possible in a queue are Insertion and Deletion. A real-time example of a queue is people standing in a queue for billing on a shop. The first person in the queue will be the first person to get the service. Similarly, the first element inserted in the queue will be the first one that will be retrieved, and hence a queue is also called a First In First Out or FIFO list.

 

 

The most common occurrence of a queue in computer applications is for scheduling of print

jobs. For example, if several people are giving print requests, all the request get queued up in

the printer and is processed on first come first serve basis.

 

(d) Linked Lists: In most real-time systems, the number of elements will not be known in advance. The main problem with an array is that you have to know how many elements it will have ahead of time. So, a different way of doing things was needed. This is where the idea of "linked lists" comes from. A linear list is a list of data items, called nodes, that are arranged in a straight line. Pointers show the order of the nodes in the list. The key here is that each node will have two parts: the first part will have the information or data, and the second part will have the link or address of the next node in the list. Memory is given to each node only when it is needed, and it is taken away when it is no longer needed.

 

 

In computer applications, linked lists are used to allocate memory. A list keeps track of all the available memory in the system. Memory pools are areas of memory. As and when the user requests memory, the system allocates memory from this pool to the user. As soon as these blocks are allocated, they will be removed from the list of available blocks. The memory will be added to the list once the user frees it again. Whenever a collection of elements is required and the number of elements is unknown in advance, linked lists are used almost everywhere.

 

(e) Tree: A tree is a non-linear data structure. This structure is mainly used to represent data containing a hierarchical relationship between elements like family tree, organization chart etc.