Arrays and Linked Lists

Question 1

What is array?

Answer 1

Contiguous area of memory consisting of equal-size elements indexed by contiguous integers.

Question 2

Time for Array Operation

Answer 2

access to any element - o(1) (constant time)
add / remove at the end - o(1) (constant time)
add / remove at the front / middle - o(n) (linear time)

Question 3

Time for Singly-Linked List Operation

Answer 3

Find - o(n)
Empty - o(1)
AddBefore(node,key) - o(n)
AddAfter(node,key) - o(1)
no tail
PushFront - o(1)
TopFront - o(1)
PopFront - o(1)
PushBack - o(n)
TopBack - o(n)
PopBack - o(n)
with tail
PushFront - o(1)
TopFront - o(1)
PopFront - o(1)
PushBack - o(1)
TopBack - o(1)
PopBack - o(n)

Question 4

Time for doubly linked list Operation

Answer 4

Everything o(1) except find operation ( o(n) )