Array
An array is a homogeneous and linear data structure that is stored in contiguous memory locations. An element in an array can be accessed, inserted or removed by specifying its position or index or subscript along with the name of the array.
Linked List
Linear or Singly Linked List
A linear or singly linked list is a linear data structure consisting of a sequence of nodes. Each node consists of two parts – Data and Link to the next node. The address of first node is stored in a pointer Start.
Each node stores the address of its next node in its link part. The linked list is non-contiguous collection of nodes that allows insertion and deletion at any specific location.
Doubly Linked List– A doubly linked list is a linear data structure consisting of a sequence of nodes. Each node consists of three parts – Data, Forward Pointer to the next node and Backward Pointer to the previous node.
The address of first node is stored in a pointer called the Header and address of last node is stored in pointer called the Trailer. The doubly linked list allows traversal in forward and backward direction.
Difference between array and linked list
| Array | Linked List |
| Deletion involves movement of elements forward | Deletion is easy without any movement of elements |
| Insertion involves movement of elements backward | Insertion is easy that does not require any movement of existing elements |
| Contiguous memory space requirement is prerequisite | Nodes can be stored at scattered locations in memory |
| Array size has to be defined so wastage of memory incase all elements are not stored in an array | Nodes need to store addresses also, so there can be wastage of memory but not because of un utilized memory space |
| Arrays can be accessed backward and forward | Special link lists like doubly linked list have to be defined for backward access |
| Arrays definition is part of the language construct | Linked list is a logical representation and have to be implemented in a programming language |
| Merging two arrays is very difficult | Merging link lists is easy |
Stack
Stack is a linear data structure that follows Last in First out (LIFO) principle. Insertion (push) and Deletion(pop) are done at one end and other end is closed.
Most common applications of a stack are
- Page-visited history in a Web browser,
- Undo sequence in a text editor,
- chain of method calls in recursive functions,
- evaluation of postfix expressions.
Stacks are also used to implement traversal in DFS for a graph. Stack makes an essential data structure for OS functions and execution of arithmetic expressions.
The maximum size of the stack must be defined a priori and cannot be changed. Trying to push a new element into a full stack causes an implementation-specific exception.
Queue
Queue is a linear data structure that follows the first-in first-out scheme. Insertions are done at the rear of the queue and removals at the front of the queue. Two variables needed for these operations are the front and rear.
A variation of Queue is Dequeue in which deletions and insertions can be done at both ends. Applications of Queue are
- Operating system scheduling lists,
- Access to shared resources (e.g. printer),
- Multi-programming
- Implementation of other Data Structures like BFS in graph traversal.
Priority Queue-priority queue is a linear data structure that behaves like a queue where each element has a priority associated with it on the basis of which deletions are done. The element with maximum (minimum) priority will be deleted from the queue. It can also be defined as a data structure that supports operations of min or max insert, delete or search.
A priority queue can be represented in two ways:
- As an unordered Linked list where insertions are made at the rear without considering priority but at time of deletion the priority is considered, which means a min or max search is needed.
- As an ordered Linked list where insertions are made at the correct location in the queue according to priority. Since the elements of queue are already in order deletion requires the normal operation at the front.
- A max or min heap can be used where insertion and deletion is performed in O(logn) time
Heap– A max(min) heap is a complete binary tree with the property that the value of each node is at least as large(small) as the values at its children. If the elements are distinct then the root node will be the largest (smallest).
The insertion will always be done as a leaf node first and then the heap will be “heapified” to bring the newly inserted node at its correct position. Heapify means that the node will be compared with its parent and if it is larger(smaller) than its parent then there will be an interchange between parent node and the newly inserted child node. This process will end up in a heap after insertion.
Deletion will be done at the root node. The last node of the complete binary tree will replace the deleted root node and then the process of heapify will be done starting from the new root node.
Good job. very clear explanations.