Introduction to Linked list
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.
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.
- Successive elements are connected by pointers.
- Last element points to None.
- Size can be increased or reduced during execution of program.
- Does not waste memroy but takes an extra space to store address of next node.
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- Insert: Insetion of an element into the linked list
- Delete: Deletion of an element into the linked list
- Delete List: Deletion of all element from the Linked List
- Count: Returns length of the Linked List 5. Find: Find nth node in the Linked List
- 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.
- Operations like insertion and deletetion in consume extra time in comparision with Linked List.
- Memory utilization is better in case of Linked List in comparision with Array.
- Arrays are easier to implement and simple to use.
- Faster access to elements in constant time because of indexing.
- Arrays are defined as contiguous block of memory thats why all the elements are situated as neighbours.
|Insertion/deletion at begining||O(1)||O(n)|
|Insertion/deletion at ending||O(n)||O(1)|