Consider a singly linked list of unknown size. You can assume that the last node has NULL or nullptr set as its next value and there is a reference to the HEAD of the linked list which can be passed into your method / function.
- Write the pseudocode for an algorithm that finds the value stored in the second to last node of this singly linked list.
- Calculate the time complexity of your algorithm. Prove your answer.
Consider a singly linked list of unknown size. You can assume that the last node has NULL or nullptr set as its next value and there is a reference to the HEAD of the linked list which can be passed into your method / function.
- Write the pseudocode for an algorithm that reverses this singly linked list.
- What is the time complexity of your algorithm? Prove your answer.
Consider a doubly linked list that uses sentinel nodes to mark its beginning and end.
- Write the pseudocode for an algorithm that takes two of these doubly linked lists and returns
trueif they store the same sequence of elements orfalseotherwise. - What is the time complexity of your algorithm? Prove your answer.
According to your textbook:
An iterator is a software design pattern that abstracts the process of scanning through a sequence of elements, one element at a time. The underlying elements might be stored in a container class, streaming through a network, or generated by a series of computations.
What the heck does this mean? What are iterators good for? Why should I care about them? Explain it to me like I am a novice software developer seeing them in C++ / Java for the first time.