Circular and Doubly Linked List PDF

Circular list structure node { int info; struct list *next; } typedef struct node *ptr; Void main() { ptr p; p = (struct node*) malloc (sizeof(struct node)); if ( p != null) insert (p);  Contd.. insert (ptr p, int n) { int i; ptr p1, p2; p1 =...

Circular list structure node { int info; struct list *next; } typedef struct node *ptr; Void main() { ptr p; p = (struct node*) malloc (sizeof(struct node)); if ( p != null) insert (p);  Contd.. insert (ptr p, int n) { int i; ptr p1, p2; p1 = p; p2 = p; for (i = 0; i< n; i++) { p -> data = i; p1= (struct node*) malloc (sizeof(struct node)); p -> next = p1; p = p1; } p -> next = p2; }  Insert a node at the start insert ( ptr p) { ptr p1,q; p1 = p; while ( p1 != p->next) { p = p ->next; } q= (struct node*) malloc (sizeof(struct node)); q -> next = p -> next; p -> next = q; }  Insert at the end insert ( ptr p) { ptr p1,q; p1 = p; while ( p1 != p->next) { p = p ->next; } q= (struct node*) malloc (sizeof(struct node)); q -> next= p -> next; p -> next = q; }  Replace the data in the nth node Void main() { ptr p,q; int n, data; n =4; data =10; replace(p, n, data); } replace( ptr p ,int n, int num) { if (p==null)) printf(“empty list”); for( k=0;knext; p -> data = num; }  Contd.. Limitations of circular list: - Not possible to traverse back - A node can not be deleted given the pointer to that node  Doubly linked list -each node has 2 pointers - One to its next node another to its previous node - traverse both the sides Contd..  Creating a single node Struct node { int info; struct node *pre , *next; }; typedef struct node *ptr;  Contd.. Void main() { ptr p; p= (struct node*) malloc(sizeof (struct node)); p -> info = 10; p-> pre = null; p -> next = null; }  Trees - Is a non linear data structure - Each node can point to more than one node - One node is chosen as the root node - Set of data elements represented in hierarchical fashion in terms of nodes  Contd.. 1. Binary tree 2. Strictly binary tree 3. Complete binary tree  1. Binary tree - Is a tree with set of elements partitioned into 3 disjoint subsets - root - left subtree - right subtree - Can have empty subtrees Contd..  Contd.. Terminologies : a. Father b. Son c. Leaf d. Ancestor e. Descendant f. Brothers  Contd.. a. Father : node A is father if A is the root of a tree and B is the root of its left or right subtree b.Son: B is the left or right son of A c.Leaf : node which doesn’t have sons d.Ancestor : n1 is the ancestor if it is either the father of n2 or the father of some ancestor of n2 e.Descendant: n2 is the descendent of n1 f. Brothers : left and right nodes of the same father node  Contd.. Left descendant : If a node n1 is a left descendant of n2 if n1 is either the left son of n2 or a descendant of the left son of n2 Non binary trees :  2. Strictly binary tree - every non leaf node has nonempty left and right subtrees - if a strictly binary tree has n leaf nodes , then it has total 2n-1 nodes  Contd.. Levels in a tree: root – level 0 son – level 1 etc depth : maximum level of any leaf node - indicates the longest path from root to any leaf node  3. Complete binary tree - is the strictly binary tree where all leaf nodes are in the same level - if the depth of a tree is d , then all the leaf nodes will be at depth d  Contd.. Applications of tree: 1. Hierarchical data representation 2. Evaluation of expression 3. Searching 4. Sorting 5. Storing routing table 6. Directories  Contd.. 1. If a complete binary tree has N nodes at a level L contains atmost 2N nodes at level L+1 2. A complete binary tree with depth D contains exactly 2L nodes at each level L no of nodes at level D = 2D no of non leaf nodes = 2D - 1 total nodes tn =20 + 21+ …..+2D = sum(2k) where k= 0 to D  Almost complete binary tree Binary tree of depth D is an ACBT if 1.Any node at level less than D-1 has 2 sons 2.For any node in the tree with a right descendant at level D , node must have a left son and every left descendant of node is either a leaf at level D or has 2 sons  Tree construction 14 ,15,4,9,7,18,3,5,16,20,17 first element is taken as root Right node is > root left node < root 14 4 15 3 9 18 7 16 20 5 14 17  Operations 1. finding duplicate 2. Traversal 3. Searching 4. Sorting  1. Traversal a. Preorder b. Inorder c. Postorder  Contd.. 1. Preorder : start from root – left subtree(PO)- right subtree (PO) 2. Inorder : start from left subtree(IO)- root- right subtree (IO) 3. Post order: start from left subtree(PSTO) – right (PSTO)- root