Consider the following declaration for the nodes of a linked list of integers: c
ID: 3890645 • Letter: C
Question
Consider the following declaration for the nodes of a linked list of integers:
class Node {
private int datum;
private Node next;
}
(a) Define a function contains which satisfies the following claim: If L is the head of a linked of list of integers and X is an integer, then contains(L, X) is true if and only if, X L.
(b) Define a recursive function append which satisfies the following claim: If L is the head of a linked list of integers and X is an integer, then append(L, X) is the list that results from adding X to the end of the list L.
(c) Define an iterative function size which satisfies the following claim: If L is the head of a linked list of integers, then size(L) is the number of elements of L.
Explanation / Answer
a) The function definition of contains(L,X) is given below:
//Checking whether the value X is present in linked list
public boolean contains(Node L, int X)
{
Node current = L; //Initializing current Node to head of the List
while (current != null)
{
if (current.datum == X)
return true; //data found, X is present in List
current = current.next;
}
return false; //data not found, X is not present in List
}
b) The function definition of recursive append(L,X) function is given below:
public Node append(Node L, int X)
{
if (L == null)
{
L = new Node(X);/* this would create a new Node and set the reference at the end of the list*/
}
else
{
L.next = append(L.next, X);//recursive call
}
return L;
}
c) The iterative function definition of size(L) is given below:
/* Returns number of elements in linked list */
public int size(Node L)
{
Node temp =L;//L is the head of the linklist
int count = 0;
while (temp != null)
{
count++;
temp = temp.next;
}
return count;//returning the size of linklist
}
/*If this helps you, please let me know by giving a positive thumbs up. In case you have any queries, do let me know. I will revert back to you. Thank you!!*/