Linked List - Concepts & Terminologies

What are the drawbacks of using sequential storage to represent stacks and queues?

One major drawback is that a fixed amount of storage remains allocated to the stack or queue even when the data structure is actually using a smaller amount or possibly no storage at all.

Further , no more than that fixed amount of storage may be allocated., thus introducing the possibility of overflow.

Define Linked List.

Linked List is an ordered collection of nodes and each node has two parts: data (information) and pointer to the next node. The pointer to the next node is known as internal pointer and the pointer used to access nodes in the linked list are called external pointer.

"A Linked List is a dynamic data structure". Justify.

Unlike an array, a list does not come with a pre-allocated set of storage locations into which elements can be placed. The number of nodes on a list may vary dramatically as elements are inserted and removed.

New nodes are created by acquiring memory using functions like malloc() and memory locations associated with deleted nodes are released using function free().

What are the advantages of Stack implementation using Linked List?

Stack can grow and shrink to any size.

No allocation of memory in advance , so efficient memory utilization is possible..

Acquiring and releasing nodes for push () and pop() operation allows flexible access to memory.

What are the disadvantages of representing a stack or queue by a linked list?

A node in a linked list occupies more storage than a corresponding element in an array, as each node has two parts : information and pointer.

In general, linked list requires twice memory as compared to array due to above mentioned reason.

Time required to add and delete node is more than array.

What are the advantages of representing a stack or queue by a linked list?

No fixed amount of storage is allocated. Dynamic allocation and deallocation makes implementation memory efficient.

What are the advantages of Linked List over Array?

No memory allocation in advance , hence overflow or underutilization of memory is not possible.

Insertion and Deletion from any position in the linked list is fast and efficient, while insertion and deletion of elements causes shifting of elements which is expensive.

What are the disadvantages of Linked List over Array?

It is quick and easy to access nth element from array using subscript. Which means array supports quick and easy to access any element randomly. But, to access nth element from Linked List requires n memory accesses sequentially, hence it is an expensive operation.

Can we implement Linked List using Array?

Yes, Linked List can be implemented using array. Each element in array will have two parts information and next (index of next node).

For example,

struct node

{

int info;

int next;

} List[MAXSZ];

What are the limitations of implementing Linked List using Array?

Fixed memory locations of array puts restriction of number nodes in the linked list.

If the number of nodes are less than the size of the array, it causes wastage of memory.

What is dangling pointer?

When a pointer is holding address of memory which is recently deallocated, it is known as dangling pointer.

Let's see example below ,

int *ptr1 = (struct node *) malloc(sizeof(struct node)); // pointer ptr1 has allocated memory

int *ptr2 = ptr1; // Now pointer ptr2 also holds address of same memory location

free(ptr1); // ptr2 remains pointing to memory which is already deallocated using ptr1

What are the limitations of dynamic implementation of Linked List?

Memory allocation and deallocation requires system calls such as malloc() and free, which takes time for execution.

Sequential traversing is the only way to access elements. (Address computation like in array to access ith element a[i] is not possible).

What is the advantage of Circular Singly Linked List over Linear Linked List?

External pointer can able to move to first node from last node in the list. Hence, adding and removing elements from head end and tail end of linked list is convenient.

Implementation of Queue is more convenient than Linear Linked List.

What are the drawbacks of Circular Singly Linked List?

It is not possible to traverse backward in the list.

Define Doubly Linked List.

Doubly Linked List is a collection of nodes with three parts: pointer to previous node, information, and pointer to the next node.

What are the Disadvantages of Doubly Linked List?

Not space efficient as it reuires two pointer , one for previous node and one for next node.

What are the advantages of Circular Doubly Linked List?

Want to read more?

Subscribe to questionbankos.com to keep reading this exclusive post.

Subscribe Now