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.
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.
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.
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.
-
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.
- 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_).
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
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.
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.
public void reverse(Node head) { Node curr = head, prev = null; while (head.next != null) { head = head.next; // move the head to next node curr.next = prev; // break the link to the next node and assign it to previous prev = curr; // we are done with previous, move it to next node curr = head; // current moves along with head } head.next = prev; //for last node } _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 5 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.
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 only_O_(_1_)time. - Space complexity:
_O_(_n_). The space depends on the number of elements added to the hash table, which contains at mostnelements.
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; } 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
def convertTocircular(head): # declare a node variable # start and assign head # node into start node. start = head # check that while head.next # not equal to null then head # points to next node. while(head.next is not None): head = head.next # if head.next points to null # then start assign to the # head.next node. head.next = start return start 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.
Thanks 🙌 for reading and good luck on your next tech interview!
Explore 3800+ dev interview question here 👉 Devinterview.io