Photo by Mohammad Rahmani on Unsplash
The Linked-List -> in Easiest Way!
When you want to study Linked-List in a perfect way. Just read these question with the answers.
Questions:
Here are 11 questions about linked lists:
1-What is a linked list? [Done!]
2-What are the different types of linked lists? [Done!]
3-What are the advantages and disadvantages of linked lists? [Done!]
4-What are the basic operations on linked lists? [Done!]
5-How do you insert a node into a linked list? [Done!]
6-How do you delete a node from a linked list? [Done!]
7-How do you search for a node in a linked list? [Done!]
8-How do you reverse a linked list? [Done!]
9-How do you check if a linked list is circular? [Done!]
10-How do you merge two linked lists? [Done!]
11-Can you explain the difference between a singly linked list and a doubly linked list?[Done!]
Answers:
1-What is a linked list?
There more than one 1-What is a linked list? [Done!] on the Linked-List [Algorithms Book - Introduction to Algorithm - Geeks for Geeks… and so forth]
So => Linked-List briefly is a [Data Structure] which stores Data Sequential in a list of nodes and this Data-Structure may be either an Empty list or has a Data.
-Linked-List is Representing SEQUENTIAL DATA.
-Linked-List is a Fundamental Alternative to Arrays.
2-What are the different types of linked lists?
There are 5 types of Linked-List:
1-Singly Linked-List. -> has one pointer [next]
2-Doubly Linked-List. -> has two pointers [next, previous]
There is another name for DLL -> Two-Way Linked List.
3-Circular Linked-List. -> has one pointer [next] and Last node [Tail.Next] Points to the Head.
There is another name for Circular -LL- -> Ring of…
4-Doubly Circular Linked-List -> has two pointers [next, previous] and last node [Tail.next] Points to the Head, and First node [Head.previous] Points to the Tail.
5-Header Linked-List -> until now I really do not know!
3-What are the advantages and disadvantages of linked lists?
The Advantages:
1-It’s Dynamic not Fixed, so you do not need to specify size of its length like Arrays.
2-in DLL you can Traversed Backward.
The Disadvantages:
1-In DDL can take 2x memory.
2-In SLL can not easily access previous elements.
4-What are the basic operations on linked lists?
1-Insertion [From Top like Stack LIFO] or [From Head or Tail - FIFO- like Deque].
2-Deletion [From Top like Stack FILO] or [From Head or Tail F-IFO- like Deque].
3-Checking if the list is Empty or not {isEmpty()} method.
4-Returning the Size of the List {size()} method.
5-Knowing the Peak-Top or First-Head of the List -> Peek, PeakFirst, PeakLast.
6-Checking if there is a data or not in the list [contains()] method.
7-Getting value by its index [get()] method.
8-Setting value instead of exists value by changing its value [set()] method.
9-Iteration throughout the list by implement {Iterable interface}.
5-How do you insert a node into a linked list?
You can insert a node to the linked list by creating a method add/push which is void, which take Generic data as parameters/argument.
-> 1-you check if the list is empty or not by invoking isEmpty() method,
-> 2-if yes, then create a node in the head of the list.
-> 3- If it’s not an empty list -> then add the element to the last list [if it’s a Stack] or to the beginning [if it’s a Queue].
Bard Suggestion:
Your answer is correct, but I would add that the node can be inserted at any position in the linked list, not just at the beginning or the end. To insert a node at a specific position, we need to traverse the linked list until we reach the desired position, and then insert the new node between the current node and the next node.
6-How do you delete a node from a linked list?
You can delete a node from the linked list by creating a method pop/remove which is T [Generic Method] and take a Node Parameters/Arguments and will return the DELETED node.
-> 1-you check if the list is empty or not by invoking isEmpty() method,
-> 2-if yes, then return Null Exception Error.
-> 3- If it’s not an empty list -> then delete the element from the last list [if it’s a Stack] or from the beginning [if it’s a Queue].
Bard Suggestion:
Your answer is correct, but I would add that we should also check if the node to be deleted exists in the linked list before attempting to delete it. If the node does not exist, we can return an error message or simply do nothing.
7-How do you search for a node in a linked list?
You can find a node in the linked list by creating a method get(Node T).
-> 1-it will return the specified node that we want.
-> 2- declare a node {current} and make it equals to the head -> Head.data.
-> 3- creating while-loop and check if {current != null}
-> 4- then if this current is equals to the Node that we compare to
-> 5- then return it.
-> 6- if not found do not do anything.
Bard’s Suggestion:
Your answer is correct, but I would add that we can also use a recursive approach to search for a node in a linked list. The recursive approach is more efficient, especially for large linked lists.
8-How do you reverse a linked list?
You can reverse a linked list using TWO ways.
1-Iteratively.
2-Recursively.
1- To reverse linked list Iteratively:
-> 1- Create a method which is T Generic and not taking arguments.
-> 2- Create new node {current} and initialise it = head.
-> 3- Create new node {previous} and initialise it = null.
-> 4- Create While-loop with condition (current != null)
-> 5- Create new node {Next} and initialise = current.next
\=> current.next = prev;
prev = current;
current = next;
End While-loop.
6- after while loop make previous = head => to start from The Tail [end of the list].
2- To reverse linked list Recursively:
-> following this Method:
if (head == null) return prev;
Node next = head.next;
head.next = prev;
return reverse_recursively(next, prev);
Bard’s Suggestion:
Your answer is correct, but I would add that the recursive approach to reversing a linked list is more concise and elegant than the iterative approach.
9-How do you check if a linked list is circular?
There are two main ways to check if a linked list is circular:
1- Using a hash table:
This method involves creating a hash table and storing the addresses of all the nodes in the linked list in the hash table. As we traverse the linked list, we check if the address of the current node is already present in the hash table. If it is, then the linked list is circular. If it is not, then we add the address of the current node to the hash table and continue traversing the linked list.
1-A pseudocode implementation of the Hash Table:
def is_circular_linked_list(head):
# Create a hash table.
hash_table = {}
# Traverse the linked list.
current_node = head
while current_node:
# Check if the address of the current node is already present in the hash table.
if current_node in hash_table:
# The linked list is circular.
return True
# Add the address of the current node to the hash table.
hash_table[current_node] = True
# Move to the next node in the linked list.
current_node = current_node.next
# The linked list is not circular.
return False
2- Using two pointers:
This method involves using two pointers, slow and fast, to traverse the linked list. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. If the linked list is circular, then the two pointers will eventually meet. If the linked list is not circular, then the fast pointer will eventually reach the end of the linked list.
2-A pseudocode implementation of the Two Pointers:
def is_circular_linked_list(head):
# Initialize the two pointers.
slow_pointer = head
fast_pointer = head
# Traverse the linked list.
while fast_pointer and fast_pointer.next:
# Move the slow pointer one node at a time.
slow_pointer = slow_pointer.next
# Move the fast pointer two nodes at a time.
fast_pointer = fast_pointer.next.next
# If the two pointers meet, then the linked list is circular.
if slow_pointer == fast_pointer:
return True
# The linked list is not circular.
return False
10-How do you merge two linked lists? Not my answer
In Java, you can merge two linked lists in one line using the addAll() method from the java.util.LinkedList class. Here's an example:
This code line => list1.addAll(list2);
Assuming list1 and list2 are instances of LinkedList, this line of code will merge list2 into list1, appending the elements of list2 to the end of list1. After execution, list1 will contain all the elements from both lists, effectively merging them.
11-Can you explain the difference between a singly linked list and a doubly linked list?
SLL->
1-Has [next] pointer, and it’s difficult to access to the previous node.
2- The SSL O(n), because it will through LL by just [Next].
DLL->
1-Has two pointers [Next, Previous], it’s easy to access to the previous node.
2- The DDL O(n^2), because of two pointers.
This is a Linked-List in Briefly.
Here are some more medium-level linked list questions to you to Answer:
Remove all duplicates from a sorted linked list.
Reverse a linked list in groups of k.
Check if a linked list is a palindrome.
Flatten a multi-level linked list.
Find the intersection point of two linked lists.
Merge two sorted linked lists into a single sorted linked list.
Add two numbers represented by linked lists.
Rotate a linked list by k nodes.
Split a linked list into two halves.
Find the middle node of a linked list in O(1) time.
Implement a stack and queue using a linked list.
Implement a least recently used (LRU) cache using a linked list.
These questions cover a variety of linked list topics, including insertion, deletion, searching, sorting, and traversing. They also cover some more advanced topics, such as finding the intersection point of two linked lists and implementing a stack and queue using a linked list.