Linked List

Question 1

What are the operations of a linked list and complexity analysis of each one?

Answer 1

Push Front O(1)
Top Front O(1)
Pop Front O(1)
Push Back O(N) when there is no tail pointer
Top Back O(N) when there is no tail pointer
Pop Back O(N) when there is no tail pointer
Find O(N)
Erase O(N)
Empty O(1)
Add Before O(N)
Add After O(1) because the method itself takes the node we want to add after it

Question 2

what is the purpose of abstract data type?

Answer 2

it’s to specify the behavior not the implementation

Question 3

what are sentinel nodes?

Answer 3

they are nodes that don’t hold any data and will always be there in the list even when it’s empty they are used as guidelines as the head and tail point to them

Question 4

difference between list and array in read and write

Answer 4

arrays are faster to read while lists are faster to write

Question 5

what makes u decide between a list and an array

Answer 5

the algorithm as using merge sort on an array means that u will copy the elements from the two arrays and then sort the large array which will take alot of time and memory but with a list u can just change the reference and then u have one big list to sort

Question 6

what is bad about a list?

Answer 6

the indirection and the pointers that go from somewhere to another not like arrays that are contiguous and that indirection the modern computers don’t like

Question 7

what is a doubly linked list and how can it improve out operations?

Answer 7

a list is a doubly list when it has a next pointer and a prev pointer and that makes addBefore O(1) and push

Question 8

what is the difference in access between list and array

Answer 8

array has direct access (Random Access) while list has sequential access

Question 9

what is a circular linked list?

Answer 9

it’s when the head pointer points to the last node and the tail pointer points to the last node