DS_new_Unit3.pdf

UNIT-3 New Syllabus Linked List & its storage representation  A linked list is a linear or dynamic data structure which is defined as a collection of data elements, called nodes.  Each node contains is divided into two parts. 1. INFO Part 2. LINK...

UNIT-3 New Syllabus Linked List & its storage representation  A linked list is a linear or dynamic data structure which is defined as a collection of data elements, called nodes.  Each node contains is divided into two parts. 1. INFO Part 2. LINK or NEXT Part Info Link /Next Node contains address of the next node  Info part:- this part contains information about the element and  Link / Next Part contain the address of the next node in the list. The last node of the linked list contain NULL in the address part.  The following fig. shows linked list with 5 nodes. start 12 23 10 17 21 Start is a pointer variable which contains address of the first node. The Next part (address part) of first node contains address of the second node. The address part of second node contains address of third node and so on. The address part of last node contains NULL, indicates end of linked list. Operation performed on linked list 1. Creation : creates a new node. 2. Traversal : Processing each element in the linked list. 3. Insertion : adding a new element in the linked list 4. Deletion : Removing (deleting) an element from the linked list. 5. Searching : Finding the location of the elements in the given list. 6. Shorting : Arranging the elements in some order (Ascending or Descending) 7. Merging : Combining two lists into single list. Static Memory allocation  The process of allocating memory at compile time is known as static memory allocation. The simplest data structure that should be used for static memory allocation is one dimensional array.   In one dimensional array, address is allocated with fixed size. For example, assumed that each element of array required 2 bytes of memory then N elements required N*2 consecutive bytes in memory. Dynamic memory allocation  The process of allocating memory at run time is known as dynamic memory allocation.  Dynamic data structure like, linked list , provide flexibility in adding, deleting or rearranging data items at run time.  Dynamic memory allocation is implemented with the use of following memory management functions 1. malloc() 2. calloc() 3. free() 4. realloc() Memory management functions are used to allocate memory and release Memory during program execution. The use of above memory management functions are as follows 1. malloc() : Allocate requested memory size in bytes and return a pointer to the first allocated space. Syntax: Pointer_var = (cast_type *) malloc(size in bytes) For example, x = (int *) malloc(200 * sizeof(int)) after successful execution of above statement a memory space equivalent to 200 times the size of integer , that is 400 bytes are allocated. And the address of first byte of memory is assigned to the pointer variable x. 2. calloc() : Allocate multiple blocks of memory and initializes them to zero. 3. free() : free the previously allocated memory space. 4. realloc() : modify the size of previously allocated memory space. Difference between Array & linked list or Advantage of linked list over array 1. Linked list is a dynamic data 1. Array is a static data structure. structure. Therefore, the Therefore, the array cannot grow or advantage of linked list over shrink in size during the execution of array is that the linked list can program grow or shrink in size during the execution of program.  2. Size is not fixed. so, In linked list 2. Size of array is fixed. so, In array wastage of memory is less wastage of memory is more 3. It provides flexibility in adding, 3. It does not provide flexibility in deleting and rearranging a data adding, deleting and rearranging a items at run time data item at run time Limitation of linked list (disadvantage of linked list)  The major limitation of linked list is that access to any item is little cumbersome and time consuming  Whenever we deal with fixed number of items. It would be better to use array than linked list because in linked list each item has additional linked field (address part). It is also noticeable that linked list occupies more storage than array for same number of items. Algorithm to traverse linked list Traversal : “processing (accessing) each element of the list is called traversal”  Start is a pointer variable which contains the address of the first node.  ptr is a pointer variable through which we can traverse linked list. Steps: 1. [Initialize pointer variable ptr] ptr = start 2. [Repeat step 3 and 4] While ptr != NULL 3. [Process info.] Process ptr  info 4. [Move pointer to next node] Ptr = ptr next [end of step 2 loop] 5. Exit Algorithm for creation of linked list Create(start, new, item)  start is a pointer variable which contains the address of the first node.  new is a pointer variable which contains address of newly created node.  item is a variable which contains the value that you store in info field of new node. Steps 1. [initially list empty] start = NULL  2. [Allocate memory to new node] new = create a new node 3. [Assign info (item) to new node] new  info = item 4. [Assign address to new node] new  next =NULL 5. [Assign address of new node to start node] start = new 6. exit Algorithm to insert a new node in the linked list  Algorithm Insert a new node at First position First_insert (start, new, item) This algorithm is used to insert a new node at the first position of the linked list  start is a pointer variable which contains the address of the first node of linked list  new is a pointer variable which contains the address of newly created node.  item is a variable which contains the value that you want to insert in info field of new node. Steps 1. [check for free space] If new = NULL then Display “overflow” & return 2. [Allocate space for a new node] new = create a new node 3. [Assign info (item) to new node] new  info = item 4. [Assign address to new node] new  next = start 5. [Assign address of new to start so it points to new node] start = new 6. exit  Algorithm Insert a new node at Last position Last_insert (start, new, item,ptr)  This algorithm is used to insert a new node at the last position of the linked list  start is a pointer variable which contains the address of the first node of linked list  new is a pointer variable which contains the address of newly created node.  item is a variable which contains the value that you want to insert in info field of new node.  ptr is a pointer variable used for traversal. Steps 1. [check for free space] If new = NULL then Display “overflow” & return 2. [Allocate space for a new node] new = create a new node 3. [Assign info (item) to new node] new  info = item 4. [Assign address to new node] new  next = NULL 5. [initialize ptr] ptr = start 6. [Move pointer to end of list] Repeat thru step 7 While ptr  next != NULL 7. [Move pointer to next node] ptr = ptr  next 8. [link the new node with last node] ptr  next = new 9. exit  Algorithm Insert a new node at Desired position or After any node A Insert_desired (start, new, item, LOC) This algorithm is used to insert a new node at the desired position (After node A whose address is stored in variable LOC) of the linked list  start is a pointer variable which contains the address of the first node of linked list   new is a pointer variable which contains the address of newly created node.  item is a variable which contains the value that you want to insert in info field of new node.  LOC is a pointer variable which contains the address of node A , after which we insert new node. If LOC is NULL then we insert new node at first position. Steps 1. [check for free space] If new = NULL then Display “overflow” & return 2. [Allocate space for a new node] new = create a new node 3. [Assign info (item) to new node] new  info = item 4. [Insert a new node at LOC] If LOC = NULL then new  next = start start = new else new  next = LOC  next LOC  next = new [end of if] 5. exit Algorithm to Delete a node from a linked list When we want to delete a node from the linked list, consider the following points.  If the linked list is empty then deletion is now possible and output should be display “underflow or empty” message.  If the node that you want to delete is not found in the list, the output should be display “node not found” message.  Deletion operation performs three ways (i) Deletion of first node from the linked list (ii) Deletion of last node from the linked list (iii) Deletion of desired node from any place from the linked list  Algorithm to delete first node from the linked list delete_first (start,ptr) This algorithm is used to delete the first node from the linked list   start is a pointer variable which contains the address of the first node of linked list.  ptr is a pointer variable which is used for traversal. Steps 1. [initialization] ptr = start 2. [check for empty list?] If ptr = NULL then Display “list is empty” & return 3. [delete first node] start = start  next 4. [free the space] free (ptr) 5. Exit  Algorithm to delete last node from the linked list delete_last (start,ptr, prev) This algorithm is used to delete the last node from the linked list  start is a pointer variable which contains the address of the first node of linked list.  ptr is a pointer variable which is used for traversal.  prev is a pointer variable used for storing the address of the previous node. Steps 1. [initialization] ptr = prev = start 2. [check for empty list?] If ptr = NULL then Display “list is empty” & return 3. [scan the list upto the end] Repeat while ptr  next != NULL prev = ptr ptr = ptr  next [end of while] 4. [delete last node] prev  next =NULL  5. [free the space] free (ptr) 6. Exit  Algorithm to delete the desired node from the linked list delete_desired (start,ptr, prev,value) This algorithm is used to delete the node from middle position of the linked list  start is a pointer variable which contains the address of the first node of linked list.  ptr is a pointer variable which is used for traversal.  prev is a pointer variable used for storing the address of the previous node.  value is a variable which contains the value of the node that we want to delete. Steps 1. [initialization] ptr = prev = start 2. [check for empty list?] If ptr = NULL then Display “list is empty” & return 3. [delete the desired node] Repeat while ptr  next != NULL If ptr  info = value then prev  next = ptr  next else prev = ptr ptr = ptr  next [end of if] [end of while] 4. [free the space] free (ptr) 5. exit Algorithm to Copy the given linked list copy (start,begin,save,ptr,new) This algorithm is used to copy the given linked list  start is a pointer variable which contains the address of the first node of linked list.  begin is a pointer variable which contain the address of first node of newly created (copied) linked list.   Save and ptr are a pointer variable which is used for traversal.  new is a pointer variable which contain the address of newly created node. Steps 1. [check for empty list?] If start = NULL then Display “list is empty” & return 2. [copy the first node] new = create a new node new  info = start  info begin = new 3. [initialize pointer] save = start 4. [repeat thru step-5] while save  next != NULL ptr = new save = save  next 5. [copy the remaining node] new = create a new node new  info = save  info ptr  next = new 6. [set the link of last node] new  next =NULL 7. [Return] Return (begin) Algorithm to reverse the given linked list or inverted linked list reverse (start,begin,save,ptr,new) This algorithm is used to copy the given linked list in reverse order.  start is a pointer variable which contains the address of the first node of linked list.  begin is a pointer variable which contain the address of first node of newly created (copied) linked list.  Save and ptr are a pointer variable which is used for traversal.  new is a pointer variable which contain the address of newly created node. Steps  1. [check for empty list?] If start = NULL then Display “list is empty” & return 2. [copy the first node] new = create a new node new  info = start  info new  next =NULL 3. [initialize pointer] save = start 4. [repeat thru step-5] while save  next != NULL ptr = new save = save  next 5. [copy the remaining node] new = create a new node new  info = save  info new  next = ptr 6. [set the begin pointer] begin = new 7. [Return] Return (begin) Algorithm to Merge the given two linked list merge (start1,start2,begin,save,ptr,new) This algorithm is used to merge (join) the given two linked list  start1 is a pointer variable which contains the address of the first node of linked list1.  Start2 is a pointer variable which contains the address of the first node of linked list2.  begin is a pointer variable which contain the address of first node of merged linked list.  save and ptr are a pointer variable which is used for traversal.  new is a pointer variable which contain the address of newly created node. Steps 1. [check for empty list?] If start1 = NULL then Go to step7 2. [copy the first node] new = create a new node new  info = start1  info begin = new 3. [initialize pointer] save = start1 4. [repeat thru step-5] while save  next != NULL ptr = new save = save  next 5. [copy the remaining node] new = create a new node new  info = save  info ptr  next = new 6. [initialize pointer to set last node of list] ptr = new 7. [check for empty list] If start1 = NULL and start2 = NULL then Display “both linked list is empty” & exit Else if start2 = NULL then Go to step 12. 8. [copy the first node] new = create a new node new  info = start2  info ptr  next = new 9. [initialize pointer] save = start2 10. [repeat thru step-5] while save  next != NULL ptr = new save = save  next  11. [copy the remaining node] new = create a new node new  info = save  info ptr  next = new 12. [set the link of last node] new  next = NULL 13. [Return] Return (begin) Insert item into a sorted linked list. Algorithm FindA(start, item, LOC,save,ptr) This algorithm is used to find the location LOC of the last node in a sorted list such that info (LOC) < item or sets LOC = NULL.  start is a pointer variable which contains the address of the first node of linked list  item is a variable which contains the value that you want to insert in info field of new node.  save and ptr are a pointer variable which is used for traversal.  LOC is a pointer variable which contains the address of node A , after which we insert new node. If LOC is NULL then we insert new node at first position. Steps 1. [check for empty list] If start = NULL then set LOC = NULL & return 2. [check for start node] If item < start  info the set LOC = NULL & return. 3. [initialize pointer variables] save = start ptr= start  next 4. repeat step 5 and 6 while ptr != NULL 5. If item < ptr  info then set LOC = save & return 6. [Move pointers in forward direction] save = ptr  ptr = ptr  next 7. [set location LOC] Set LOC = save 8. return Main Algorithm for sorted linked list Steps 1. call FindA() algorithm to find the location LOC 2. call insert_desired() algorithm to insert node after LOC 3. return Circular linked list  In singly linked list the last node contains the NULL pointer in the address part. If we replace the NULL pointer of last node with the address of first node in linked list then this type of linked list is called circular linked list. 12 25 10 22 17 Circular linked list Advantage of circular linked list over singly linked list  First advantage is concerned with its accessibility of a node.- In circular linked list every node is accessed from any other node.  Second advantage is concerned with deletion operation- when we delete a node from singly linked list whose address is in variable x then we must have an address of start node and previous node. To find out the above address a searching process must be performed from the first node of linked list. the above requirement doesn’t exist in circular linked list.  Third advantage is concerned with some operations like splitting a linked list. we can do this more efficiently in circular linked list. Disadvantage  In circular linked list it is possible to get into an infinite loop. To resolve above problem , a special node called, header node is placed in the circular linked list. Algorithm for creation of circular linked list Cir_Create(start, new, item)  start is a pointer variable which contains the address of the first node.   new is a pointer variable which contains address of newly created node.  item is a variable which contains the value that you store in info field of new node. Steps 1. [initially list empty] start = NULL 2. [Allocate memory to new node] new = create a new node 3. [Assign info (item) to new node] new  info = item 4. [Assign address of new node to start node] start = new 5. [set the link] new  next =start 6. exit Doubly linked list (two –way list)  In singly linked list, we have been able to traverse the list in only one direction.  While in double linked list we traverse the linked list in forward direction from the beginning to the list to the end or in the backward direction from the end of the list to the beginning means, both directions.  Doubly linked list is a linear collection of data elements, called node, where each node N is divided into three parts. Info, LPTR and RPTR. Left link / LPTR /Prev Right link / RPTR / Next info field  LPTR ot left link or prev. contains the address of previous (preceding ) node  RPTR or right link or Next contains the address of next (successor) node.  Info contains the value of the node.   The LPTR / left link of the left most (first) node and RPTR or right link of the right most node are NULL indicating the end of the linked list from both the direction. Example of doubly linked list having four nodes 16 20 22 30 Doubly linked list creation algorithm This algorithm creates a doubly linked list. doubly_create(L, R, prev, next, value, new)  In doubly linked list the Left most and Right most node’s address is given by pointer variables L and R respectively.  Left and right link of the node are denoted by pointer variable prev and next respectively.  value is a variable which contains the value that we want to insert in node.  new is a pointer variable which contain the address of the newly created node. Steps 1. [ allocate memory] new = create a new node 2. [assign value to info field] new  info =value 3. [set the link] new  prev = NULL and new  next =NULL 4. [assign new to L and R position] L = R = new 5. Exit Doubly linked list traversal algorithm This algorithm traverse (process all elements of the list) a doubly linked list. doubly_traverse(L, R, prev, next , p)  In doubly linked list the Left most and Right most node’s address is given by pointer variables L and R respectively.  Left and right link of the node are denoted by pointer variable prev and next respectively.   p is a pointer variable which is used for traversal. Steps Forward traversal 1. [ initialize pointer] p=L 2. Repeat step 3 and 4 while p != NULL 3. Process p  info 4. [move p in forward direction] p = p  next 5. return backward traversal 1. [ initialize pointer] p=R 2. Repeat step 3 and 4 while p != NULL 3. Process p  info 4. [move p in backward direction] p = p  prev 5. Return Doubly linked list insertion algorithm Doub_insert (L , R, M, X, prev, next)  In given doubly linked list L and R are pointer variables pointing to the left most and right most node in the list respectively.  It is required to insert a node whose address is given by a pointer variable new.  The left and right link of the node are denoted by pointer variable prev and next respectively.  The insertion is to be performed to the left of the specified node with its address is given by variable M.  X is a variable which contains the value that you want to insert. Steps 1. [create a new node] new = create a new node] 2. [assign info] new  info = X 3. [insert into empty list]  If L = R = NULL then new  prev = new  next = NULL L = R = new [end of if] 4. [insert at first position] If L = M then new  prev = NULL new  next = M M  prev = new L = new 5. [insert at last position] If R = M then new  next = NULL new  prev = M M  next = new R = new 6. [insert at middle] new  prev = M  prev new  next = M M  prev  next = new M  prev = new 7. return Doubly linked list deletion algorithm Doub_delet (L , R, old, prev, next)  In given doubly linked list L and R are pointer variables pointing to the left most and right most node in the list respectively.  It is required to delete a node whose address is given by a pointer variable old.  The left and right link of the node are denoted by pointer variable prev and next respectively. Steps 1. [check for empty list] If L = R = NULL then Display “list is empty” & return  2. [deleting single node] If L = R = old then Set L = R = NULL & return 3. [delete the left most node] If L = old then L = L  next L  prev = NULL [end of if] 4. [delete the right most node] If R = old then R = R  prev R  next = NULL [end of if] 5. [delete from middle] old  prev  next = old  next old  next  prev = old  prev 6. return Applications of linked list 1. Implementation of stacks and queues 2. Implementation of graphs : Adjacency list representation of graphs is most popular which is uses linked list to store adjacent vertices. 3. Dynamic memory allocation: We use linked list of free blocks. 4. Maintaining directory of names 5. Performing arithmetic operations on long integers 6. Manipulation of polynomials by storing constants in the node of linked list 7. representing sparse matrices Example of Manipulation of polynomials 10x2 + 26x +10x + 6 by storing constants in the node of linked list 10x2 + 26x, here 10 and 26 are coefficients and 2, 1 is its exponential value. Points to keep in Mind while working with Polynomials:  The sign of each coefficient and exponent is stored within the coefficient and the exponent itself  Additional terms having equal exponent is possible one  The storage allocation for each term in the polynomial must be done in ascending and descending order of their exponent Representation of polynomial using Linked list  Coefficient part  Exponent (power) part  Address part Polynomials 10x2 + 26x +10x + 6 poly 10 2 26 1 10 1 6 0 Address part Coefficient exponent(power)