Data Structures

Question 1

8 Data Structure types

Answer 1

sets, 
bags (or multisets), 
sequential lists, 
ordered lists (with ordering from a “less than” operator), 
stacks, 
queues (priority queues), 
tables, and 
graphs.

Question 2

Linked List

Answer 2

A data structure in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.

Advantages over arrays

1) Dynamic size
2) Ease of insertion/deletion

Drawbacks:

1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists efficiently with its default implementation. Read about it here.
2) Extra memory space for a pointer is required with each element of the list.
3) Not cache-friendly. Since array elements are contiguous locations, there is the locality of reference which is not there in the case of linked lists.

Question 3

Doubly Linked List (DLL)

Answer 3

It contains an extra pointer, typically called the previous pointer, together with the next pointer and data which are there in the singly linked list.

Advantages over singly linked list
1) A DLL can be traversed in both forward and backward directions.
2) The delete operation in DLL is more efficient if the pointer to the node to be deleted is given.
3) We can quickly insert a new node before a given node.
In a singly linked list, to delete a node, the pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using the previous pointer.

Disadvantages over singly linked list

1) Every node of DLL Requires extra space for a previous pointer. It is possible to implement DLL with a single pointer though (XOR Linked List).
2) All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with the next pointers. For example in the following functions for insertions at different positions, we need 1 or 2 extra steps to set the previous pointer.

Question 4

Circular Linked List

Answer 4

A linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or a doubly circular linked list.

Advantages of Circular Linked Lists:
1) Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.

2) Useful for implementation of a queue. Unlike this implementation, we don’t need to maintain two pointers for the front and rear if we use a circular linked list. We can maintain a pointer to the last inserted node and the front can always be obtained as next of last.
3) Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.
4) Circular Doubly Linked Lists are used for the implementation of advanced data structures like Fibonacci Heap.
https: //www.youtube.com/watch?v=ANbJdUBIVRU