Singly Linked Lists - Other Operations

isEmpty

The list isEmpty operation is rather straightforward. We simply need to return the truth of whether head.next has a null pointer. Obviously, isEmpty runs in constant time.

function isEmpty() returns boolean
    return head == NULL       (1)
end function

peek

The peek operation is designed to return the data from the last node inserted into the list, which is the node pointed at by head. This is easy to do; however, we must ensure that we check to see if the list is empty in line 1 before we return the head.data in line 3. Due to its simple structure, the run time of the peek operation is constant.

function peek() returns data
	if isEmpty()			(1)
		raise exception		(2)
	end if
	return head.data		(3)
end function

peekEnd

The peekEnd operation is designed to return the first node inserted into the list, which is now the last node in the list. Like the peek operation, we must ensure the list is not empty in line 1 before actually searching for the end of the list. Lines 3 – 5 walk through the list using a while statement until curr.next is null, signifying that curr is pointing at the last node in the queue. Finally, line 6 simply returns the data in the last node. Since peekEnd must walk through the entire list to find the last node, it runs in order $N$ time.

function peekEnd() returns data
	if isEmpty()			    (1)
		raise exception		    (2)
	end if
    curr = head 			    (3)
    while curr.next != null		(4)
        curr = curr.next		(5)
    end while
    return curr.data			(6)
end function