linked list in dsa python (presentation)

linked list in dsa pythion presentation

1. Linked List Data Structure and Algorithms

2. Topics Singly Linked Lists and Chains, Representing Chains in C, Polynomials, Sparse Matrix, Doubly Linked Lists, Circular & Header Linked Lists

3. Linked Lists A linked list, is a linear collection of data elements called nodes, where the linear order is given by means of pointers. It is the second most used data structure after array

4. Advantages of Linked Lists They are a dynamic in nature which allocates the memory when required. Insertion and deletion operations can be easily implemented. Stacks and queues can be easily executed. Linked List reduces the access time.

5. Disadvantages of Linked Lists The memory is wasted as pointers require extra memory for storage. No element can be accessed randomly; it has to access each node sequentially. Reverse Traversing is difficult in linked list.

6. Linked List Memory Representation In memory the linked list is stored in scattered cells (locations).The memory for each node is allocated dynamically means as and when required. So the Linked List can increase as per the user wish and the size is not fixed, it can vary. Suppose first node of linked list is allocated with an address 1008. Its graphical representation looks like the figure shown below Suppose next node is allocated at an address 506, so the list becomes

7. Linked List Memory Representation Suppose next node is allocated with an address with an address 10 , the list become, Address Comments links 1008 Root & single element 506 506 1 st element insertion 10 10 2 nd element insertion NULL

8. Linked List Memory Representation contd.. Let LIST be the linked list. First of all, LIST requires two linear arrays–call them as INFO and LINK. INFO[K] represents the information part and LINK[K] represents the next pointer field of the node of LIST for Kth element. LIST also requires 2variables such as START which contains the location of the beginning of the list and the next pointer sentinel denoted by NULL which indicates the end of the list. Since the subscript of the arrays INFO and LINK will usually be positive, so NULL should be treated as 0 unless otherwise stated.

9. Types of Linked Lists Singly Linked Lists Doubly Linked Lists Circular Linked List

10. Double Linked List Important Concepts: Link−Each Link of a linked list store the data Next−Each Link of a linked list contain a link to next link Prev −Each Link of a linked list contain a link to previous link Linked List− A Linked List contains the connection link to the first Link called First and to the last link called Last.

11. Circular Linked List Circular Linked List is a variation of Linked list in which first element points to last element and last element points to first element. Both Singly Linked List and Doubly Linked List can be made into as circular linked list. Singly Linked List as Circular In singly linked list, the next pointer of the last node points to the first node.

12. Circular Linked List Doubly Linked List as Circular In doubly linked list, the next pointer of the last node points to the first node and the previous pointer of the first node points to the last node making the circular in both directions.

13. Linked List Basic Operation Insertion−add an element at the beginning of the list. Deletion−delete an element at the beginning of the list. Insert Last-add an element in the end of the list. Delete Last−delete an element from the end of the list. Insert After−add an element after an item of the list. Traverse−Traverse and display the complete list in forward manner. Search−search an element using given key or data item. Delete−delete an element using given key or data item. Traverse Backward−displaying complete list in backward manner. Applicable for double and circular linked list

14. Traverse Algorithm 1.Traverse Algorithm Consider LIST be a linked list in memory stored in linear arrays INFO and LINK with START pointing to the first element, NULL indicating the end of the list and PTR is the pointer that points to the node currently being processed. Below is the algorithm to traverse through all nodes exactly once and write the node data element and can be represented using procedure PRINT(INFO,LINK,START) 1.Set PTR :=START 2.Repeat steps 3 and 4 while PTR<>NULL 3. PRINT INFO[PTR] 4. PTR:=LINK[PTR] [PTR pointing to next node] 5.Exit 2.Find count of no. of element in a linked list Consider LIST be a linked list in memory stored in linear arrays INFO and LINK with START pointing to the first element, NULL indicating the end of the list and PTR is the pointer that points to the node currently being processed. Below is the algorithm to find the number of NUM elements in the linked list and can be represented using procedure COUNT(INFO,LINK,START,NUM) 1.Set PTR: = START 2.SetCNT=0 3.Repeat steps 4 and 5 while PTR<>NULL 4. IF(INFO[PTR]=NUM) THEN Set CNT=CNT+1 5. PTR=LINK[PTR] [PTR pointing to next node] 6.PRINT CNT 7.Exit

