9. On the last page of these review problems is an implementation of the IntNode
ID: 3599983 • Letter: 9
Question
9. On the last page of these review problems is an implementation of the IntNode class (a) Write an implementation of the static method public static int countZeros( IntNode node) that will count the number of zeros that occur in the given linked list of ints (b) Write an implementation of a static method public static String list2String( IntNode node ) that returns a String representation of the linked list referred to by the parameter node. If the linked list is empty, the String representation should be "[]" (two square brackets next to each other). If the linked list is not empty, the String representation should look like this, "C 3 52 0 2 -4 16 ]", with a space before and after each entry of the list. (c) Write a method public static IntNode removeFirst IntNode head ) that returns a reference to the second node from the linked list referred to by the parameter head (d) Write a methood public static IntNode addFirst( int element, IntNode head) that returns a reference to the new head of a linked list with a node containing element followed by the list referred to by the parameter head (e) Write a method public static void set( int element, int i, IntNode head ) that modifies the list referred to by the parameter head so that the i'th node in the list has its data changed to element. If there is no i'th node in the list, then the list is not modifiedExplanation / Answer
Program 1 :
class CountZeros
{
/* if 0 is present in arr[] then returns the index of FIRST occurrence
of 0 in arr[low..high], otherwise returns -1 */
int firstZero(int arr[], int low, int high)
{
if (high >= low)
{
// Check if mid element is first 0
int mid = low + (high - low) / 2;
if ((mid == 0 || arr[mid - 1] == 1) && arr[mid] == 0)
return mid;
if (arr[mid] == 1) // If mid element is not 0
return firstZero(arr, (mid + 1), high);
else // If mid element is 0, but not first 0
return firstZero(arr, low, (mid - 1));
}
return -1;
}
// A wrapper over recursive function firstZero()
int countZeroes(int arr[], int n)
{
// Find index of first zero in given array
int first = firstZero(arr, 0, n - 1);
// If 0 is not present at all, return 0
if (first == -1)
return 0;
return (n - first);
}
// Driver program to test above functions
public static void main(String[] args)
{
CountZeros count = new CountZeros();
int arr[] = {1, 1, 1, 0, 0, 0, 0, 0};
int n = arr.length;
System.out.println("Count of zeroes is " + count.countZeroes(arr, n));
}
}
Output:
Program 3 :
// Java program to find n'th node in linked list
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
class LinkedList
{
Node head; //the head of list
/* Takes index as argument and return data at index*/
public int GetNth(int index)
{
Node current = head;
int count = 0; /* index of Node we are
currently looking at */
while (current != null)
{
if (count == index)
return current.data;
count++;
current = current.next;
}
/* if we get to this line, the caller was asking
for a non-existent element so we assert fail */
assert(false);
return 0;
}
/* Given a reference to the head of a list and an int,
inserts a new Node on the front of the list. */
public void push(int new_data)
{
/* 1. alloc the Node and put data*/
Node new_Node = new Node(new_data);
/* 2. Make next of new Node as head */
new_Node.next = head;
/* 3. Move the head to point to new Node */
head = new_Node;
}
/* Drier program to test above functions*/
public static void main(String[] args)
{
/* Start with empty list */
LinkedList llist = new LinkedList();
/* Use push() to construct below list
1->12->1->4->1 */
llist.push(1);
llist.push(4);
llist.push(1);
llist.push(12);
llist.push(1);
/* Check the count function */
System.out.println("Element at index 3 is "+llist.GetNth(3));
}
}
Output:
Program 2 :
Program 4:
To get the nth node from the tail of the linked list, we can calculate the length of the entire list by traversing the list once. Let this length be l. nth node from the tail is the (l-n+1)th node from the start. Or we can use two pointers. We can increment one of these to point to the nth node from the start and then increment both of these simultaneously till the first node reaches the end of the list. The second node points to the nth node from the tail.
Pseudocode:
Program 5 :
1) Functions that do not modify the head pointer: Examples of such functions include, printing a linked list, updating data members of nodes like adding given a value to all nodes, or some other operation which access/update data of nodes
It is generally easy to decide prototype of functions of this category. We can always pass head pointer as an argument and traverse/update the list. For example, the following function that adds x to data members of all nodes.
void addXtoList(struct Node *node, int x)
{
while(node != NULL)
{
node->data = node->data + x;
node = node->next;
}
}
Run on IDE
2) Functions that modify the head pointer: Examples include, inserting a node at the beginning (head pointer is always modified in this function), inserting a node at the end (head pointer is modified only when the first node is being inserted), deleting a given node (head pointer is modified when the deleted node is first node). There may be different ways to update the head pointer in these functions. Let us discuss these ways using following simple problem:
“Given a linked list, write a function deleteFirst() that deletes the first node of a given linked list. For example, if the list is 1->2->3->4, then it should be modified to 2->3->4”
Algorithm to solve the problem is a simple 3 step process: (a) Store the head pointer (b) change the head pointer to point to next node (c) delete the previous head node.
Following are different ways to update head pointer in deleteFirst() so that the list is updated everywhere.
2.1) Make head pointer global: We can make the head pointer global so that it can be accessed and updated in our function. Following is C code that uses global head pointer.
// global head pointer
struct Node *head = NULL;
// function to delete first node: uses approach 2.1
// See http://ideone.com/ClfQB for complete program and output
void deleteFirst()
{
if(head != NULL)
{
// store the old value of head pointer
struct Node *temp = head;
// Change head pointer to point to next node
head = head->next;
// delete memory allocated for the previous head node
free(temp);
}
}
Run on IDE
See this for complete running program that uses above function.
This is not a recommended way as it has many problems like following:
a) head is globally accessible, so it can be modified anywhere in your project and may lead to unpredictable results.
b) If there are multiple linked lists, then multiple global head pointers with different names are needed.
See this to know all reasons why should we avoid global variables in our projects.
2.2) Return head pointer: We can write deleteFirst() in such a way that it returns the modified head pointer. Whoever is using this function, have to use the returned value to update the head node.
// function to delete first node: uses approach 2.2
// See http://ideone.com/P5oLe for complete program and output
struct Node *deleteFirst(struct Node *head)
{
if(head != NULL)
{
// store the old value of head pointer
struct Node *temp = head;
// Change head pointer to point to next node
head = head->next;
// delete memory allocated for the previous head node
free(temp);
}
return head;
}
Run on IDE
See this for complete program and output.
This approach is much better than the previous 1. There is only one issue with this, if user misses to assign the returned value to head, then things become messy. C/C++ compilers allows to call a function without assigning the returned value.
head = deleteFirst(head); // proper use of deleteFirst()
deleteFirst(head); // improper use of deleteFirst(), allowed by compiler
Run on IDE
2.3) Use Double Pointer: This approach follows the simple C rule: if you want to modify local variable of one function inside another function, pass pointer to that variable. So we can pass pointer to the head pointer to modify the head pointer in our deleteFirst() function.
// function to delete first node: uses approach 2.3
// See http://ideone.com/9GwTb for complete program and output
void deleteFirst(struct Node **head_ref)
{
if(*head_ref != NULL)
{
// store the old value of pointer to head pointer
struct Node *temp = *head_ref;
// Change head pointer to point to next node
*head_ref = (*head_ref)->next;
// delete memory allocated for the previous head node
free(temp);
}
}
Program 1 :
class CountZeros
{
/* if 0 is present in arr[] then returns the index of FIRST occurrence
of 0 in arr[low..high], otherwise returns -1 */
int firstZero(int arr[], int low, int high)
{
if (high >= low)
{
// Check if mid element is first 0
int mid = low + (high - low) / 2;
if ((mid == 0 || arr[mid - 1] == 1) && arr[mid] == 0)
return mid;
if (arr[mid] == 1) // If mid element is not 0
return firstZero(arr, (mid + 1), high);
else // If mid element is 0, but not first 0
return firstZero(arr, low, (mid - 1));
}
return -1;
}
// A wrapper over recursive function firstZero()
int countZeroes(int arr[], int n)
{
// Find index of first zero in given array
int first = firstZero(arr, 0, n - 1);
// If 0 is not present at all, return 0
if (first == -1)
return 0;
return (n - first);
}
// Driver program to test above functions
public static void main(String[] args)
{
CountZeros count = new CountZeros();
int arr[] = {1, 1, 1, 0, 0, 0, 0, 0};
int n = arr.length;
System.out.println("Count of zeroes is " + count.countZeroes(arr, n));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.