Get value in Linked List

FAQ

1. Which one is better, Array-List or Linked-List and Why?
Answer:Linked List , Advantages and reasons are below:-
        a) In array elements are stored in consecutive memory locations. ( i.e if address of 1st element is 100 then address it next element is 101 provided that one element of array consumes only one byte in memory ) But In linked list , Nodes of linked list are scattered in memory it means addresses of elements are not consecutive but still they are connected to each other through link which contains address of it's next node or element.
        b) Insertion and deletion inside array is not efficient since it requires shifting of elements.For example if we want to insert an element at the 0th position then we have to shift all the elements of array to the right and if we have to delete element present at 0th position then we have to shift all the elements to the left..( It means insertion and deletion is not that easy in array.. it is more time consuming ) But in linked list we can easily do that by just changing links .
        c) We can keep on inserting elements till memory is available and if we don't need the data we can easily return the memory occupied by it to the free storage so that it can be used by other programs…!
        
2. Why is binary search not possible using linked list?
Answer: It is possible but there is no point using it, because at the end it would take same time as normal linear search. And with linked list the second prerequisite is not satisfied as any random element in linked list cannot be accessed in constant time, but it must be traversed completely.
        
3. Why we need to travel the whole linkedlist to get the data from it ? Why we can't get it as in array we used to?
Answer: This is because in array we have a base address and we  can just access by writting arrray[index] but here this is not possible because nodes of linked list are scattered in memory but connected through a link.

4. Why time complexity and space complexity to get value from first and last is just O(1) ?
Answer: This is because we have the keyword head and tail that is defined in anode class which stores the address and data of first and last node so we don't need to travel for that.

Hint

1. Keyword head.data is used to access data from first.
2. Before accessing any data fisrt check the size of linked list, if 0 then return -1.
3. Keyword tail.data is used to access data from first.
4. If invalid index is passed, should return -1 and print "Invalid arguments".
5. Cant we make a temporary node to travel in the linked list and stop before the index provided and then return the data of that node?
 

MCQ

1. What is the time ans space complexity to get value from first from the given linked list ?
	a) O(n) & O(n)
	b) O(n) & O(1)
	c) O(1) & O(n)
	d) O(1) & O(1)

Answer: d) O(1) & O(1)

2. What is the time ans space complexity to get value from last from the given linked list ?
	a) O(n) & O(n)
	b) O(n) & O(1)
	c) O(1) & O(n)
	d) O(1) & O(1)
  
Answer: c) O(1) & O(1)

3. What is the time ans space complexity to get value at the index passed from the given linked list ?
	a) O(n) & O(n)
	b) O(n) & O(1)
	c) O(1) & O(n)
	d) O(1) & O(1)
  
Answer: b) O(n) & O(1)

4. What is the space complexity for deleting a linked list?
  a) O(1)
  b) O(n)
  c) Either O(1) or O(n)
  d) O(logn)
  
Answer: a) O(1)