recategorized
2,043 views
0 votes
0 votes

Consider an implementation of unsorted single linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of the linked list). Given the representation, which of the following operation can not be implemented in $O(1)$ time ?

  1. Insertion at the front of the linked list.
  2. Insertion at the end of the linked list.
  3. Deletion of the front node of the linked list.
  4. Deletion of the last node of the linked list.
recategorized

1 Answer

Best answer
2 votes
2 votes

A)Insertion at the front of the linked list.

new_node->next=head;
head=new_node;

$\Theta \left ( 1 \right )$

B) Insertion at the end of the linked list.

Tail->next=new_node;
new_node->next=NULL;

 $\Theta \left ( 1 \right )$

C) Deletion of the front node of the linked list.

Next_node=Head;
Head=Next_node->next;
free(Next_node);

$\Theta \left ( 1 \right )$

D)Deletion of the last node of linked list

Here although we have tail pointer but it will be of no use because there is no previous pointer (as it is single linked list).we need to have second last pointer so that we make it the last pointer and can free the last pointer i.e deleting the last node.So we need to traverse the whole linked list making it $\Theta \left ( n \right )$.

struct node *p,*prev;
p=head;
while(p)
{
    prev=p;
    p=p->next;
}
prev->next=NULL;
free(p);

ANSWER D)

selected by

Related questions

0 votes
0 votes
2 answers
1
makhdoom ghaya asked Sep 26, 2016
5,011 views
Given the following prefix expression :$^{*} + 3 + 3 ↑ 3 + 3 3 3$What is the value of the prefix expression ?$2178$ $2199$$2205$ $2232$
0 votes
0 votes
1 answer
3
makhdoom ghaya asked Sep 26, 2016
8,925 views
The runtime for traversing all the nodes of a binary search tree with $n$ nodes and printing them in an order is$O(\lg n)$$O(n \lg n)$ $O(n)$$O(n^{2})$
2 votes
2 votes
1 answer
4
makhdoom ghaya asked Sep 28, 2016
2,795 views
In Data mining, ______ is a method of incremental conceptual clustering.STRINGCOBWEBCORBAOLAD