What is the difference between a singly-linked list and a doubly-linked list?
A singly linked list is typically connected in one direction while a doubly linked list is a complex type of complex link in which a node contains some data as well as a pointer to the next and the previous node present in the list. Again, the singly linked list permits traversal in one way only while the doubly linked list permits a two-way traversal. Besides, a singly linked list uses minimal memory in every node while a doubly linked list uses more memory in every node. Lastly, a singly linked list is mainly used for stacks while a doubly-linked list is mostly used to execute stacks, heaps as well as binary trees.
In what situation would you use a singly-linked list over a doubly-linked list?
Mainly, a singly linked list is easier to declare as compared to a doubly-linked list which requires an additional node to manage and perform operations since it has an address of the previous and the next node. Further, a singly linked list requires less memory to perform as compared to a doubly-linked list. In a singly linked list, traversal can be done only using the next node. Lastly, a singly linked list provides a better direct assessment of an element while in a double linked list, the memory is stored randomly thus elements are accessed.
In what situation would you use a doubly-linked list over a singly-linked list?
If a node is in a linked list with N nodes, how many nodes will be traversed during a search for the node? Explain the best- and worst-case search scenarios.
Mainly, since it is not easy to access any element present in the linked list, then we can only traverse. In that regard, to search a node, it is essential to first start a list from the beginning, then continue scanning until we reach the end of the list or if we find the match. Therefore we need to traverse the O (n), that is, the number of nodes to search.
Best Case Scenario: When the node is present at the inception of the list itself. Thus, in this case, only one node is traversed.
Worst Case Scenario: When the node is not found at the last node of the list itself, then we will have to traverse the number of nodes.
Explain why a singly-linked list defines a Remove After the () function, while a doubly-linked list defines a Remove() function.
Typically, a singly linked list node does not store the reference to the preceding node and only possesses a pointer for the subsequent node. To delete a note, it is important to know what was the address of the preceding node of the actual node that we want to get rid of so that the linked list can stay connected after the node has been deleted, hence it uses RemoveAfter() function. While in a doubly-linked list, there are pointers to preceding and succeeding nodes, hence we can easily delete a code directly and connect it to the preceding and succeeding directly, thus it uses Remove() function.
Could a Remove After() function also be defined for a doubly-linked list? Explain why or why not.
Yes, the main reason being that RemoveAfter() function could be defined for a DLL. Since it posses all the features of SLL so the SLL functions can be employed for a DLL. To employ the RemoveAfter function, it is essential to make sure that the node has a pointer to the succeeding node and that it is applicable for the DLL. RemoveAfter() can be employed for singly-linked lists as well as doubly-linked lists.
Could a Remove() function also be defined for a singly-linked list? Explain why or why not.
No, the key reason being that Remove function could not be employed for SLL. Since using the RemoveAfter() function, it is essential to make sure that every node has the preceding and the succeeding pointers which do not apply to SLL because they only possess the next point. As a result, Remove() function can be used only for a doubly-linked list and not for SLL.