Question

i need an conclusion for my research thesis paper and my research paper covered these areas(why do we need data structures? What is the relationship between data structure and algorithm? What data structures have we learned? What are their respective logical and physical / storage structures? What are their advantages and disadvantages? In which cases do they apply to (combined with time complexity analysis)? Please analyze the learned data structure one by one. At least one application example combining data structure and algorithm should be given)

My question please write an conclusion for my thesis paper.

Answer 1

1. Why do we need data structures?

Data structures are used as a framework for organizing and storing information in virtual memory forms. In computing, RAM and virtual memory, such as the Cloud or other shared storage systems, store large quantities of data rapidly and efficiently. However, there is a twofold dilemma: first, how can it be stored efficiently, and second, how will we be able to retrieve it over time if it’s just stored away in cyberspace? Data structures are the solution to these dilemmas. Data structures organize and prioritize information into datasets and databases that can be compressed efficiently to save storage space. These organizational structures are also structured logically so that retrieving information from them is simple and straightforward, making the data usable once more. Use of appropriate data structure enables a computer system to perform its task more efficiently, by influencing the ability of computer to store and retrieve data from any location in its memory.

2. Relationship between data structure and algorithm

Data structures are the way to arrange data so that some kind of operations on them get facilitated. Algorithm is the way to do something with the data in the most efficient way, so as most answers here indicate - Data structures help algorithms achieve their goals in the most efficient way.. Algorithms are like verbs and Data Structures are like nouns. An Algorithm is just a method of doing something on a computer, while a Data Structure is a layout for memory that represents some sort of data

3. Data structures have we learned (Commonly used Data Structures)

· Arrays

· Stacks

· Queues

· Linked Lists

Arrays

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together.

Advantages of Arrays

1. Arrays represent multiple data items of the same type using a single name.

2. In arrays, the elements can be accessed randomly by using the index number.

3. Arrays allocate memory in contiguous memory locations for all its elements. Hence there is no chance of extra memory being allocated in case of arrays. This avoids memory overflow or shortage of memory in arrays.

4. Using arrays, other data structures like linked lists, stacks, queues, trees, graphs etc can be implemented.

5. Two-dimensional arrays are used to represent matrices.

Disadvantages of Arrays

1. The number of elements to be stored in an array should be known in advance.

2. An array is a static structure (which means the array is of fixed size). Once declared the size of the array cannot be modified. The memory which is allocated to it cannot be increased or decreased.

3. Insertion and deletion are quite difficult in an array as the elements are stored in consecutive memory locations and the shifting operation is costly.

4. Allocating more memory than the requirement leads to wastage of memory space and less allocation of memory also leads to a problem.

Applications of Arrays

1. Arrays can be used for sorting data elements. Different sorting techniques like Bubble sort, Insertion sort, Selection sort etc use arrays to store and sort elements easily.

2. Arrays can be used for performing matrix operations. Many databases, small and large, consist of one-dimensional and two-dimensional arrays whose elements are records.

3. Arrays can be used for CPU scheduling.

Stack

Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

Every time an element is added, it goes on the top of the stack and the only element that can be removed is the element that is at the top of the stack, just like a pile of objects.

Push() à to add elements

Pop() à to remove elements

ADVANTAGES

· Easy to started

· Less Hardware Requirement

· Cross- Platform

DIS ADVANTAGES

· not flexible

· Lack of scalability

· Unable to Copy & Paste

Applications of Stack

1. reverse a word. You push a given word to stack - letter by letter - and then pop letters from the stack.

2. Parsing

3. Expression Conversion (Infix to Postfix, Postfix to Prefix etc)

Queue

A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

Advantage

· Provide first-in first-out access of data

Disadvantages

· Slow access to remaining elements other than first elements

· Free space is there, when we delete some elements from front

Applications of Queue

1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.

2. In real life scenario, Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is free.

3. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive i.e First come first served.

Linked list

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array. Following are the important terms to understand the concept of Linked List.

· Link − Each link of a linked list can store a data called an element.

· Next − Each link of a linked list contains a link to the next link called Next.

· LinkedList − A Linked List contains the connection link to the first link called First.

Following are the basic operations supported by a list.

· Insertion − Adds an element at the beginning of the list.

· Deletion − Deletes an element at the beginning of the list.

· Display − Displays the complete list.

· Search − Searches an element using the given key.

· Delete − Deletes an element using the given key.

Advantages of Linked List

1. Linked list is a dynamic data structure so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give initial size of linked list.

2. Insertion and deletion of nodes are really easier. Unlike array here we don’t have to shift elements after insertion or deletion of an element. In linked list we just have to update the address present in next pointer of a node.

3. As size of linked list can increase or decrease at run time so there is no memory wastage.

4. Data structures such as stack and queues can be easily implemented using linked list.

Disadvantage

1. More memory is required to store elements in linked list as compared to array. Because in linked list each node contains a pointer and it requires extra memory for itself.

2. Elements or nodes traversal is difficult in linked list. We cannot randomly access any element as we do in array by index.

3. In linked list reverse traversing is really difficult.

Applications of linked list in computer science –

· Implementation of stacks and queues

· Implementation of graphs : Adjacency list representation of graphs is most popular which is uses linked list to store adjacent vertices.

· Dynamic memory allocation : We use linked list of free blocks.

· Maintaining directory of names

· Performing arithmetic operations on long integers

· Manipulation of polynomials by storing constants in the node of linked list

· representing sparse matrices