cs301 GDB fall 2017

CS301 GDB Complete overview decision on you but we recommended link list

GDB Scenario: Suppose you are working as a developer in a software house. A task is given to you to build an application for a shopping mall to maintain the inventory of different products. Products are divided into different categories. The number of categories are fixed but products in each category can increase/decrease depend on introducing new products. When new product will arrive it will be added to its category, if product will already in any category then only its quantity will update. GDB Questions: From array, singly linked list and doubly linked list, which data structure you will prefer to use to build required application. Searching of product should be efficient and application should take minimum possible memory. Select data one or more structure(s) of your choice with solid reason to justify your selection. Instructions: A concise, coherent and to the point answer is preferred over lengthy comment having irrelevant details.  Answers, posted on regular Lesson's MDB or sent through email will NOT be considered in any case.

Advantages:  1. It is used to represent multiple data items of the same type by using the only single name. 2. It can be used to implement other data structures like linked lists, stacks, queues, trees, graphs etc. 3. 2D arrays are used to represent matrices. Disadvantages: 1. We must know in advance that how many elements are to be stored in the array. 2. The array is static structure. It means that array is of fixed size. The memory which is allocated to the array cannot be increased or reduced. 3. Since array is of fixed size, if we allocate more memory than requirement then the memory space will be wasted. And if we allocate less memory than the requirement, then it will create the problem. 4. The elements of array are stored in consecutive memory locations. So insertions and deletions are very difficult and time-consuming.

Advantage

1. Linked lists are a dynamic data structure, which can grow and be pruned, allocating and de-allocating memory while the program is running.
2. Insertion and deletion node operations are easily implemented in a linked list.
3. Dynamic data structures such as stacks and queues can be implemented using a linked list.
4. There is no need to define an initial size for a linked list.
5. Items can be added or removed from the middle of list.
6. Backtracking is possible in two way linked list.

Disadvantage

1. They use more memory than arrays because of the storage used by their pointers.
2. Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
3. Nodes are stored contiguously, greatly increasing the time periods required to access individual elements within the list, especially with a CPU cache.
4. Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backward and while doubly linked lists are somewhat easier to read, memory is consumed in allocating space for a back-pointer.

Advantages over singly linked list

• A DLL can be traversed in both forward and backward direction.
•  The delete operation in DLL is more efficient if pointer to the node to be deleted is given. In the singly linked list, to delete a node, 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 previous pointer.

disAdvantages link list

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