LinkedList

Question 1

What is a linked list?

Answer 1

Linked List is a linear data type whose each element is a separate object.
Each element comprises of data, and reference to the next node.
A linked list is of variable size compared to Array being fixed size

Question 2

Components of LL?

Answer 2

head: Reference to the first node of the list (to know where to start the LL)
node: contains data and reference to the next, or previous node
tail: reference to the last node (to improve the time complexity to add new node)

Question 3

Types of LL?

Answer 3

• Single LL: LL with nodes that contain data and reference to the next node, it does not have a ref to prev node. Also, the last node’s ref is null
• Circular single LL: LL that contains data and reference to the next node, it does not have a ref to prev node. Also, the last node’s ref is pointing to the first node (not the root)
  e. g. multiplayer game where the turn of players rotate
• double LL: LL that contains data and reference to the next node, and prev node. Also, the last node’s ref is null
  e. g. music player with prev, next buttons
• circular double LL: LL that contains data and reference to the next node, and prev node. Also, the last node’s ref is pointing to the first node (not the root)
  e. g. Alt + tab button

Question 4

How is LL stored in memory?

Answer 4

LL is stored as each node in a random memory cell location which is not continuous like an array.

Thus you cannot access the nth element directly from the first element’s address