Introduction to Linked list

Abhishek Kumar • Category: Data Structures • Tags: datastructures linkedlist

---

In this introduction part of the linked list, we will learn about the basics of a Linked List, like its types and operations and we will also go through the advantages and disadvantages of a Linked List over an Array with the comparison of time complexity.

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 n^th 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)

---