UNIT – IOverview of data structure, Basics of Algorithm Analysis including Running Time Calculations, Abstract DataTypes, Arrays, Arrays and Pointers, Multidimensional Array, String processing, General Lists and List ADT, Listmanipulations, Single, double and circular lists. Stacks and Stack ADT, Stack Manipulation, Prefix, infix andpostfix expressions, recursion. Queues and Queue ADT, Queue manipulation.UNIT – IISparse Matrix Representation (Array and Link List representation) and arithmetic (addition, subtraction andmultiplication), polynomials and polynomial arithmetic.Trees, Properties of Trees, Binary trees, Binary Tree traversal, Tree manipulation algorithms, Expression treesand their usage, binary search trees, AVL Trees, Heaps and their implementation, Priority Queues, B-Trees, B*Tree, B+ TreBASED ON MY SYLLABUS TELL ME IN WHICH UNIT IS LINKED LIST ,SINGLY LINKED LIST DOUBLY LINK LIST THERE

"Data Structures and Algorithms

Algorithm design, Complexity, Time-Space Trade offs. Use of pointers in data structures

Cheat SheetThis is a compilation of worst-case complexities for various data-structures and algorithms.Data-StructuresData Structure Worst Case Complexity NotesArray Insert O(1)Retrieve O(1)Linked List Insert at Tail O(n)Insert at Head O(1)Retrieve O(n)Note that if new elements are added at the head of the linkedlist then insert becomes a O(1) operation.Binary Tree Insert O(n)Retrieve O(n)In worst case, the binary tree becomes a linked-list.Dynamic Array Insert O(1)Retrieve O(1)Note by retrieving it is implied we are retrieving from a specific index of the array.Stack Push O(1)Pop O(1)There are no complexity trick questions asked for stacks or queues. We only mention them here for completeness. The two data-structures are more important from a last-in last-out (stack) and first in first out (queue) perspective.Queue Enqueue O(1)Dequeue O(1)Priority Queue (binary heap) Insert O(lgn)Delete O(lgn)Get Max/Min O(1)Hashtable Insert O(n)Retrieve O(n)Be mindful that a hashtable's average case for insertion and retrieval is O(1)B-Trees Insert O(logn)Retrieve O(logn)Red-Black Trees Insert O(logn)Retrieve O(logn)AlgorithmsCategory Worst Case Complexity NotesSorting Bubble Sort O(n2)Insertion Sort O(n2)Selection Sort O(n2)Quick Sort O(n2)Merge Sort O(nlgn)Note, even though worst case quicksort performance is O(n2) but in practice quicksort is often used for sorting since its average case is O(nlgn).Trees Depth First Search O(n)Breadth First Search O(n)Pre-order, In-order, Post-order Traversals O(n)n is the total number of nodes in the tree. Most tree-traversal algorithms will end up seeing every node in the tree and their complexity in the worst case is thus O(n).

i. First-in-first out types of computations are efficiently supported by STACKS. ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations. iii. Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices. iv. Last-in-first-out type of computations are efficiently supported by QUEUES.1 point(i) and (ii) are true(ii) is true(iii) is true(ii) and (iv) are true

. Which data structure is used for implementing recursion?a) Stackb) Queuec) Listd) Array