We want to write a method for the SinglyLinkedList class that allows us to insert an element into the beginning of the list. We want this operation to be completed in Θ(1) time.

public void insertBeginning(Object element) {


Remember that there might be more than one case to consider here and also, don’t foget to change the length!

Toggle Solution

Here the solution that I came up with:

public void insertBeginning(Object element) {
  head = new SinglyLinkedListNode(element, head);

What we’re doing is making a new SinglyLinkedListNode with the object as its element. We’re also setting newly created SinglyLinkedListNode’s next pointer to be the previous head (which could have been null).

This operation is Θ(1) because all we’re doing is creating a new node and incrementing a counter (both of which are constant operations).

I don't claim to be perfect so if you find an error on this page, please send me an email preferably with a link to this page so that I know what I need to fix!

comments powered by Disqus