1. Introduction to Linked Lists

1. What is a Linked List?

1. Linked list is a data structure used for storing collection of data.
2. Properties of linked list
1. Successive elements are connected by pointers.
2. Last element points to null.
3. It does not waste space but takes extra memory.
4. Can grow or shrink size during execution of a program.
3. Like arrays, Linked List is a linear data structure.
4. Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.
   
5. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration.
   

2. History of Linked List?

1. Linked lists were developed in 1955–1956 by Allen Newell, Cliff Shaw and Herbert A. Simon at RAND Corporation as the primary data structure for their Information Processing Language.

3. Why Linked List?

1. Arrays can be used to store linear data of similar types, but arrays have following limitations.
1. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
   
2. Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.
   
3. Deleting an element from an array is also an expensive, because room has to be deleted and all adjacent elements to be shifted to left.
4. Array size is fixed, if we want resize the array we need to create a new array with new size and copy the all the elements of old array and destroy the old array.
2. To overcome the above limitations, we need to use linked lists.

4. Advantages of Linked List?

1. Linked list size is not fixed like arrays, it is dynamic size.
2. Ease of insertion and deletion.
   

5. Disadvantages of Linked List?

1. For accessing an element or random access of an element is not allowed.
2. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
3. Extra memory space for a pointer is required with each element of the list.

6. Types of Linked List?

1. Linked list has following types.
1. Single Linked List
2. Doubly Linked List
3. Circular Linked List
4. Unrolled Linked List