You can check all 43 Linked Lists interview questions here 👉 https://devinterview.io/data/linkedLists-interview-questions
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.
Source: www.thecrazyprogrammer.com
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.
Source: www.cs.cmu.edu
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.
Source: www.quora.com
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.
Source: www.interviewcake.com
- A singly linked list
- A doubly linked list is a list that has two references, one to the next node and another to previous node.
- 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.
Source: www.cs.cmu.edu
- 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).
Source: github.com
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
Source: stackoverflow.com
You can simulate a linked list by using two stacks. One stack is the "list," and the other is used for temporary storage.
- To add an item at the head, simply push the item onto the stack.
- To remove from the head, pop from the stack.
- To insert into the middle somewhere, pop items from the "list" stack and push them onto the temporary stack until you get to your insertion point. Push the new item onto the "list" stack, then pop from the temporary stack and push back onto the "list" stack. Deletion of an arbitrary node is similar.
This isn't terribly efficient, by the way, but it would in fact work.
Source: stackoverflow.com
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.
Implementation
Java Java
public void reverse(Node head) { Node curr = head, prev = null;<span class="token cVar">while</span> <span class="token cBase">(</span>head<span class="token cBase">.</span>next <span class="token cBase">!=</span> <span class="token cVar">null</span><span class="token cBase">)</span> <span class="token cBase">{</span> head <span class="token cBase">=</span> head<span class="token cBase">.</span>next<span class="token cBase">;</span> <span class="token cComment">// move the head to next node</span> curr<span class="token cBase">.</span>next <span class="token cBase">=</span> prev<span class="token cBase">;</span> <span class="token cComment">// break the link to the next node and assign it to previous</span> prev <span class="token cBase">=</span> curr<span class="token cBase">;</span> <span class="token cComment">// we are done with previous, move it to next node</span> curr <span class="token cBase">=</span> head<span class="token cBase">;</span> <span class="token cComment">// current moves along with head</span> <span class="token cBase">}</span> head<span class="token cBase">.</span>next <span class="token cBase">=</span> prev<span class="token cBase">;</span> <span class="token cComment">//for last node</span>
}
Source: stackoverflow.com
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:
[1]->[2]->[3]Push 5:
[5]->[1]->[2]->[3]Pop:
[1]->[2]->[3] // returning 5Source: stackoverflow.com
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.
Complexity Analysis
Time:
Constant
O(1)
Dbl. Logarithmic
O(log log n)
Logarithmic
O(log n)
Square Root
O(√n)
Linear
O(n)
Linearithmic
O(n log n)
Quadratic
O(n2)
Exponential
O(2n)
Factorial
O(n!)
Space:
Constant
O(1)
Dbl. Logarithmic
O(log log n)
Logarithmic
O(log n)
Square Root
O(√n)
Linear
O(n)
Linearithmic
O(n log n)
Quadratic
O(n2)
Exponential
O(2n)
Factorial
O(n!)
Time: O(n)
Space: O(n)
- Time complexity :
O(n). We visit each of thenelements in the list at most once. Adding a node to the hash table costs onlyO(1)time. - Space complexity:
O(n). The space depends on the number of elements added to the hash table, which contains at mostnelements.
Implementation
Java Java
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}Source: leetcode.com
To convert a singly linked list to circular linked list, we will set next pointer of tail node to head pointer.
- Create a copy of head pointer, let's say
temp. - Using a loop, traverse linked list till tail node (last node) using temp pointer.
- Now set the next pointer of tail node to head node.
temp->next = head
Implementation
Python PY
def convertTocircular(head): # declare a node variable # start and assign head # node into start node. start = head<span class="token cComment"># check that</span> <span class="token cVar">while</span> head<span class="token cBase">.</span><span class="token builtin">next</span> <span class="token cComment"># not equal to null then head</span> <span class="token cComment"># points to next node.</span> <span class="token cVar">while</span><span class="token cBase">(</span>head<span class="token cBase">.</span><span class="token builtin">next</span> <span class="token cVar">is</span> <span class="token cVar">not</span> <span class="token cBool">None</span><span class="token cBase">)</span><span class="token cBase">:</span> head <span class="token cBase">=</span> head<span class="token cBase">.</span><span class="token builtin">next</span> <span class="token cComment">#</span> <span class="token cVar">if</span> head<span class="token cBase">.</span><span class="token builtin">next</span> points to null <span class="token cComment"># then start assign to the</span> <span class="token cComment"># head.next node.</span> head<span class="token cBase">.</span><span class="token builtin">next</span> <span class="token cBase">=</span> start <span class="token cVar">return</span> start</code></pre></div></div></div><div class="row my-2"><div><span><i>Source:</i> <span><a href="https://www.techcrashcourse.com/2016/06/program-convert-singly-linked-list-to-circular-linked-list.html" rel="noreferrer" target="_blank" title="Convert a Singly Linked List to Circular Linked List Interview Questions Source To Answer">www.techcrashcourse.com</a></span></span> </div></div></div></div></div> <br><br></div><div data-v-5e9078c0="" class="unit"><div><h2>🔹 13. Insert an item in a sorted Linked List maintaining order</h2></div> <div><h3>Answer:</h3> <div class="answer"><div><div><div class="AnswerBody"><p>The <code>add()</code> method below walks down the list until it finds the appropriate position. Then, it splices in the new node and updates the <code>start</code>, <code>prev</code>, and <code>curr</code> pointers where applicable.</p><p>Note that the reverse operation, namely <em>removing</em> elements, doesn't need to change, because you are simply throwing things away which would not change any order in the list.</p></div></div><div style="font-size: 14px;"><div class="mb-3 mt-2"><span class="h5">Implementation</span></div><div><nav class="mdc-tab-bar"><div class="mdc-tab-scroller"><div class="mdc-tab-scroller__scroll-area mdc-tab-scroller__scroll-area--scroll" style="margin-bottom: 0px;"><div class="mdc-tab-scroller__scroll-content"><button class="mdc-ripple-upgraded mdc-ripple-upgraded--background-focused mdc-tab mdc-tab--min-width mdc-tab--active" aria-selected="true" tabindex="0"><div class="mdc-tab__content"><span class="mdc-tab__text-label"><span>Java</span> <span class="shadow-text lang-badge java">Java</span></span></div><span class="mdc-tab-indicator mdc-tab-indicator--active"><span aria-hidden="true" class="mdc-tab-indicator__content mdc-tab-indicator__content--underline"></span></span><div class="mdc-tab__ripple mdc-ripple-upgraded mdc-ripple-upgraded--background-focused"></div></button></div></div></div></nav></div><div class="mt-2"><div class="AnswerBody"><pre><code><span class="token cVar">public</span> <span class="token cVar">void</span> <span class="token cMod">add</span><span class="token cBase">(</span><span class="token class-name">T</span> x<span class="token cBase">)</span> <span class="token cBase">{</span> <span class="token class-name">Node</span> newNode <span class="token cBase">=</span> <span class="token cVar">new</span> <span class="token class-name">Node</span><span class="token cBase">(</span><span class="token cBase">)</span><span class="token cBase">;</span> newNode<span class="token cBase">.</span>info <span class="token cBase">=</span> x<span class="token cBase">;</span> <span class="token cComment">// case: start is null; just assign start to the new node and return</span> <span class="token cVar">if</span> <span class="token cBase">(</span>start <span class="token cBase">==</span> <span class="token cVar">null</span><span class="token cBase">)</span> <span class="token cBase">{</span> start <span class="token cBase">=</span> newNode<span class="token cBase">;</span> curr <span class="token cBase">=</span> start<span class="token cBase">;</span> <span class="token cComment">// prev is null, hence not formally assigned here</span> <span class="token cVar">return</span><span class="token cBase">;</span> <span class="token cBase">}</span> <span class="token cComment">// case: new node to be inserted comes before the current start;</span> <span class="token cComment">// in this case, point the new node to start, update pointers, and return</span> <span class="token cVar">if</span> <span class="token cBase">(</span>x<span class="token cBase">.</span><span class="token cMod">compareTo</span><span class="token cBase">(</span>start<span class="token cBase">.</span>info<span class="token cBase">)</span> <span class="token cBase"><</span> <span class="token cNum">0</span><span class="token cBase">)</span> <span class="token cBase">{</span> newNode<span class="token cBase">.</span>link <span class="token cBase">=</span> start<span class="token cBase">;</span> start <span class="token cBase">=</span> newNode<span class="token cBase">;</span> curr <span class="token cBase">=</span> start<span class="token cBase">;</span> <span class="token cComment">// again we leave prev undefined, as it is null</span> <span class="token cVar">return</span><span class="token cBase">;</span> <span class="token cBase">}</span> <span class="token cComment">// otherwise walk down the list until reaching either the end of the list</span> <span class="token cComment">// or the first position whose element is greater than the node to be</span> <span class="token cComment">// inserted; then insert the node and update the pointers</span> prev <span class="token cBase">=</span> start<span class="token cBase">;</span> curr <span class="token cBase">=</span> start<span class="token cBase">;</span> <span class="token cVar">while</span> <span class="token cBase">(</span>curr <span class="token cBase">!=</span> <span class="token cVar">null</span> <span class="token cBase">&&</span> x<span class="token cBase">.</span><span class="token cMod">compareTo</span><span class="token cBase">(</span>curr<span class="token cBase">.</span>info<span class="token cBase">)</span> <span class="token cBase">>=</span> <span class="token cNum">0</span><span class="token cBase">)</span> <span class="token cBase">{</span> prev <span class="token cBase">=</span> curr<span class="token cBase">;</span> curr <span class="token cBase">=</span> curr<span class="token cBase">.</span>link<span class="token cBase">;</span> <span class="token cBase">}</span> <span class="token cComment">// splice in the new node and update the curr pointer (prev already correct)</span> newNode<span class="token cBase">.</span>link <span class="token cBase">=</span> prev<span class="token cBase">.</span>link<span class="token cBase">;</span> prev<span class="token cBase">.</span>link <span class="token cBase">=</span> newNode<span class="token cBase">;</span> curr <span class="token cBase">=</span> newNode<span class="token cBase">;</span>
}
Source: stackoverflow.com
A doubly linked list is simply a linked list where every element has both next and prev mebers, pointing at the elements before and after it, not just the one after it in a single linked list.
so to convert your list to a doubly linked list, just change your node to be:
private class Node
{
Picture data;
Node pNext;
Node pPrev;
};and when iterating the list, on each new node add a reference to the previous node.
Source: stackoverflow.com
Thanks 🙌 for reading and good luck on your next tech interview!
Explore 3800+ dev interview question here 👉 Devinterview.io