linkedLists

Question 1

What’s the time complexity for traversing arrays?

Answer 1

Time: 0(1), because arrays occupy contiguous (adjacent) blocks of memory

Question 2

What’s the time complexity for traversing linked lists?

Answer 2

Time: 0(n), because linked list nodes can exist anywhere in memory

Question 3

What’s the time and space complexity for linked lists?

Answer 3

Time: 0(n), because linked list nodes can exist anywhere in memory

Space: 0(n), because it requires n nodes to store n values. Linked lists hold two main pieces of information (the value and pointer) per node. This means that the amount of data stored increases linearly with the number of nodes in the list.

Question 4

Whats the time and space complexity for doubly linked lists?

Answer 4

Time: 0(1), because of the two addresses in a node (next and previous), this makes it efficient.

space: 0(n), because it holds two addresses in a node, one is of the next node and the other one is of the previous node, this takes more memory

Question 5

What’s the time complexity for addToHead()?

Answer 5

Time: 0(1), addToHead() is O(1) since each of its steps operate in constant time, regardless of the size of the list

Because linked lists have a time complexity of 0(n) and addToHead() has a time complexity of 0(1), to add to head on a linked list would take 0(n) time.

Question 6

What’s the time complexity for print() or search()?

Answer 6

Time: 0(n), because it requires visiting n nodes

Question 7

What’s the time complexity for addToTail()?

Answer 7

Time: 0(n), because it requires visiting n nodes

Question 8

What’s the time complexity for removeFromHead() and removeFromTail() for linked lists?

Answer 8

Time: 0(n)