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.

Maximum area histogram

Table of contents

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

Linked List example 1

  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

ParameterLinked ListArray
Insertion/deletion at beginingO(1)O(n)
Insertion/deletion at endingO(n)O(1)

Recommended Posts