Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Easy

A Brief Introduction To Linked Lists

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

A Linked Lists is a linear Data Structure that consists of a group of nodes. Unlike an array, it has elements that are stored in random memory locations.

Each node contains two fields:

  • data stored at that particular address.
  • The pointer contains the address of the next node.

 

The last node of the Linked list contains a pointer to null to represent the termination of the linked list. Generally, we call the first node as the head node and the last node as the Tail node in Linked List.

Introdcution to Linked List

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm.

Why Linked List Over Array?

The array contains the following limitations:

  • The size of an array is fixed. We must know the size of the array at the time of its creation, hence it is impossible to change its size at runtime.
  • Inserting a new element in an array of elements is expensive because we need to shift elements to create room for new elements to insert.
  • Deleting an element in an array is also expensive as it also takes the shifting of elements in the array.
    Also read - merge sort in linked list
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Advantages of Linked List

The advantages of Linked List are:-

  • Insertion and deletion operations can be implemented very easily and these are not costly as they do not require shifting of elements.
  • They are dynamic in nature. Hence, we can change their size whenever required.
  • Stacks and queues can be implemented very easily using Linked Lists.

Disadvantages of Linked List

The disadvantages of Linked List are:-

  • Random access of an element is not possible in Linked Lists, we need to traverse Linked List from starting to search an element into it.
  • It is relatively slow to process in comparison to an Array.
  • Since node of a Linked List contains both data and pointer to the next node, hence extra memory is required to store the pointer of each node.

Types of Linked List

Introduction to Linked List

There are three types of Linked Lists:

  • Singly Linked List
  • Circular Linked List
  • Doubly Linked List

Singly Linked List

A Singly Linked List contains a node that has both the data part and pointer to the next node. The last node of the Singly Linked List has a pointer to null to represent the end of the Linked List. Traversal to previous nodes is not possible in singly Linked List i.e We can not traverse in a backward direction.

Singly Linked List

Circular Linked List

Circular Linked List is similar to singly Linked List but the last node of singly Linked List has a pointer to node which points to the first node (head node) of Linked List.

Circular Linked List

Doubly Linked List

Doubly Linked List contains a node that has three entries: (1) data part, (2) pointer to the next node, and (3) pointer to the previous node. We can traverse in both forward and backward directions in doubly Linked Lists.

Implementation of Linked List

Here we are implementing a Singly Linked List for the sake of understanding.

Implementation of Linked List
Implementation of Linked List
Implementation of Linked List

Frequently Asked Questions

Name some applications of Linked List?

Here are a few examples of Linked Lists' most common uses:

  1. We can implement queues, stacks, graphs, etc. using linked lists.
  2. We can add elements to the list's beginning and end using linked lists.
     

What is multiple linked list?

Each node in a multiply linked list has two or more link fields. The same set of records are joined using each field in a different order, such as "by name, by date of birth, by the department, etc."

How will you remove a cycle from a linked list?

Floyd's cycle detect technique, also referred to as the tortoise and hare algorithm because it employs two pointers/references that move at diametrically opposed speeds, is one way to spot the cycle. If there is a cycle, the two pointers (let's say, slow and fast) will point to the same element after a finite number of steps.

Conclusion

Congratulations on finishing the blog! We have discussed about linked list, their types, and their implementation in C++.


Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. For placement preparations, you must look at the problemsinterview experiences, and interview bundles.

We wish you Good Luck! 

Happy Learning!

Topics covered
1.
Introduction
2.
Why Linked List Over Array?
3.
Advantages of Linked List
4.
Disadvantages of Linked List
5.
Types of Linked List
6.
Singly Linked List
7.
Circular Linked List
8.
Doubly Linked List
9.
Implementation of Linked List
10.
Frequently Asked Questions
10.1.
Name some applications of Linked List?
10.2.
What is multiple linked list?
10.3.
How will you remove a cycle from a linked list?
11.
Conclusion