1649 data structures algorithms greenwich asm2

Table of Contents

LIST OF FIGURE:..................................................................................................................................................4

I. INTRODUCTION:...............................................................................................................................................5

II. IMPLEMENT COMPLEX DATA STRUCTURES AND ALGORITHMS:.................................................5

1. HIGHLIGHT SOME DIFFERENCES BETWEEN SINGLY AND DOUBLY LINKED-LIST:..............5

2. DESCRIBE SINGLY AND DOUBLY LINKED-LIST’S OPERATIONS:.................................................5

3. IMPLEMENT SINGLY AND DOUBLY LINKED-LIST:...........................................................................6

3.1. Singly linked-list:.......................................................................................................................................6

3.2. Doubly linked-list:.......................................................................................................................................11

4. INSERT AN ELEMENT IN THE MIDDLE OF A LINKED-LIST:.........................................................16

III. IMPLEMENT ERROR HANDLING AND REPORT TEST RESULTS:..................................................17

1. TESTING PLAN:...............................................................................................................................................17

2. EVALUATION:.............................................................................................................................................20

IV: DISCUSS HOW ASYMPTOTIC ANALYSIS CAN BE USED TO ASSESS THE EFFECTIVENESS OF

AN ALGORITHM:................................................................................................................................................20

1. Θ NOTATION:..............................................................................................................................................20

2. BIG O NOTATION:......................................................................................................................................21

3. Ω NOTATION:..............................................................................................................................................21

V. DETERMINE TWO WAYS IN WHICH THE EFFICIENCY OF AN ALGORITHM CAN BE

MEASURED, ILLUSTRATING YOUR ANSWER WITH AN EXAMPLE:...................................................22

1. SPACE COMPLEXITY:...............................................................................................................................22

2. TIME COMPLEXITY:.................................................................................................................................23

VI. CONCLUSION:...............................................................................................................................................24

REFERENCES.......................................................................................................................................................25

LIST OF FIGURE:

Figure 1. Class Node.....................................................................................................................................6

Figure 2. Add element at the end..................................................................................................................7

Figure 3. The process of adding the element at the end................................................................................7

Figure 4. Add element at the beginning........................................................................................................8

Figure 5. The process of adding the element at the beginning......................................................................8

Figure 6. Delete the element at the beginning...............................................................................................9

Figure 7. The process of deleting the element at the beginning....................................................................9

Figure 8. Delete the element at the end.......................................................................................................10

Figure 9. The process of removing the element at the end.........................................................................10

Figure 10. toString()....................................................................................................................................11

Figure 11. class Node (Doubly)..................................................................................................................11

Figure 12. Add elements to the beginning of Doubly.................................................................................12

Figure 13. The process of adding elements to the beginning in Doubly.....................................................12

Figure 14. Add the element at the end of Doubly.......................................................................................13

Figure 15. The process of adding the element at the end in Doubly...........................................................13

Figure 16. Delete the first element in Doubly.............................................................................................14

Figure 17. The process of deleting the first element in Doubly..................................................................14

Figure 18. Delete the last element in Doubly..............................................................................................15

Figure 19. The process of deleting the last element in Doubly...................................................................15

Figure 20. toString()....................................................................................................................................16

Figure 21. Add the element to the center....................................................................................................16

Figure 22. The process of add the element to the center.............................................................................17

Figure 23. Θ NOTATION (geeksforgeeks)................................................................................................21

Figure 24. BIG O NOTATION (geeksforgeeks)........................................................................................21

Figure 25. Ω NOTATION (tutorialspoint)..................................................................................................22

Figure 26. Space complexity example........................................................................................................23

Figure 27. Time complexity (tutorialspoint, 2021).....................................................................................24

Figure 28. Time complexity example.........................................................................................................24