Introduction to Linked list

Table of contents

• Types of Linked List
• Operations on Linked List
• Advantages of Linked List over Array
• Disadvantages of Linked List over Array
• Comparision of Linked Lists with Arrays

A Linked List is a data structure used for storing collections of data. Basically, it is a collection of nodes in a particular sequence.

1. Successive elements are connected by pointers.
2. Last element points to None.
3. Size can be increased or reduced during execution of program.
4. Does not waste memroy but takes an extra space to store address of next node.

Types of Linked List

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List

Operations on Linked List

1. Insert: Insetion of an element into the linked list
2. Delete: Deletion of an element into the linked list
3. Delete List: Deletion of all element from the Linked List
4. Count: Returns length of the Linked List 5. Find: Find nth node in the Linked List

Advantages of Linked List over Array

1. Size of Linked List can be easily incresed and reduced without wastage of memory i.e., Linked List is dynamic in size. It happens because in case of array memory is allocated during compile time but in case of Linked List memory is allocated during runtime.
2. Operations like insertion and deletetion in consume extra time in comparision with Linked List.
3. Memory utilization is better in case of Linked List in comparision with Array.

Disadvantages of Linked List over Array

1. Arrays are easier to implement and simple to use.
2. Faster access to elements in constant time because of indexing.
3. Arrays are defined as contiguous block of memory thats why all the elements are situated as neighbours.

Comparision of Linked Lists with Arrays

Parameter	Linked List	Array
Indexing	O(n)	O(1)
Insertion/deletion at begining	O(1)	O(n)
Insertion/deletion at ending	O(n)	O(1)