Register

GO Classes DPP | GATE CS | Data Structures | Array vs Linked List

447 views
7 7 votes

A sequence of $n$ elements is implemented in two ways:

  1. As a normal array with contiguous memory and no extra empty slot.
     
  2. As a singly linked list with only a $\texttt{head}$ pointer and no $\texttt{tail}$ pointer.
     

Which of the following statements are correct in the worst case?

  1. In an array, $\texttt{get_at(i)}$ takes $O(1)$ time.
     
  2. In an array, $\texttt{insert_first(x)}$ takes $O(1)$ time.
     
  3. In a singly linked list, $\texttt{get_at(i)}$ takes $O(1)$ time.
     
  4. In a singly linked list, $\texttt{insert_first(x)}$ takes $O(1)$ time.
     
  5. In a singly linked list, $\texttt{delete_first()}$ takes $O(1)$ time.
     
  6. In a singly linked list with only $\texttt{head}$, $\texttt{insert_last(x)}$ takes $O(1)$ time

1 Answer

2 2 votes
Array access by index is direct, so $\texttt{get_at(i)}$ is $O(1)$.

But inserting at the beginning of an array needs shifting, so it is $O(n)$.

In a singly linked list, accessing the $i$-th node needs traversal, so it is $O(n)$.

Inserting or deleting the first node only changes the $\texttt{head}$ pointer, so both are $O(1)$

Without a $\texttt{tail}$ pointer, inserting at the end needs traversal, so it is $O(n)$.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

6 6 votes
1 1 answer
236
236 views
GO Classes asked Jul 3
236 views
GO Classes DPP | GATE CS | Data Structures | Linked List Complexity
For a singly linked list storing only the head pointer, which of the following operations can be done in worst-case $O(1)$ time?Access the $i$-th element Modify the $i$-t...
5 5 votes
2 2 answers
324
324 views
GO Classes asked Jul 3
324 views
GO Classes DPP | GATE CS | Data Structures | Linked List Traverse
Consider the following singly linked list:$\texttt{12 - 18 - 25 - 31 - 44 - 57 - NULL}$Now, consider the following function:int Size(struct Node *list) { int count = 0; w...
5 5 votes
2 2 answers
291
291 views
GO Classes asked Jul 3
291 views
GO Classes DPP | GATE CS | Data Structures | Insertion in Linked List
A singly linked list is:$\texttt{5 - 8 - 20 - NULL}$A new node $\texttt{​newP}$ contains data $9$. Pointer $\texttt{​prevP}$ points to the node containing $8$.The inserti...
4 4 votes
2 2 answers
239
239 views
GO Classes asked Jul 3
239 views
GO Classes DPP | GATE CS | Data Structures | Delete by Value
A singly linked list is:$\texttt{5 - 8 - 20 - 9 - 20 - 7 - NULL}$The function $\texttt{deleteByValue(L, val)}$ removes only the first node whose data is equal to $\texttt...