15. Searching Algorithm Unsorted List Consider LIST be a linked list in memory stored in linear arrays INFO and LINK with START pointing to the first element, NULL indicating the end of the list and PTR is the pointer that points to the node currently being processed and ITEM is the information given. Below is the algorithm to find the location LOC of the node where ITEM first appears in the LIST and can be represented by SEARCH(INFO,LINK,START,ITEM) 1.Set PTR = START 2.Set LOC=NULL 3.Repeat steps 4 and 5 while PTR <> NULL 4.IF (ITEM= INFO[PTR]) THEN LOC=PTR EXIT 5.ELSE PTR=LINK[PTR] 6.Exit Sorted List Consider LIST be a linked list in memory stored in linear arrays INFO and LINK with START pointing to the first element, NULL indicating the end of the list and PTR is the pointer that points to the node currently being processed and ITEM is the information given. Below is the algorithm to find the location LOC of the node where ITEM first appears in the LIST and can be represented by SEARCH_SL(INFO,LINK,START,ITEM) 1.Set PTR = START 2.Set LOC = NULL 3.Repeat 4 while PTR<>NULL 4.IF(ITEM<INFO[PTR]) then Set PTR=LINK[PTR] else IF(ITEM=INFO[PTR]) then LOC=PTR EXIT else EXIT

16. Garbage Collection The maintenance of the linked list in memory assumes the possibility of inserting new nodes into the list requires some mechanism which provides unused memory space for the new nodes. Analogously some mechanism is required where by the memory space of deleted nodes becomes available for further use. Together with the linked list in memory, a special list is maintained which consists of unused memory cells. The list, which has its own pointer, is called the list of available space or the free storage list or free pool. Suppose the linked list is implemented by parallel arrays and then the unused memory cells in the array will be also linked together to form linked list using AVAIL as its list pointer variable.

17. Garbage Collection contd.. Suppose some memory space becomes reusable because a node is deleted from a list or an entire list is deleted from the program. Clearly we want the space to be available for future use. One way to bring this is to immediately reinsert the space into the free-storage list. This is what will do when we implement the linked list by means of linear arrays. However, the method may be too time-consuming for the operating system of a computer and which may choose an alternative method as follows.

18. Garbage Collection contd.. The operating system of a computer may periodically collect all the deleted space on to the free storage list and the techniques does this collection is called garbage collection. It is invisible to the programmer. It takes 2 steps 1st –The computer runs through all the list, tagging those cells which are currently in use 2nd –computer run through the memory, collecting all untagged space onto the free-storage list The garbage collection take place when- There is only some minimum amount of space No space at all left in the free-storage list CPU is idle and has time to do the collection

19. The situation is called Overflow when the data are inserted into a data structure but there is no available space i.e.free storage list is empty. This will happen when AVAIL is NULL and insertion operation is initiated. The situation is called Underflow when deletion operation is initiated when the data structure is empty. This will happen when START is NULL and deletion operation is initiated. Overflow and Underflow

20. Insertion Algorithm Various situations are possible for inserting a node in a linked list. They are as following Inserts node at the beginning of the list Inserts node after the node with a given location Inserts a node into a sorted list All our algorithms assume that the linked list is in memory in the form LIST(INFO,LINK,START,AVAIL) and that the variable ITEM contains new information to be added to the list. All algorithms will include following steps: If AVAIL=NULL, then print OVERFLOW NEW:=AVAIL, AVAIL=LINK[AVAIL] INFO[NEW]:=ITEM

21. Inserting at the beginning of the list INSFIRST(INFO, LINK,START,AVAIL,ITEM) 1.If AVAIL=NULL, then Write: OVERFLOW and Exit 2.Set NEW:=AVAIL and AVAIL:=LINK[AVAIL] 3.Set INFO[NEW]:=ITEM 4.LINK[NEW]:=START 5.START:=NEW 6.Exit

22. Inserting After a Given Node INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM) If AVAIL=NULL then WRITE:OVERFLOW and Exit Set NEW:=AVAIL and AVAIL:=LINK[AVAIL] Set INFO[NEW]:=ITEM If LOC=NULL then Set LINK[NEW]:=START and START:=NEW Else: Set LINK[NEW]:=LINK[LOC] and LINK[LOC]:=NEW 5.Exit

23. Inserting into a sorted linked list 1.IF(START=NULL) THEN Set LOC=NULL and Return 2.IF(ITEM<INFO[START]) THEN LOC=NULL and Return 3.Set SAVE=START and PTR=LINK[START] 4.REPEAT 5 and 6 WHILE PTR<>NULL 5. IF ITEM<INFO[PTR] THEN Set LOC=SAVE and Return 6. Set SAVE = PTR and PTR=LINK[PTR] 7.Set LOC=SAVE 8.Call INSLOC(INFO,LINK,START,AVAIL,LOC,ITEM) 9.Return

24. Deletion Algorithm The three pointers fields are changed as follows: 1.The next pointer field of first node now points to second node, where node N previously pointed. 2.The next pointer field of N now points to the original first node in the free poll, where AVAIL previously pointed. 3.AVAIL now points to the deleted node N.

25. Deletion from a node following a given node

26. Deletion from a node following a given node DEL(INFO, LINK, START, AVAIL, LOC, LOCP) This algorithm deletes the node N with location LOC.LOCP is the location of the node which precedes N or, when N is the first node, LOCP=NULL 1.If LOCP=NULL then, Set START:=LINK[START] Else: Set LINK[LOCP]:=LINK[LOC] 2.Set LINK[LOC]:=AVAIL and AVAIL:=LOC 3.Exit

