Introduction To Data Structures PDF

Introduction To Data Structures Presented By Ms. Sujata S. Kullur Assist. Prof. IT Department  Definition Of Data Structures A Data structure is a particular way of storing and organising data in a computer so that it can be used efficiently. Data Structure is the s...

Introduction To Data Structures Presented By Ms. Sujata S. Kullur Assist. Prof. IT Department  Definition Of Data Structures A Data structure is a particular way of storing and organising data in a computer so that it can be used efficiently. Data Structure is the structural representation of logical relationships between elements of data. A Data Structure is a method of representing data. It is not only deals with raw data but also involves the relationship between data.  The study Of Data Structure It Includes:- Logical description of data structure. Implementation of data structure. Quantitative analysis of data structure.  Types of Data Structure Static & Dynamic Data Structures Linear & Non-linear Data Structures Primitive and Non-Primitive Data Structures Homogeneous and Non-homogeneous Data Structures Linear & Non-linear Data Structures Linear Data Structures Array Stack Queue Link List Non-linear Data Structures Tree Graph  Operations On Data Structures Creation- first operation to create data structure Insertion- adding new record Deletion- removing a record Updating- changes data value Traversing- accessing each record exactly Searching- finding the location of the record Sorting- arranging data elements in logical order Merging- combining data elements in single set Areas where Data Structures are used Database Management System Compiler Design Network Analysis Numerical Analysis Artificial Intelligence Statistical Analysis Simulation Operating System Graphics  Stack Stack is an ordered list in which items are inserted and removed at only one end called TOP. It is a List In First Out List Procedure PUSH(S,Top,X) 1. check for stack overflow if Top  N then Write(“Stack overflow”) return 1. Increment Top Top Top+1 3. Insert element S[Top] X 4. finished return Stack: Insertion(PUSH) Top=0 Stack empty Stack: Insertion(PUSH) Top=Top+1 10 One element Inserted Stack: Insertion(PUSH) 20 Top=Top+1 10 Next element Inserted Stack: Insertion(PUSH) 30 Top=Top+1 20 10 Next element Inserted Stack: Insertion(PUSH) Top=Top+1 40 30 20 10 Last element Inserted Stack Full or Overflow Procedure Pop(S,Top) 1. Check for underflow on pop if Top =0 then Write(‘Stack underflow on pop’) take action in response to underflow Exit 2. Decrement pointer Top Top –1 3. Return former top element of stack Return(S[Top +1]) Stack: Deletion(POP) Top=Top-1 30 20 10 Element Deleted Stack: Deletion(POP) Top=Top-1 20 10 Element Deleted Stack: Deletion(POP) 10 Top=Top-1 Element Deleted Stack: Deletion(POP) Top=Top-1 Stack Under Flow Stack Empty  Queue A Queue is an Ordered List in which all insertions can take place at one end called REAR and all deletions take place at other end called FRONT. It is called as First In First Out List. Procedure QINSERT(Q,F,R,N,Y) 1 Overflow? If R>= N Then Write “OVERFLOW” return 2 Increment the rear pointer R R+1 3 Insert element Q[R] Y 4 Is front pointer properly set? If F=0 F Return  Queue Insertion F R Queue Insertion 10 F R Queue Insertion 10 20 F R Queue Insertion 10 20 30 F R  Queue Insertion 10 20 30 40 F R Queue Full or Overflow Procedure QDELETE(Q,F,R) 1 Underflow? If F= 0 Then Write “UNDERFLOW” return 2 Delete element Y Q[F] 3 Queue empty If F=R Then FR0 else FF+1 4 Return element Return (Y)  Queue Deletion 20 30 40 F R First In First Out  Queue Deletion 30 40 F R First In First Out  Queue Deletion 40 F R First In First Out  Queue Deletion F R Queue Empty or Under Flow  Procedure CQINSERT(Q,F,R,N,Y) 1Reset rear pointer? If R=N then R 1 Else RR+1 2 Overflow? If F=R Then Write “OVERFLOW” Return 3 Insert element Q[R] Y 4 Is front pointer properly set? If F=0 F Return Procedure CQDELETE(Q,F,R,N) 1 Underflow? If F= 0 Then Write “UNDERFLOW” Return(0) 2 Delete element Y Q[F] 3 Queue empty ? If F=R Then FR0 Return(Y) 4 Increment front pointer If F=N Then F=1 else FF+1 Return (Y) Linked List A linked list is a data structure which allows to store data dynamically and manage data efficiently. Typically, a linked list, in its simplest form looks like the following FIRST A B C NULL Linked List There is a pointer (called FIRST) points the first element (also called node) Successive nodes are connected by pointers. Last element points to NULL. It can grow or shrink in size during execution of a program. It can be made just as long as required. It does not waste memory space, consume exactly what it needs. Arrays versus Linked Lists Array: Contagious Storage Array versus Linked Lists In arrays elements are stored in a contagious memory locations Arrays are static data structure unless we use dynamic memory allocation Arrays are suitable for  Inserting/deleting an element at the end.  Randomly accessing any element.  Searching the list for a particular value. Linked List: Non-Contagious Storage a 15 b 45 c 25 d 50 e 22 f 35 g 30 h 10 i 20 j k 40 Array versus Linked Lists In Linked lists adjacency between any two elements are maintained by means of links or pointers It is essentially a dynamic data structure Linked lists are suitable for  Inserting an element at any position.  Deleting an element from any where.  Applications where sequential access is required.  In situations, where the number of elements cannot be predicted beforehand. Insertion in a Linked List Single Linked List: Insertion Insertion steps: Create a new node Start from the header node Manage links to Insert at front Insert at end Insert at any position FIRST Singly Linked Lists LINK LINK LINK LINK a b c d First node Last node  Availability Stack AVAIL LINK d c b a  Availability Stack NEW AVAIL d c b a Insertion of node First INSERT(X, FIRST) 1.Underflow? if AVAIL=NULL then Write (‘Availability stack is empty’) Return (FIRST) 2. Obtain address of next free node NEW  AVAIL 3. Remove node from availability stack AVAIL  LINK( AVAIL) 4. Initialize fields of new node INFO(NEW) X LINK(NEW)FIRST 5. Return address of new node Return(NEW) Insertion of node at end INSEND(X, FIRST) 1.Underflow? if AVAIL=NULL then Write (‘Availability stack is empty’) Return (FIRST) 2. Obtain address of next free node NEW  AVAIL 3. Remove node from availability stack AVAIL  LINK( AVAIL) 4. Initialize fields of new node INFO(NEW) X LINK(NEW)NULL 5. Is the list empty if FIRST=NULL then Return(NEW) 6. Initiate search for end of list SAVE  FIRST 7. Search for end of list Repeat while LINK(SAVE) ≠ NULL SAVE  LINK(SAVE) 8. Set LINK field of last node to new LINK(SAVE) NEW 9. Return first node pointer Return(FIRST) Insertion of node in order INSORD(X, FIRST) 1.Underflow? if AVAIL=NULL then Write (‘Availability stack is empty’) Return (FIRST) 2. Obtain address of next free node NEW  AVAIL 3. Remove node from availability stack AVAIL  LINK( AVAIL) 4. Initialize fields of new node INFO(NEW) X 5. Is the list empty if FIRST=NULL LINK(NEW) NULL then Return(NEW) 6. Does the new node precede all others in the List If INFO(NEW) ≤ INFO(FIRST) Then LINK(NEW) FIRST Return(NEW) 7. Initiate search predecessor of new node SAVE  FIRST 8. Search for end of list Repeat while LINK(SAVE)≠ NULL and INFO(LINK(SAVE)) ≤ INFO(NEW) SAVE  LINK(SAVE) 9. Set LINK field of last node to new LINK(NEW)  LINK(SAVE) LINK(SAVE) NEW 10. Return first node pointer Return(FIRST) Deletion from a Linked List Single Linked List: Deletion Deletion steps Start from the header node Manage links to Delete at front Delete at end Delete at any position freeingup the node as free space. Free Memory after Deletion Do not forget to free() memory location dynamically allocated for a node after deletion of that node. It is the programmer’s responsibility to free that memory block. Failure to do so may create a dangling pointer – a memory, that is not used either by the programmer or by the system. The content of a free memory is not erased until it is overwritten. Deletion of node First DELETE(X, FIRST) 1.Empty List? if FIRST=NULL then Write (‘Underflow’) Return 2. Initialize the search for X TEMP  FIRST 3. Find X Repeat thru Step 6 while TEMP ≠ X and LINK(TEMP) ≠ NULL 4. Update Predecessor Marker PRED TEMP 5. Move to next Node TEMP LINK(TEMP) 6. End of the list? If TEMP ≠ X Then Write (‘Node not found’) Return 7. Delete X If X= FIRST (Is X first Node?) then FIRST LINK(FIRST) Else LINK(PRED) LINK(X) 8. Return node to availability area LINK(X) AVAIL AVAIL X Return Hashing Hashing is a technique used to performing insertion, deletion & search operations in the constant average time by implementing Hash table data structure. It is used to determine the presence or absence of an arbitrary element in a Symbol Table. It is used to Index and Retrieve items in a Database. Two Types of Hashing 1. Static Hashing 2. Dynamic Hashing Static Hashing : It is the hash function maps search key value to a fixed set of locations. Dynamic Hashing : The Hash Table can grow to handle more Items. The associated Hash Function must change as the table grows. Hash Table & Hash Function Hash Table The Hash Table data structure is a array of some fixed size table containing the Keys. A Key is a values associated with each record. A Hash table is partition into array of size. Each Bucket has many slots and each slots holds one records. Hash Function A Hashing Function is a key to address transformation which acts upon a given Key to complete the relative position of the Key in a array Hashing fv(X) = X modM A Key can be a member of a String etc.. A Hash Function Formula is Hash (Key Value ) =(Key Values % Table Size) Hash(10) =10 % 5=0 Hash(33) =33 % 5 =3 Hash(21)= 21 % 5=1 Hash(11)=11 % 5=1 Hashing A good Hashing consist of Minimum collision. Be easy and quick to complete. Distribute Key Value in the Hash Table. Use all the Information provided in the Key. Application of Hash Table: Database Systems Symbol Tables Data Dictionaries Network Processing Algorithm Collision Collision occurs when a hash values of a records being inserted hashes to an address that already contains a different record. “ When two key values hash to the same position”. Collisions and overflows occur simultaneously. Insert 11,21 in hash table 11 =Hash(11) =11%5 =1 21= Hash (21) =21%5 =1 (collision occur) Hashing Collision Resolution : The process of finding another position for the collide record is said to be collision Resolution Strategy. Two categories of Hashing. 1. Open Hashing eg: Separate Chaining. 2. Closed Hashing eg : Open Addressing ,Rehashing and Extendable hashing. Hashing Open Hashing : Each Bucket in the Hash table is the head of a Linked List. All Elements that hash to a Particular Bucket are Placed on the Buckets Linked List. Closed Hashing: Ensures that all elements are stored directly in to the Hash Table. Linear Hashing Linear hashing: Collide elements are stored at another slot in the table. Ensures that all elements stored directly in the hash table.  Linear hashing Procedure LINSEARCH(X,HT,b,j) //search the hash table HT(0:b-1)(each bucket has //exactly 1 slot) using linear probing.If HT(j)=0 // //then the j-th bucket is empty and X can be entered // //into the table.Otherwise HT(j)=X and X is //already in the table.F is the hash function// i  f(X);ji while HT(j)  X and HT(j)  0 do j  (j+1) mod b //treat the table as circular// if j=I then call TABLE-FULL endif //no empty slot// repeat end LINSEARCH Chaining Chaining is an open hashing Technique A Pointer fields is added to each record Location. In this method the table can never overflow since the linked are only extended upon or New Keys. Traverse the list to check whether it is already present. If is not already present, insert at end of the list similarly, the rest of the elements are inserted. Example: 10 , 11 , 81 , 10 , 7 , 34 , 94 , 17 , 29 , 89 , 99 CHAPTER 1 69  Chaining Advantages More number of elements can be inserted as it uses of linked list. Collision resolution is simple and efficient. Disadvantages It requires pointers, which occupies more memory space. Disadvantages: It requires pointers, which occupies more memory space.  Hashing With chaining Procedure chnsrch(X,HT,b,j) //search the hash table HT(0:b-1) for X.// //Either HT(i) =0 or it is a pointer to the list of // //identifiers X such that f(X) = i. List nodes have fields// //IDENT and LINK.Either j points to the node // //already containing X or j=0// j  HT(f(x)) //compute head node address// //search the chain starting at j// while j  0 and IDENT(j)  X do j  LINK(j) repeat end CHNSRCH