Top 43 Linked Lists Interview Questions And Answers

Q: What is complexity of `push` and `pop` for a Stack implemented using a LinkedList?

O ( 1 ) . Note, you don't have to insert at the end of the list. If you insert at the front of a (singly-linked) list, they are both `O(1)`. Stack contains 1,2,3: ```py [1]->[2]->[3] ``` Push 5: ```js [5]->[1]->[2]->[3] ``` Pop: ```js [1]->[2]->[3] // returning 5 ```

Q: How to reverse a singly Linked List using only two pointers?

Nothing faster than O ( n ) can be done. You need to traverse the list and alter pointers on every node, so time will be proportional to the number of elements.

Question 1

Define Linked List

Accepted Answer

A **linked list** is a linear data structure where each element is a separate object. Each element (we will call it a **node**) of a list is comprising of two items - the **data** and a **reference (pointer)** to the next node. The last node has a reference to **null**. The entry point into a linked list is called the **head** of the list. It should be noted that _head is not a separate node,_ but the reference to the first node. If the list is empty then the head is a null reference.

Question 2

Name some advantages of Linked List

Accepted Answer

There are some:
* Linked Lists are **Dynamic Data Structure** -  it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give initial size of linked list.
* Insertion and Deletion are **simple to implement** - Unlike array here we don’t have to shift elements after insertion or deletion of an element. In linked list we just have to update the address present in next pointer of a node.
* **Efficient Memory Allocation/No Memory Wastage** - In case of array there is lot of memory wastage, like if we declare an array of size 10 and store only 6 elements in it then space of 4 elements are wasted. There is no such problem in linked list as memory is allocated only when required.

Question 3

What is a cycle/loop in the singly-linked list?

Accepted Answer

A **cycle/loop** occurs when a node’s next points _back_ to a _previous node_ in the list. The linked list is no longer linear with a beginning and end—instead, it cycles through a loop of nodes.

