Singly linked lists contain basically car/cdr, Doubly linked lists contain another container it seems Linked lists are null terminated. They can be circular, where one node points to a previous node in the chain.
What is a sentinel key?
Access/Entry
Usually, this can be called the front pointer or the head. The last one is usually called the tail. There also exists front + back pointers.
When adding a node to the end of a list, if the list had a tail pointer, you’ll need to move the tail to the end of the list.
When deleting the end of the list, we can’t just delete the tail as that would leave a dangling pointer, so that would be o(n) since we have to traverse the list.
When inserting a value into a doubly linked list, create a temporary node to the new value, point temp→prev = curr, temp→ next = curr→next, then curr→next→prev = temp and curr→next = temp. Alternatively, add a variable here representing curr→next called like curr_n or whatever and pointe that.
To delete a value from a doubly linked list:
curr→ next→prev = curr→prev curr→prev→next = curr→next
delete curr curr = null
Circular singly linked list
complexity O(1) to remove the first element. However because it is circular moving the head of the list is O(1) and that would change the first/last element of the list in one operation.
Circular double linked list
Same thing goes for double linked lists though it uses more operations and lines of code.
Sentinel nodes
Sentinel nodes are lists that contain dummy nodes at the ends of the lists which do not contain any data. They eliminate the special cases for list modifications, like insert remove first and last nodes, all the cases are implemented the same way.
Recursion in math
For a proof of a recursive function, you need a base case and a recursive case where the recursive case is