A Brief Introduction To Linked Lists


If you are a programmer, you must have heard about the concept of linked lists, quite a few times! 

 

Learning about linked lists is essential as they form an important part of the data structure. Hence, we have come up with this blog wherein we are going to explain in depth about linked lists, its categories, how it is represented and what are the functions that it performs.

 

Also, we are going to discuss how to sort a stack and remove loop in linked list. But first, you have to know about what actually linked lists are?

 

What is a Linked List? 

 

Linked lists are defined as the series of data structures which are connected to each other through links. In this sequence, there are certain items. Whereas, each link has some sort of connection with the other link. 

 

After array, linked list is the most useful and popular data structure. When you are studying about linked list, it’s important for you to understand its three main concepts:

 

  • Link: Each of the links stores a data which is called as an element.
  • Next:In a linked list, each link contains a link with the next link which is known as Next.
  • LinkedList: Linked list has some sort of connection link with the first link known as First.

 

Linked List Representation

 

As we know, a linked list is defined as the node series in which the address of your first node gets stored in a pointer named HEAD. Each of these nodes in the linked list has following parts which are:

 

  • Data item
  • Address which points towards the other node

 

As if we want to represent any of these nodes in C language the structure would be:

 

Structure node

 

{

 

Int data;

 

*next;

 

} ;



Linked List Categories

 

When you study linked lists, you should know that there are mainly three types of linked lists. They are discussed as follows:

 

Singly Linked List 

 

This category of linked list contains nodes that have data parts and an address part [ next part]. It means all the points on the next node in the sequence of that node.

 

In singly list you can mainly perform the operations of insertion, traversal and deletion.

 

Doubly Linked List 

 

In this kind of linked list, every node has data parts and mainly two addresses. One address is for the previous node and one address is for the next node. 

 

Circular Linked List 

 

Circular linked list is mostly similar to the singly linked list. It involves the usage of the last node which holds the address of the first node. It will form a circular chain. 

 

After having a clear understanding of the linked list categories, it is important to know about its operations.

 

Linked List Operations

 

Traversal 

 

If we have a linked list ‘ K’ , you can traverse the whole linked list  by starting it from the head note. Suppose if there are n number of nodes, then traversal time complexity will become O (N). 

 

Insertion

 

Inserting the new node at any given position will be achieved by manipulating the next two pointers. Consider prevNode and the newNode set. Set newNode next pointer to the prevNode next pointer and then set prevNode pointer to the newNode pointer.

 

The prevNode pointer denotes the pointer of the node where the newNode is being inserted. As only constant pointers change irrespective of what the size of the linked list is. The complexity will always be O(1)

 

Deletion

 

If we want to delete a node from the given linked list, we have to take certain steps into account. They are as follows:

 

  • Firstly find the previous node of the node which has to be deleted.
  • Secondly you should change the pointer of the next node
  • Then at last, free up the memory present in the last node.

 

In deletion, there would be chances of having a special case in which you have to delete the first node. In such cases, the head of the linked list is updated.

 

Searching

 

In order to search any given value of the list, it's important for you to traverse a linked list. Then compare the present value in the node with it. 

 

Updation

 

When you are going to update a node's value, you have to set the data part to its next value.

 

Firstly, you should update the first node value in which data is equal with the val to set to a new value called newVal.


Comments

Post a Comment

Popular posts from this blog

What are the 5 types of inheritance?

Image
  The concept of inheritance is considered among the most crucial concepts of object-oriented programming. Inheritance in Java is considered as a process where one class inherits the property of its parent class. When we simply define inheritance, we call it the capability of a class that derives the properties or features of other classes. The new class will be created as the ‘ derived class’ and the existing class will be known as base or parent class. Talking about the types of inheritance, it is generally of five types. Here, in this blog we are going to discuss all these inheritance types in detail with the help of examples. Without any ado, let’s get started! Types of inheritance In case of inheritance, one class derives the properties from its parent class. Here, any new class will be derived from its existing class. This new class is the derived class and our current class will be termed as the base class. When we talk about inheritance in Java, there are mainly five types ...
Read more

Remove duplicates from a sorted linked list

Image
Introduction Before reading this article, It is recommended to have an understanding of the linked list and its implementation and some basic operations on the linked list. Problem Description Create a function that takes a non-descending list and removes any duplicate nodes. Only one traversal of the list is necessary. Eg. Consider the given linked list: 1->1->1->2->2->3, the function is expected to convert the linked list into 1->2->3. In this article, we will extensively discuss the Label Control in C# & how to  remove duplicates from sorted doubly linked list .  Important:  We are supposed to delete only the duplicates i.e. only one copy of nodes should be there. Intuition:  The biggest hint given is that the list is sorted or non-decreasing in nature. From this, we can deduce that if duplicates are present, then it has to be the next one in the chain. The ideal way to approach this problem is to simply loop through the first value i...
Read more

How often can you Buy and Sell the same stock?

Image
The stock market is notoriously unpredictable. It can be hard enough to guess whether or not a particular investment will pay off or not. We know that understanding all the nuances of rules and regulations involved when buying and selling stocks is difficult. One big question many people have is, “How often can you buy and sell the same stock with transaction fee ?”  Before you start trading, you are unaware of the steps to follow to start trading and what would be the best time to buy and sell stock with transaction fee.  No matter if this is your first time investing or if you’ve been around the block a few times before, we hope that our guide will help you understand briefly on how to sell and buy stocks with in same time. Let's start with understanding stock trading and the types of traders in detail. What is Stock trading? The term "stock trading" describes the purchasing and selling of equities on a stock market. Investors that purchase and sell stocks with the inte...
Read more