Introduction to Data Structure and Algorithm [Explore Java]

Definition of Data Structure

Data Structure is a method of organizing huge amount of data for ease access and manipulation. Array, Linked List, Tree, Graphs are examples of Data Structure.

Linked List

Linked List is collection of nodes; nodes are containers having at least two parts: one for storing data and another for storing address of another node. Linked List is very flexible kind of data structure; insertion and deletion of any node from any position is possible, but random access of the nodes is not possible in the linked list It is necessary to remember address or reference of the first node of the linked list. From first node all the remaining nodes of the list can be traversed sequentially. The last node of the Linked list contains data and address of nothing or null.

Doubly Linked List:

Doubly linked list is a chain of nodes, the node of the doubly linked list has three fields or parts; one part contains address of the preceding node, second part contains data and third part contains address of the successor node. In doubly linked list address or reference of the first nodes must be known. In doubly linked list back tracking is possible, that is traversing backwards from last node to the first node is possible. Backtracking is not possible with singly linked list.

Circular Linked list:

In circular linked list, the last node of the list contains reference or address of the fist node (head node).

Skip List:

Sequential access is the only method to traverse linked list (both singly and doubly). So, traversing or searching data in the linked list will be slow. If the data of the linked list can be stored in order, then skip lists of the original linked list can be created. Skip list contains reference to the intermediate nodes of the list. Fist search is performed on the skip list sequentially to find the range within which the search node lies. As, range is found in the skip list then sequential search only between the found range is performed on the original list. This idea of creating skip list reduces search time in the linked list.

 

Stack:

Stack is a data structure in which elements can be added and removed from one end known as "TOP". Stack is also known as Last in First out (LIFO). The last element inserted in the stack is the first element to be removed from the stack. Inserting element in the stack is known as PUSH operation and removing element from the stack is known as POP operation. Stack can be implemented using array or linked list. Array implementation of Stack is static in nature; that is the size of stack if fixed. Linked List implementation of Stack is dynamic.

Queue:

Queue is a data structure in which elements are added from the end known as rear and removed from another end known as front. The first element inserted to the queue is the first element to be removed. It is also known as First in First out (FIFO). Queue can be implemented either using array or linked list.

Circular Queue:

In circular queue the last element is placed next to the first element of the queue, such that a circle is formed.

Priority Queue:

Elements of the queue are given priority and based on the priority elements are removed from the queue.

Tree:

Tree is a data structure in which elements are stored in hierarchical manner. The first node of the tree is known as root node and nodes below the root are either internal node or leaves. Internal nodes will have children and leaves don't have child. Nodes are organized in different levels. Node of level 'l' is parent of node at level 'l+1'. Tree does not contain cycle, that is, it is not possible to come back to the node from where traversal or searching was started.

Binary Tree:

Binary Tree is tree in which each node can have 0, 1 or 2 children. Each node can have left child, right child or no child. Each child is binary tree in itself. First node of the tree is known as root node. The tree data structure uses node similar to node of doubly linked list to stored data and addresses of successors.

Binary Search Tree:

Binary Search Tree is a binary tree in which value stored in the parent node is greater than the value stored in its left children and less than value stored in its right children.

Tree traversal:

Visiting each node of the tree at least once is traversing tree. Binary Tree can be traversed in three different ways:

• Preorder Traversal: First visit root, then left child, then right child
• Inorder Traversal: First visit left child, then root node, then right child
• Postorder Traversal: First visit left child, then right child, then root of the tree

Breadth First Search (BFS):

In Breadth First Search (BFS) elements of the tree is searched level by level. First root is searched, then all the nodes of the second level is (immediately children of the root) searched, then nodes of third level is searched and so on.

This is the brief description of the syllabus of Data Structure and Algorithm of BIM 4th semester.