Linked List

Linked List Linked List Definition A linked list is a dynamic data structure where a  node  is made up of two items - the data and a reference (or pointer) which points to the next node. A linked list is a collection of nodes where each node is connected to the next node through a pointer. The first node is called a  head  and if the list is empty then the value of head is NULL.For a real-world analogy of linked list, you can think of conga line, a special kind of dance in which people line up behind each other with hands on shoulders of the person in front. A Simple Linked List Circular Single Linked list In Circular Single Linked List, last node contains a pointer to the first node, We can have a circular singly linked list as well as a circular doubly linked list. There is no storing of NULL values in the list Implementation Insertion A node can be added in three ways: Insertion in an empty list Insertion at the beginning of the li...

Binary Search Tree Definition Binary search tree (BST), also known as sorted binary tree, is a node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree. The left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node.The BST data structure is the basis for a number of highly efficient sorting and searching algorithms, and it can be used to construct more abstract data structures including sets, multisets, and associative arrays. BST Rules For a node x in of a BST T, –the left subtree of x contains elements that are smaller than those stored in x, –the right subtree of x contains all elements that are greater than those stored in x, Binary Search Tree Operations Search() : find key in the BST  Whenever an element is to be searched, start searching from the root node. Then if th...

Stack And Queue Stack Stack is a basic data structure that can be logically thought of as a linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack.  The basic implementation of a stack is also called a LIFO (Last In First Out) to demonstrate the way it accesses data, since as we will see there are various variations of stack implementations. There are basically three operations that can be performed on stacks. They are inserting an item into a stack (push), deleting an item from the stack, and displaying the contents of the stack. Array Representation •Stack has two variables: -TOP which is used to store the address of the topmost element of the stack. -MAX which is used to store the maximum number of elements that the stack can hold. -If TOP = NULL, then indicates that the stack is empty. -If TOP = MAX – 1, then the stack is full. Linked List Representati...