Linked List

Linked List : Introduction

What is Linked List?

Linked List is a Linear Data Structure, Just Like the Array but in Array, Elements are stored in the Contiguous memory Location But in Linked List they are not stored in this manner.

In Linked List the Elements are linked using the Pointers.

Why Linked List is needed?

The array can be used to store the data then what’s the need of the Linked List.

Limitation of Array:

  • The size of Array is Fixed , we can’t enter the elements more than its Size But in Linked List there is no size limit , unless the heap memory gets full.
  • Insertion/Deletion Suppose We have a Array named A as

    A[6] : [3,4,6,7] → All elements are in the Sorted Order

    and if we want to enter 1 at its right place we have move many elements

  • If we want to insert the Element we have moved all these Elements.

  • Now if the Array size is so big then it takes a much higher amount of time in order to insert or Delete an Element. So Insertion/Deletion are Expensive Process . Whereas in the case of the Linked List we just have to play with the linking of the nodes for Insertion/Deletion.

So the Advantages of Linked List are:

  1. Dynamic Size
  2. Ease of Insertion/Deletion

Drawbacks:

  1. In Linked List, Random Access is not Allowed, In order to search for an Element we have to start searching from the First Node(Head Node).
  2. Extra memory For pointer is Required with each element

How Linked List is represented?

Representation of Linked List:

  • Linked List can be defined as a collection of objects called nodes that are randomly stored in the memory.
  • A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory.
  • The last node of the list contains Pointer to the null.

C++ Code

// A linked list node
 struct Node {
 int data;
 struct Node* next;
 };

Types of Linked List

There are 3 different types of Linked Lists:

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

Singly Linked List:

So this is the simple depiction of the singly linked list. In this, all the nodes are connected in the Forward Manner.

Doubly Linked List:

As you can see, the doubly linked list is very similar to the singly linked list except for the difference of the previous pointer. In a doubly-linked list, a node is made up of the following components:

  • Data
  • Next (Points to the next node)
  • Prev (Points to the previous node)

Circular Linked List:

You can see from the illustration above that the circular linked list contains the same kind of nodes as a singly linked list. As the name circular suggests, the tail node points to the head of the linked list instead of pointing to null which makes the linked list circular.

Special thanks to Jayant for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article