linked list - OpenGenus IQ: Learn Computer Science

Algorithm to detect and remove loop in a Linked List

Given a Linked list, find out whether it contains a loop or not. If it does, then remove the loop and make the last node point to NULL.

Algorithms

Algorithm to check if a linked list is sorted

In this article, we have explored an algorithm to check if a given Linked List is sorted or not in linear time O(N). It takes constant space O(1).

Algorithms

Check if Linked List is Empty

Checking if the given Linked List is empty depends on the ways Linked List has been formed (with or without root). We have covered both approaches.

Algorithms

Check whether a Singly Linked List is Palindrome or not

Linked List can be palindrome if they have the same order when it traverse from forward as well as backward. This is solved using three methods: using stack, string and by reversing the list.

Algorithms

Reverse a doubly linked list in C++

In this article, we are going to see how to reverse a doubly linked list by reversing the links of each node (without swapping values of nodes) and have implemented the solution using C++.

Algorithms

To check if the linked list is a circular linked list (2 methods)

We will be seeing two efficient methods to determine whether the given linked list is a circular linked list or not. With this, we solve the problem in linear time.

Algorithms

Cycle Detection Algorithms

A cycle in a data structure as we have already seen is a condition with no end. A few popular cycle detection algorithms are Floyd's cycle detection algorithm and Brent’s Cycle Detection Algorithm.

Data Structures

Finding the length of a loop in linked list

In this article, we will look at the method of finding the length of a loop in a linked list. For that you should be able to understand Floyd's loop detection algorithm.

Data Structures

Detect a loop in a linked list (3 methods)

A Loop in a linked list is a condition when a Linked list does not have any end. We have explored different ways to detect loop in a linked list like by marking visited nodes, using hashmap and Floyd's cycle finding algorithm.

Algorithms

Reverse alternate groups of K nodes in a Singly Linked List

We are given a pointer to the head of a singly Linked List and you have to write a function to reverse the elements of the given singly Linked List in alternate groups of K nodes. Once the operation is performed, pointer to the head of the Linked List must be returned from the function.

Algorithms

Reverse a linked list using 2 pointers technique using XOR operator

You must have come across reversing a linked list using 3 pointers technique which is the most common approach to do it. But do you know how to reverse a linked list with just 2 pointers? This article will teach you just that! Let's dive into it.

Data Structures

Circular Linked List

Circular Linked list is a complex form of a linked list data structure as within a circular linked list the last node points to the first node of the list. We have covered it in detail with all operations and implementation in Java.

Data Structures

XOR Linked List

XOR Linked List is the memory efficient version of Doubly Linked List because it makes use of only one space for address field with every node. It provides facilitates list traversal in both forward and backward directions. Insertion and deletion operations take constant time

Data Structures

Skip List

A skip list is a data structure that is used for storing a sorted list of items with a help of hierarchy of linked lists that connect increasingly sparse subsequences of the items. A skip list allows the process of item look up in efficient manner. The time complexity of operations are O(log N)

Data Structures

Doubly Linked List

Doubly Linked List has the flexibility of traversing the list in both the ways i.e., forward and backward unlike singly linked list where movement is restricted in forward direction only. Doubly Linked List contains an extra pointer to link the previous node which enables the backward traversing.

Data Structures

Implementing Queue using Linked list

A queue (First in First out) is an ordered collection of items where the addition of new items happens at one end, called the rear, and removal of existing items occurs at the other end called front. It can be implemented using Linked Lists which brings many advantages over array implementation

linked list

Flattening a Linked List

In this article, we explored an algorithm to flatten a linked list where each node has two pointers with one to another linked list. Our approach explored a novel application of the merge component of merge sort to solve this problem.

linked list

Find the middle element of a singly Linked List

In this article, we will explore two approaches to find the middle element of a singly linked list. In one approach, we will use one traversal to count the number of elements and the other to find the middle element. The second approach is to use one traversal and concept of fast and slow pointers.

linked list

Sort a Linked List which is already sorted on absolute values

Algorithm Example Complexity Implementations Questions Reading time: 15 minutes | Coding time: 5 minutes The problem at hand is to sort a singly Linked List which is already sorted on absolute value. Sorting always

linked list

Merge Sort a singly Linked List

Algorithm Complexity Implementations Questions Merge sort is a fast comparison based sorting algorithm which can be utilized in sorting a Linked List as well. Merge Sort is preferred for sorting a linked list.

linked list

Insertion Sort a Linked List

Algorithm Pseudocode Complexity Implementations Questions Reading time: 15 minutes | Coding time: 20 minutes Insertion sort is a comparison based sorting algorithm which can be utilized in sorting a Linked List as well. Insertion

linked list

Insert element in a sorted Linked List

Pseudocode Implementations Complexity Can binary search be used to improve performance? Reading time: 15 minutes | Coding time: 20 minutes In this session, we will explore how to insert an element in a sorted

linked list

Deletion operation in a Linked List

How to delete a node? Delete first node Delete last node Pseudocode Implementations Complexity Reading time: 15 minutes | Coding time: 20 minutes Linked List is an efficient data structure to store data. You

linked list

Insertion operation in a Linked List

How to insert a node at front? Insert a node at a particular location How to insert a node at end? Implementations Complexity Reading time: 15 minutes | Coding time: 20 minutes Linked List

linked list

Search an element in a Linked List

How to search a node? Why is searching in Linked List slower than arrays? Is binary search possible in Linked List? Implementations Complexity Reading time: 15 minutes | Coding time: 20 minutes Linked List