GATE CS Linked Lists questions

Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head. struct node{ int elt; struct node *next; }; int getListSize (struct node *head) { if( E1 ) return 1; return E2; } Which one of the following options gives the correct replacements for the expressions …

Let $\mathrm{LIST}$ be a datatype for an implementation of linked list defined as follows: typedef struct list { int data; struct list *next; } LIST; Suppose a program has created two linked lists, $L1$ and $L2$, whose contents are given in the figure below (code for creating $L1$ and $L2$ is not provided here). $L1$ contains $9$ nodes, and …

Let $\textsf{SLLdel}$ be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let $\textsf{DLLdel}$ be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list. Let $n$ denote the number of nodes in each …

Consider the problem of reversing a singly linked list. To take an example, given the linked list below, the reversed linked list should look like Which one of the following statements is $\text{TRUE}$ about the time complexity of algorithms that solve the above problem in $O(1)$ space?

What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order?

Consider the C code fragment given below. typedef struct node { int data; node* next; } node; void join(node* m, node* n) { node* p = n; while(p->next != NULL) { p = p->next; } p->next = m; } Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will

$N$ items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: $\Theta \left(N\right)$ delete, …

The following C function takes a singly-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank. typedef struct node { int value; struct node *next; } Node; Node *move_to-front(Node *head) { Node *p, *q; if ((head == NULL) || (head -> next == …

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers $1, 2, 3, 4, 5, 6, 7$ in the given order. What will be the contents of the list after function completes execution? struct node { int value; struct node *next; }; void …

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among $\text{union, intersection, membership, cardinality}$ will be the slowest?

A circularly linked list is used to represent a Queue. A single variable $p$ is used to access the Queue. To which node should $p$ point such that both the operations $\text{enQueue}$ and $\text{deQueue}$ can be performed in constant time?

Consider the function $f$ defined below. struct item { int data; struct item * next; }; int f(struct item *p) { return ((p == NULL) || (p->next == NULL)|| ((p->data <= p ->next -> data) && f(p->next))); } For a given linked list $p$, the function $f$ returns $1$ if and only if

In the worst case, the number of comparisons needed to search a single linked list of length $n$ for a given element is

The concatenation of two lists is to be performed on $O(1)$ time. Which of the following implementations of a list should be used?

Which of the following statements is true? As the number of entries in a hash table increases, the number of collisions increases. Recursive programs are efficient The worst case complexity for Quicksort is $O(n^2)$ Binary search using a linear linked list is efficient

Linked lists are not suitable data structures for which one of the following problems?

In a circular linked list organization, insertion of a record involves modification of