Write functions Insert and Remove which add and remove nodes from ordered single linked list based on the Node value

Q:

Write functions Insert and Remove which add and remove nodes from ordered single linked list based on the Node value

A:

public Node Insert(Node head, int value)
{
if (head == null || value < head.value)
return new Node(value, head);
else
{
head.next = Insert(head.next, value);
return head;
}
}

Write a function which will test whether or not there is a cycle in a single linked list

Q:

Write a function which will test whether or not there is a cycle in a single linked list

A:

public bool hasLoop(Node head)
{
Node first = head;
Node second = head;
while (first && second &&
first.Next && second.Next &&
second.Next.Next)
{
first = first.Next;
second = second.Next.Next;
if (first == second)
{
// Found loop
return true;
}
}
return false;
}

Write a function which will print values from the single linked list in the reverse order in O(n) time. No changes to the list can be made and no additional data structures can be used

Q:

Write a function which will print values from the single linked list in the reverse order in O(n) time. No changes to the list can be made and no additional data structures can be used”

A:

public void PrintInReverseOrder (Node head)
{
if (head != null)
{
PrintInReverseOrder(head.next);
Console.WriteLine(head.value);
};
}

Compute the sum of all the values in the nodes of a single linked list

Q:

Compute the sum of all the values in the nodes of a single linked list


A:

public int getSum(Node head)
{


if (head == null) return 0;
else
return getSum(head.next) + head.value;

}

Calculate length of the linked list

Q:

Calculate length of the linked list

A:

public int getLength(Node head)
{
if (head == null)
return 0;
else
return length(head.next) + 1;

}

Reverse a Singly Linked List

Q:
Reverse a Singly Linked List

A:
public Node Reverse(Node head)
{
Node next;
Node current;
current = head;
Node Result = null;
while (current != null)
{
next = current.next;
current.next = result;
result = current;
current = next;
}
return (result);
}

What are the advantages and disadvantages of linked list structure vs. arrays?

Q:

What are the advantages and disadvantages of linked list structure vs. arrays?

A:

Linked lists allow only sequential access to elements O(n) while arrays allow random access O(1). Linked lists requires an extra storage for references, which often makes them impractical for lists of small data items such as characters or Boolean values. From the over side, size of array is restricted to declaration. Insertion/Deletion of values in arrays are very expensive comparing to linked list and requires memory reallocation. Elements can be inserted into linked lists indefinitely, while an array will eventually.

What is the difference between array and linked list?

Q:
What is the difference between array and linked list?

A:

The main difference between the linked list and the array is that while the array is a static data structure (with fix number of elements), the linked list - dynamic data structure. In terms of complexity, the linked list is usually more efficient as to the space it uses, however, algorithms for linked lists are usually more complicated that those of the array.

A rectangular plate with length 8 inches

Q:

A rectangular plate with length 8 inches, breadth 11 inches and thickness 2 inches is available. What is the length of the circular rod with diameter 8 inches and equal to the volume of the rectangular plate?

A:

3.5 inches
Explanation: Volume of the circular rod (cylinder) = Volume of the rectangular plate (22/7)*4*4*h = 8*11*2, h = 7/2 = 3.5.

Three cards are drawn

Q:

Three cards are drawn at random from an ordinary pack of cards. Find the probability that they will consist of a king, a queen and an ace.

A:

64/2210

Divide 45 into four parts

Q:

Divide 45 into four parts such that when 2 is added to the first part, 2 is subtracted from the second part, 2 is multiplied by the third part and the fourth part is divided by two, all result in the same number.

A:

8, 12, 5, 20
Explanation: a + b + c + d =45; a+2 = b-2 = 2c = d/2; a=b-4; c = (b-2)/2; d =2(b-2); b-4 + b + (b-2)/2 + 2(b-2) = 45;.

Reverse a Linked-List

Q:

Reverse a Linked-list. Write code in C.

A:

Recursive solution:

Node * reverse( Node * ptr , Node * previous)
{
Node * temp;
if(ptr->next == NULL) {
ptr->next = previous;
return ptr;
} else {
temp = reverse(ptr->next, ptr);
ptr->next = previous;
return temp;
}
}
reversedHead = reverse(head, NULL);

Non-recursive solution:

Node * reverse( Node * ptr )
{
Node * temp;
Node * previous = NULL;
while(ptr != NULL) {
temp = ptr->next;
ptr->next = previous;
previous = ptr;
ptr = temp;
}
return previous;
}

Singly Linked List – Delete Node

Q:

You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C.

A:

void deleteNode( Node * node )
{
Node * temp = node->next;
node->data = node->next->data;
node->next = temp->next;
free(temp);
}

DeleteList()

Q:

Write a function DeleteList() that takes a list, deallocates all of its memory and sets its
head pointer to NULL (the empty list).

A:

Delete the whole list and set the head pointer to NULL. There is a slight complication
inside the loop, since we need extract the .next pointer before we delete the node, since
after the delete it will be technically unavailable.
void DeleteList(struct node** headRef) {
struct node* current = *headRef; // deref headRef to get the real head
struct node* next;
while (current != NULL) {
next = current->next; // note the next pointer
free(current); // delete the node
current = next; // advance to the next node
}
*headRef = NULL; // Again, deref headRef to affect the real head back
// in the caller.
}

Count()

Q:

Write a Count() function that counts the number of times a given int occurs in a list.

A:
int Count(struct node* head, int searchFor) {
struct node* current = head;
int count = 0;
while (current != NULL) {
if (current->data == searchFor) count++;
current = current->next;
}
return count;
}
Alternately, the iteration may be coded with a for loop instead of a while...
int Count2(struct node* head, int searchFor) {
struct node* current;
int count = 0;
for (current = head; current != NULL; current = current->next) {
if (current->data == searchFor) count++;
}
return count;
}