![](https://www.programcreek.com/wp-content/uploads/2012/12/linked-list-cycle-300x211.png)

Question 4

What is complexity of `push` and `pop` for a Stack implemented using a LinkedList?

Accepted Answer

O(1). Note, you don't have to insert at the end of the list. If you insert at the front of a (singly-linked) list, they are both `O(1)`. Stack contains 1,2,3: ```py [1]->[2]->[3] ``` Push 5: ```js [5]->[1]->[2]->[3] ``` Pop: ```js [1]->[2]->[3] // returning 5 ```

Question 5

What is time complexity of Linked List operations?

Accepted Answer

* A linked list can typically only be accessed via its head node. From there you can only traverse from node to node until you reach the node you seek. Thus **access is O(n)**. * Searching for a given value in a linked list similarly requires traversing all the elements until you find that value. Thus **search is O(n)**. * Inserting into a linked list requires re-pointing the previous node (the node before the insertion point) to the inserted node, and pointing the newly-inserted node to the next node. Thus **insertion is O(1)**. * Deleting from a linked list requires re-pointing the previous node (the node before the deleted node) to the next node (the node after the deleted node). Thus **deletion is O(1)**.

Question 6

How to reverse a singly Linked List using only two pointers?

Accepted Answer

Nothing faster than O(n) can be done. You need to traverse the list and alter pointers on every node, so time will be proportional to the number of elements.

Question 7

Under what circumstances are Linked Lists useful?

Accepted Answer

Linked lists are very useful when you need :
* to do a lot of insertions and removals, but not too much searching, on a list of arbitrary (unknown at compile\-time) length.
* splitting and joining (bidirectionally\-linked) lists is very efficient.
* You can also combine linked lists \- e.g. tree structures can be implemented as "vertical" linked lists (parent/child relationships) connecting together horizontal linked lists (siblings).

Using an array based list for these purposes has severe limitations:

*   Adding a new item means the array must be reallocated (or you must allocate more space than you need to allow for future growth and reduce the number of reallocations)
*   Removing items leaves wasted space or requires a reallocation
*   inserting items anywhere except the end involves (possibly reallocating and) copying lots of the data up one position

Question 8

Detect if a List is Cyclic using Hash Table

Accepted Answer

To detect if a list is cyclic, we can check whether a node had been visited before. A natural way is to use a hash table.

**Algorithm**

We go through each node one by one and record each node's reference (or memory address) in a hash table. If the current node is `null`, we have reached the end of the list and it must not be cyclic. If current node’s reference is in the hash table, then return true.

Question 9

What are some types of Linked List?

Accepted Answer

* A **singly linked list**

![](https://www.andrew.cmu.edu/course/15-121/lectures/Linked%20Lists/pix/linkedlist.bmp)
* A **doubly linked list** is a list that has two references, one to the next node and another to previous node.

![](https://www.andrew.cmu.edu/course/15-121/lectures/Linked%20Lists/pix/doubly.bmp)
* A **multiply linked list** - each node contains two or more link fields, each field being used to connect the same set of data records in a different order of same set(e.g., by name, by department, by date of birth, etc.).
* A **circular linked list** - where last node of the list points back to the first node (or the head) of the list.

![](https://i2.wp.com/algorithms.tutorialhorizon.com/files/2016/03/Circular-Linked-List.png)

Question 10

Name some disadvantages of Linked Lists?

Accepted Answer

Few disadvantages of linked lists are :

* They use more memory than arrays because of the storage used by their pointers.
* Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back-pointer.
* Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
* Random access has linear time.
* Nodes are stored incontiguously (no or poor cache locality), greatly increasing the time required to access individual elements within the list, especially with a CPU cache.
* If the link to list's node is accidentally destroyed then the chances of data loss after the destruction point is huge. Data recovery is not possible.
* Search is linear versus logarithmic for sorted arrays and binary search trees.
* Different amount of time is required to access each element.
* Not easy to sort the elements stored in the linear linked list.

Top 43 Linked Lists Interview Questions

Name some advantages of Linked List

Define Linked List

Name some disadvantages of Linked Lists?

Under what circumstances are Linked Lists useful?

What is time complexity of Linked List operations?

What are some types of Linked List?

What is a cycle/loop in the singly-linked list?

How to implement Linked List Using Stack?

When is a loop in a Linked List useful?

When should I use a List vs a LinkedList?

When to use a Linked List over an Array/Array List?

Why does linked list delete and insert operation have complexity of O(1)?

Compare Array based vs Linked List stack implementations

When is doubly linked list more efficient than singly linked list?

How is it possible to do Binary Search on a Doubly-Linked List in O(n) time?

How to apply Binary Search O(log n) on a sorted Linked List?

How would you compare Dynamic Arrays with Linked Lists and vice versa?

Why is Merge sort preferred over Quick sort for sorting Linked Lists?

How would you traverse a Linked List in O(n1/2)?

Why would you ever do Binary Search on a Doubly-Linked list?

Detect if a List is Cyclic using Hash Table

What is complexity of push and pop for a Stack implemented using a LinkedList?

Convert a Singly Linked List to Circular Linked List

Insert an item in a sorted Linked List maintaining order

How to reverse a singly Linked List using only two pointers?

Convert a Single Linked List to a Double Linked List

Find similar elements from two Linked Lists and return the result as a Linked List

Split the Linked List into k consecutive linked list "parts"

Remove duplicates from an unsorted Linked List

Convert a Binary Tree to a Doubly Linked List

Sum two numbers represented as Linked Lists

Implement Double Linked List from Stack with min complexity

Merge two sorted singly Linked Lists without creating new nodes

Floyd's Cycle Detect Algorithm: How to detect a Cycle (or Loop) in a Linked List?

Floyd's Cycle Detect Algorithm: Remove Cycle (Loop) from a Linked List

How to find Nth element from the end of a singly Linked List?

Floyd's Cycle Detect Algorithm: Explain how to find a starting node of a Cycle in a Linked List?

How to recursively reverse a Linked List?

Find the length of a Linked List which contains Cycle (Loop)

Given a singly Linked List, determine if it is a Palindrome

Find Merge (Intersection) Point of Two Linked Lists

Copy a Linked List with Random (Arbitrary) Pointer using O(1) Space

Do you know any better than than Floyd's algorithm for cycle detection?

Why does linked list delete and insert operation have complexity of `O(1)`?

How is it possible to do Binary Search on a Doubly-Linked List in `O(n)` time?

How to apply Binary Search `O(log n)` on a sorted Linked List?

How would you traverse a Linked List in `O(n^1/2)`?

What is complexity of `push` and `pop` for a Stack implemented using a LinkedList?

Split the Linked List into `k` consecutive linked list "parts"

How to find `Nth` element from the end of a singly Linked List?

Copy a Linked List with Random (Arbitrary) Pointer using `O(1)` Space