A data structure is a method for storing and organizing data in a virtual system. It is used to denote a particular way of organizing data for particular types of operation such as modification, navigation, and access of information.
There are numerous data structures ranging from arrays and lists to more complex structures such as trees, heaps and graphs.
Data structures help to:
- Manage and utilize large datasets
- Quickly search for particular data from a database
- Build clear hierarchical or relational connections between data points
- Simplify and speed up data processing
Each data structure has a task or situation it is most suited to solve.
*Widely used basic data structures: *
- Linked lists
- Hash tables
An algorithm for a particular task is a finite sequence of instructions, each of which has a clear meaning and can be performed with a finite amount of effort in a finite length of time.
Some common categories of algorithms are:
- Graph/tree traversing
- Dynamic programming
- Hashing and regex (string pattern matching)
When solving real-world coding problems, it is required that runtime and resource efficiency are achieved. Knowing the data structure and algorithm which best fits the current solution will increase program performance and reduce time required to make it.
Proper understanding of data structures and algorithms ensures well-optimized and efficient code.
The efficiency or performance (complexity) of an algorithm relates to the resources required by it, such as how quickly it will run (time complexity), or how much computer memory (space complexity) it will use.
The ability to formulate an efficient algorithm depends on being able to organize the data in an appropriate manner. It is for this reason coding some coding interviews ask for demonstration of comprehension of data structures and algorithms.
Primitive data structures and data types are native to the programming language. These include boolean, null, number, string, etc.
Non-primitive data structures are not defined by the programming language but rather by the programmer. These include linear data structures, static data structures, and dynamic data structures, like queue and linked lists.
- Queues & Stacks
- Linked List
- Hashtables / maps
Arrays are sequences of primitive data types, similar to a list. Each array has a fixed number of cells decided on its creation, and each cell has a corresponding numeric index used to select its data.
Stacks and queues differ from the exact definition of arrays in other programming languages by how objects are added or removed.
Queues are conceptually similar to stacks; both are sequential structures, but queues process elements in the order they were entered rather than the most recent element.
Queues are FIFO (first in, first out) while stacks are LIFO (last in, first out). As a result, queues can be thought of as a FIFO (First In, First Out) version of stacks. These are helpful as a buffer for requests, storing each request in the order it was received until it can be processed.
Linked lists are a data structure which, does not use physical placement of data in memory. This means that, rather than indexes or positions, linked lists use a referencing system: elements are stored in nodes that contain a pointer to the next node, repeating until all nodes are linked.
This system allows efficient insertion and removal of items without the need for reorganization.
Trees are another relation-based data structure, which specialize in representing hierarchical structures. Like a linked list, nodes contain both elements of data and pointers marking its relation to immediate nodes.
Each tree has a “root” node, off of which all other nodes branch. The root contains references to all elements directly below it, which are known as its “child nodes”. This continues, with each child node, branching off into more child nodes.
Nodes with linked child nodes are called internal nodes while those without child nodes are external nodes. A common type of tree is the “binary search tree” which is used to easily search stored data.
These search operations are highly efficient, as its search duration is dependent not on the number of nodes but on the number of levels down the tree.
Graphs are a relation-based data structure helpful for storing web-like relationships. Each node, or vertex, as they’re called in graphs, has a title (A, B, C, etc.), a value contained within, and a list of links (called edges) it has with other vertices.
The graph structure is invaluable in conveying relationship charts in textual form, anything from circuitry to train networks.
A hash table is a dictionary-like data structure, where keys are paired with values. Hash tables are great for rapid retrieval and modification of data, though the array and list-like objects above are better for storage. Still, especially with the explosive growth of data, hash tables have become nearly ubiquitous. For example, popular NoSQL databases used in the web such as MongoDB and Redis are distributed hash tables and key/value stores.