Inserting an item into an unsorted list and inserting into a sorted list are the
ID: 3810224 • Letter: I
Question
Inserting an item into an unsorted list and inserting into a sorted list are the same time complexity. (2) In array-based implementation, deleting from a sorted list requires that the elements below the one being deleted be moved up one slot. 3) You can perform a binary search on both a linked-based implementation and an array-based implementation. (4) The next item in a linked list always can be found by accessing the next physical location in memory. (5) If currPtr++ points to a node in a dynamic linked list, the operation currPtr++ advances to the next node in the list. type parameters. What is the difference between a shallow copy and a deep copy? (2) When a copy constructor (a special member function) of a class is implicitly called?Explanation / Answer
1)
i) False- Reason: For a sorted list, if we consider the worst case, the insertion takes O(n) as if we insert the largest element, we have to traverse the complete list. On the other hand, insertion in a unsorted list is O(1) as the items order is not maintained.
ii) False- Reason: In array based implementation, deleting an element from the array implicitly shits the elements present to the right of deleted element to shift one index to the Left which is an internal implementation of index based removal in array.
iii) False- Reason: In binary search, we reduction in input size should take constant time. Its possible in array as they are indexes based contrary to linked list
iv) False- Reason: In linked list, the address of the next item is stored in the current node itself
v) False- Reason: If curptr points to current node in list, the address of next node is given by cruptr->Next(where Next is a pointer storing the address of subsequent node in list.)
vi) True
2)
i) Shallow copy versus Deep copy:
Shallow copy is a copy of the collection and not its elements while Deep copy copies all the object fields.Deep copy take place when an object is copied with the objects it points to.
Shallow copy points to identical location in memory where the source points to while deep copy points to a different location in memory but with same contents.
ii) The copy constructor of a class is implicitly called when an object is created from another object of same type. Also, it may be called when an object present in a class is passed by value to a function.
3)
i) Retrive item in an unsorted list : O(n) : Reason- we have to travserse the entire list
ii) Retrive item in sorted list using binary search : O(logn) : Using binary search algo to find mid and splitting the list.
iii) Insert item in an unsorted list : O(1) : Explained in part 1
iv) Insert item in an sorted list : O(n) : Explained in part 1