What is linked list and types of linked list?

A linked list is a set of elements, usually structures, where each element contains a pointer or index to the "next" element, along with the data represented by the element.

Often, the elements are allocated from the heap. Sometimes, a fixed number of elements is contained in an array. In the first case, pointers are used. In the second case, indices are used.

Types of linked lists are ... In an array implementation, read pointer as index.
  • Singly linked - there is a head pointer, and one next pointer per element. The last element's pointer is null. This type of list can be traversed in only one direction.
  • Doubly linked - there is a head pointer, and each element contains two pointers, one to the previous element and one to the next element. This type of list can be traversed in two directions, making insertion and deletion a bit easier, at the cost of extra memory.
  • Circularly linked - the same as Singly or Doubly linked, except that the last element's pointer points back to the first element's pointer. These types of lists are often used as queues.