27. Header Linked List A header linked list is a list which always contains a special node, called the header node, at the beginning of the list. The following are two kinds of widely used header lists: 1.A grounded header list is a header list where the last node contains the null pointer 2.A circular header list is a header list where the last node points back to the header node.

28. Circular Header List Algorithm Consider LIST to be a circular header linked list in memory. START pointing to the first element, NULL indicating the end of the list and PTR is the pointer that points to the node currently being processed. Below is the algorithm to traverse through all nodes exactly once and write the node data element 1.SetPTR=LINK[START] 2.Repeat steps 3 and 4 while PTR<>START 3.PRINT INFO[PTR] 4.PTR=LINK[PTR] 5.Exit Consider LIST to be a circular header linked list in memory with START pointing to the first element, specific ITEM info is given, NULL indicating the end of the list and PTR is the pointer that points to the node currently being processed. Below is the algorithm to find the location LOC in LIST which contains the ITEM. It can be represented using procedure SEARCHCHL(INFO,LINK,START,ITEM) 1.SetLOC=NULL 2.Repeat step3 while PTR<>START AND INFO[PTR]<>ITEM 3.SetPTR=LINK[PTR] 4.IF(INFO[PTR]=ITEM)THEN Set LOC=PTR ELSE Set LOC=NULL 5.Exit

29. Circular Header List Algorithm cont… Delete the first node N which contains ITEM Consider LIST to be a circular header linked list in memory with START pointing to the first element, specific ITEM info is given, NULL indicating the end of the list and PTR is the pointer that points to the node currently being processed. Below is the algorithm to delete the first node N which contains ITEM. It can be represented using procedure DELLOCHL(INFO,LINK,START,AVAIL,ITEM) 1.Set SAVE = START and PTR=LINK[START] 2.Repeat steps 3 while PTR<>START AND INFO[PTR]<>ITEM 3.Set SAVE=PTR and PTR=LINK[PTR] 4.IF(INFO[PTR]=ITEM) THEN Set LOC=PTR and LOCP=SAVE ELSE Set LOC=NULL and LOCP=SAVE 5.IF(LOC=NULL) THEN PRINT(ITEM not exist) and EXIT 6.Set LINK[LOCP]=LINK[LOC] 7.Set LINK[LOC]=AVAIL and AVAIL=LOC 8.Exit

30. Double Linked List

31. Double Linked List –Deletion Algorithm Suppose we are given the location LOC of a node N in LIST and want to delete N from the list. We assume that LIST is a two-way circular header list. Note that PREV[LOC] and NEXT[LOC] are the locations respectively of the nodes which precede and follow node N. So N is deleted from the list by changing the following pair of pointers: NEXT[PREV[LOC]]=NEXT[LOC] and PREV[NEXT[LOC]]=PREV[LOC] The deleted node N is then returned to the AVAIL list by the assignments: NEXT[LOC]=AVAIL and AVAIL=LOC 1.SetNEXT[PREV[LOC]]=NEXT[LOC] and PREV[NEXT[LOC]]=PREV[LOC] 2.SetNEXT[LOC]=AVAIL and AVAIL=LOC 3.Exit

32. Double Linked List –Insertion Algorithm Suppose we are given the locations LOCA and LOCB of adjacent nodes A and B in LIST and wanted to insert a given ITEM of information between nodes A and B. As with a single linklist , we first remove the first node N from the AVAIL list, using the variable NEW to keep track of its location and then copy the data ITEM into the node N i.e.we set: NEW=AVAIL, AVAIL=NEXT[AVAIL], INFO[NEW]=ITEM As shown in the picture, the node N with contents ITEM is inserted into the list by changing the following four pointers: NEXT[LOC]=NEW, NEXT[NEW]=LOCB, PREV[LOCB]=NEW and PREV[NEW]=LOCA 1.IF(AVAIL=NULL) THEN PRINT(OVERFLOW) and EXIT 2.NEW=AVAIL, AVAIL=NEXT[AVAIL], INFO[NEW]= ITEM 3.NEXT[LOCA]= NEW, NEXT[NEW]=LOCB, PREV[LOCB]=NEW and PREV[NEW]=LOCA 4.Exit

33. Sparse Matrix A sparse matrix is a two-dimensional array in which most of the elements are zero or null. It is a wastage of memory and processing time if we store null values or 0 of the matrix in an array. To avoid such circumstances different techniques are used such as linked list. N-square sparse matrices is called triangular matrix. A square matrix is called lower triangular if all the entries above the main diagonal are zero. Similarly, a square matrix is called upper triangular if all the entries below the main diagonal are zero.

34. Sparse Matrix cont… Sparsematrixcanberepresentedusingalistofsuchnodes,onepernon–zeroelementofthematrix.Forexample,considerthesparsematrix Thelinkedlistcanberepresentedusinglinkedlistasshownbelow