Implement a Linked List
The most common way to be asked a linked list interview question is to be given the head node of a singly linked list. Since you are only given the head, you know that you don't have access to a wrapper class or the tail node, so all operations must happen by iterating from the beginning.
When you are given this node as an input, it will already be instantiated and have a value for its data and next.
Instead of creating a special linked list object, we will write functions that take a head node and performs a prepend, append, insert, and delete operation in the same manner as how you will use them in an interview.
See the final implementation in a REPL.
Prepend and Append
For prepend, we just want to insert a value before the head node we are given, and we can do this in constant O(1) time.
Note that this is one of the advantages of a linked list over an array. When you insert an item, you don't have to shift anything beyond it. All that needs to be done is to update pointers.
For append, we want to insert the value at the end.
Since we don't have access to the tail, we must iterate through all n items until we reach the end.
We know we have reached the tail when a node's next value is null.
Note: If we did have access to the tail, we could also append in O(1) time.
Delete a Node
To delete a node, first we find the node that precedes it in the linked list.
Then we change this preceding node's next
to reference the node after the one we want to delete (precedingNode.next = precedingNode.next.next).
Since none of the items in the linked list now no longer reference the node we wanted to delete, it is effectively removed from our linked list, and the garbage collector will recognize this and clear it from memory.
Insert an Item
To insert a node into a linked list, it requires O(n) time because we must iterate through the list to the index that we want to insert at.
Linked List Wrapper Object
It is not as likely in an interview to be given a fully implemented linked list wrapper class, but it's good to understand it for clarity or if you are asked to build it yourself.
The following is the implementation for a doubly linked list that has access to the tail.
Since it is doubly linked, nodes will have a prev pointer.
We will also track the length which is incremented each time a node is added.
Since we're using a wrapper object, it manages the head and tail for us.
You can interact with this doubly linked list wrapper class in a REPL.
Our wrapper now tracks the head and tail nodes.
When we append/prepend, we need to make sure we update our head or tail and also set the next and prev correctly.
These can all be done in constant time O(1).
Recursive Iteration
We have used a while loop to iterate through our linked lists.
Anytime we see a while loop, this is a clue that recursion would also work well.
Let's see how to iterate a linked list recursively: