J. Hunter (1998) states that the use of data structures and algorithms is the fundamentals used by programmers to store and manipulate data. He has also stated that though knowledge of every part of software engineering is not compulsory, it is important to understand that the subject of data structures and algorithms is concerned with the coding phase.
According to Robert Lafore (2008), data structure is an arrangement of data in a computer's memory and Algorithms manipulate the data in these structures in various ways.
According to the site under Data-structures-and-algorithms.psexam.com, Data structure is a way of storing and organizing data in a computer's memory or in a disk to be used efficiently. Data structures enable a programmer to mentally structure large amounts of data into manageable relationships.
All the above definitions tell us that Data structures are designed to arrange data in the computer's memory location to manipulate when necessary to achieve maximum performance in computer applications.
Data structures will enable to do more or could be used less. For example, carry out fast searching or sorting of data or in a limited form.
Some common data structures are arrays, linked lists, queues, stacks, binary trees and hash files. But there are data structures that can be thought of as Abstract data types as well, the given examples above can be considered as ADTs except arrays. All most all data structures have both advantages and disadvantages.
When a data structure provides operations, we can call the data structure an abstract data type (ADT).
Algorithms are used to manipulate the data contained in these data structures as in searching and sorting. Many algorithms apply directly to a specific data structures. To work with certain data structures it is required to know how to insert new data, search or delete a specified item.
Algorithms are commonly useful for:
Searching for a particular data item (or record).
Sorting the data. There are many ways to sort data. Simple sorting, Advanced sorting
Iterating through all the items in a data structure. (Visiting each item in turn so as to display it or perform some other action on these items)
Characteristics of Data Structures
Data Structure
Advantages
Disadvantages
Array
Quick inserts
Fast access if index known
Slow search
Slow deletes
Fixed size
Ordered Array
Faster search than unsorted array
Slow inserts
Slow deletes
Fixed size
Stack
Last-in, first-out access
Slow access to other items
Queue
First-in, first-out access
Slow access to other items
Linked List
Quick inserts
Quick deletes
Slow search
Binary Tree
Quick search
Quick inserts
Quick deletes
(If the tree remains balanced)
Deletion algorithm is complex
Red-Black Tree
Quick search
Quick inserts
Quick deletes
(Tree always remains balanced)
Complex to implement
2-3-4 Tree
Quick search
Quick inserts
Quick deletes
(Tree always remains balanced)
(Similar trees good for disk storage)
Complex to implement
Hash Table
Very fast access if key is known
Quick inserts
Slow deletes
Access slow if key is not known
Inefficient memory usage
Heap
Quick inserts
Quick deletes
Access to largest item
Slow access to other items
Graph
Best models real-world situations
Some algorithms are slow and very complex
NOTE: The data structures shown above (with the exception of the array) can be thought of as Abstract Data Types (ADTs).
Table 1.1
Source Author Jeff Hunter
Abstract Data Types
According to J. Hunter (1998), An Abstract Data Type (ADT) is a way of looking at a data structure on what it does and not how it does its job. Examples of ADT are stacks and queues. It is important to understand that both stacks and queues can be implemented using an array. It is also possible to implement stacks and queues using a linked list. This demonstrates the "abstract" nature of stacks and queues: how they can be considered separately from their implementation.
According to Nell Dale et al (1996), an abstract data type is a set of operations that are defined in a certain level without getting any limitations from operational details.
To describe the term Abstract Data Type better, we could break the term into "data type" and "abstract".
Data type - is an item with certain characteristics and the permissible operations and what operations can be performed on it.
Abstract - The word abstract in this context stands for "considered apart from the detailed specifications or implementation".
An Abstract Data Type is a "description" of the data and a list of operations that can be carried out on that data and instructions on how to use these operations. What is excluded is the details of how the methods carry out their tasks. For example an end user should be told what methods to call, how to call them, and the results that should be expected, but not HOW they work.
Further extension of the meaning of the ADT when applying it to data structures such as a stack and queue - In Java, as with any class, it means the data and the data and the operations that can be performed on it. Therefore, even the basics of how the data is stored should be invisible to the user. Users not only should not know how the methods work, they should also not know what structures are being used to store the data.
Example for the stack class, the end user knows that push() and pop() (among other similar methods) are available and how they work. The user doesn't and shouldn't have to know how push() and pop() work, or whether data is stored in an array, a linked list, or some other data structure like a tree.
Abstract Data Type (ADT) makes it easy to specify an algorithm if the operations needed could be indicated without having to think at the same time, about how the operations are performed. Since there are usually many ways to execute an ADT, it might be useful to write an algorithm that can be used with any of the possible implementations. Well-known ADTs, like the Stack ADT, are often implemented for it to be written once and used by many programmers.
The operations on ADTs provide a common high-level language for specifying and talking about algorithms. For ADTs, we often differentiate the code that uses the ADT, called the client code, from the code that implements the ADT, called provider code as it provides a standard set of services. One of the basic goals of an ADT is to separate the interests of the provider, who writes the code that implements the ADT, and the client, who uses the ADT. The provider only has to worry about whether the implementation is correct-according to the specification of the ADT-and not how it will be used. Otherwise, the client thinks that the implementation of the ADT is correct and doesn't worry about the details.
