A data structure is a concept from computer science that refers to a particular method of collecting and organizing information. All data structures use information about where a given piece of data is located in the memory of a computer in order to access that data and connect it to other pieces of data. Data structures establish one of many different sorts of relationships between individual pieces of information. Different types of data structure are more efficient for different purposes, and the difficulty of coding varies widely between types of data structure.
Arrays are among the simplest data structures but are nonetheless very powerful tools for organizing information. In an array, elements are assigned sequential memory addresses, allowing the memory address of any item in the array to be determined very rapidly using simple mathematical computations, a key advantage. Arrays can be conceived of as existing in any number of dimensions. A one-dimensional array might be conceptualized as a list, a two-dimensional array as a table, and a three-dimensional array as a cube of individual cells. Arrays of more than three dimensions can exist as well.
Linked lists are another simple but very important type of data structure. In a linked list, each node consists of a variable containing both actual data and information identifying the next element in the list. A linked list can thus be stepped through so long as the address of the first node is known. This type of data structure is versatile because it lends itself to dynamic growth, as new nodes can easily be assigned at any time. The addition of a variable containing the location of the previous node in the list allows this type of data structure to be traversed in either direction.
Trees order nodes hierarchically, beginning with a root node, and descending through multiple layers of nodes until all necessary data has been accommodated within the structure. Typically, the elements within a tree are sorted in some fashion. Trees may implement sorting and can potentially provide much more rapid access to stored data because of this, as each branching eliminates whole swathes of information from consideration that would need to be sorted through in a linked list.
Hash tables are used to determine a memory address in which a given piece of data is to be stored by using an equation to transform that data into a memory address. They can be a very efficient structure for storing and retrieving data from an array.
All data structures are designed to decrease the number of instructions that a computer must execute in order to locate a particular piece of information. Different types of data lend themselves to different types of data structure, but most modern programming languages offer support for a wide variety of data structure, or provide the tools to allow programmers to code their own data structures.
