20

When programmers talk about "data structures", are they only talking about abstract data types like lists, trees, hashes, graphs, etc.?

Or does that term include any structure that holds data, such as composite types (class objects, structs, enums, etc.) and primitive types (boolean, int, char, etc.)?

I've only ever heard programmers use the term to reference complex data structures or abstract data types, however the Wikipedia article that provides a list of data structures includes both composite types and primitive types in the definition, which is not what I expected (even though it does make sense).

When looking around online I see other places that refer to the term "data structure" in the programming sense as only referring to abstract data types, such as this lecture from Stony Brook University's Department of Computer Science which states

A data structure is an actual implementation of a particular abstract data type.

or this wikibook on data structures, which uses the term in sentences like this:

Because data structures are higher-level abstractions, they present to us operations on groups of data, such as adding an item to a list, or looking up the highest-priority item in a queue

So why do I only ever hear programmers referring to complex data structures or abstract data types when they use the term "data structure"? Do programmers have a different definition for the term than the dictionary definition?

Peter Mortensen
  • 1,050
  • 2
  • 12
  • 14
Rachel
  • 23,979
  • 16
  • 91
  • 159
  • 1
    The term evolved over time. The CS crowd normally uses the term for generic types of structures that can hold multiple items of related data (linked lists, trees etc...) – Oded May 09 '12 at 13:45
  • 2
    isnt it just a terminology thing? a string is actually an array of chars, and it's a data structure which represents a sequence of individual charachters – Mithir May 09 '12 at 13:46
  • 4
    Isn't "data structure" a self-defined term? It's any structure for storing data! It's kind of hard to take the question seriously. – Michael K May 09 '12 at 14:12
  • @MichaelK That was the basis of my question :) If a data structure is a structure for storing data, than things like primitive data types are considered data structures, however I never hear primitive data types being referred to as "data structures" by programmers, so was wondering if programmers mean something different when they talk about data structures :) – Rachel May 09 '12 at 14:14
  • 1
    @Rachel So your question is actually whether primitive data types are data structures or not? `if programmers mean something different when they talk about data structures` is still polling for opinions though. – yannis May 09 '12 at 14:15
  • 2
    "Primitive" completely depends on scope. At the binary level there is no such thing as an int, for example. At an even lower level there aren't even bits - just electrical bias. Again, this is a self defining term - not a good question at all. – Michael K May 09 '12 at 14:17
  • [Wikipedia](http://en.wikipedia.org/wiki/Data_structure): "In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently." Whatever level of abstraction you are at, this definition applies. – Michael K May 09 '12 at 14:47
  • 1
    Related meta question: http://meta.programmers.stackexchange.com/q/3568/1130 – Rachel May 09 '12 at 15:04
  • @MichaelK I provided a link to primitive types as wikipedia defines them – Rachel May 09 '12 at 15:19
  • 1
    @Rachel Thank you Rachel, we actually have a good question now. I reopened, this question. – maple_shaft May 09 '12 at 16:30
  • Usage probably varies from language to language I'd imagine, but also context. In very high level interpreted language like JS, I would assume somebody meant either a custom object or array of objects with special interface methods or a generalized pattern for handling data a certain way like a linked list. In C I could see it meaning one thing when used in a conversation about how to write C vs. another in a conversation about how C gets compiled into machine language. – Erik Reppen May 09 '12 at 22:24

3 Answers3

21

The generic definition of "data structure" is anything that can hold your data in a structured way, so yes this would include composite types and primitive types in addition to abstract data types. For example, a string is a data structure as it can hold a sequence of characters in a structured way.

However, the term also has another meaning to programmers.

Since the term "data structures" is so broad, developers usually use a more specific term to identify what they are talking about, such as class or data object or primitive type, and the specific term used for most complex or abstract data types is "data structure"

This is why you hear "data structure" most frequently being used for abstract data types like Arrays, Lists, Trees and Hashtables, and not for things like primitive data types

Rachel
  • 23,979
  • 16
  • 91
  • 159
Alex
  • 3,228
  • 1
  • 22
  • 25
  • 4
    I think graphs are very common too but they are just rarely represented in standard libraries because they are very hard to build in a generic and efficient way. – Klaim May 09 '12 at 13:52
  • So when programmers talk about "data structures", they're usually talking about [abstract data types](http://en.wikipedia.org/wiki/List_of_data_structures#Abstract_data_types)? And although [primitive types](http://en.wikipedia.org/wiki/List_of_data_structures#Primitive_types) (such as int, bool, or char) and [composite types](http://en.wikipedia.org/wiki/List_of_data_structures#Composite_types) (like a class, struct, or enum) are still considered data structures by programmers, they are usually referred to by different terms? – Rachel May 09 '12 at 13:57
  • 1
    @Rachel technically a data structure could be a homebrewed implementation using pointers/classes ect too. I made some very ugly "data structures" similar to lists as part of a C++ homework assignment. We just don't call classes data structures as often because they're usually something more specific. – Ben Brocka May 09 '12 at 14:07
  • @BenBrocka Ahhh so "data structure" is a very broad term which does cover these other objects, however its typically better to be more specific when talking about data structures and to use terms like "primitive data type" or "data object" instead of "data structure". And the commonly used specific term for objects like `Lists`, `Trees`, `Graphs`, etc just happens to be "data structures" – Rachel May 09 '12 at 14:11
  • 1
    @Rachel yes, even though everything is a data structure (strictly speaking) the term 'data structure' usually refers to those abstract data types. I'd say the term 'data structure' from a developer's perspective refers to how he's storing the data. It could be a in memory list, a file in the disk or could be a custom data structure he implemented himself. – Alex May 09 '12 at 14:13
  • @Alex Perhaps you can update your answer to include that? That "data structure" is both a very broad generic term, and a more specific term used to define abstract data types, and that frequently when programmers talk about "data structures", they are referring to the more specific term? – Rachel May 09 '12 at 14:31
  • @Rachel It's sort of what I said but I'll try to change the text to be more specific. No problem... – Alex May 09 '12 at 14:38
  • @Alex Do you mind if I make a few edits to your answer to clarify it so I can mark it as the accepted answer? – Rachel May 09 '12 at 15:07
  • @Rachel absolutely not, go ahead. – Alex May 09 '12 at 15:29
  • @Alex Thanks :) Feel free to edit it further if you think it needs it – Rachel May 09 '12 at 15:35
  • @Rachel see? you knew the answer already, just needed some hint ;) – Alex May 09 '12 at 15:43
  • @Alex Actually you guys did provide me with the answer I was looking for :) I was thinking that "data structures" had a different definition to programmers than what wikipedia said, but it turns out it doesn't have a different definition, but it does have another meaning :) – Rachel May 09 '12 at 15:45
  • @Rachel the interesting thing is: that's the true answer to your question but it's hard to explain why exactly that is. The term 'data structure' is very easy to define and explain but somehow it got used in a more strict way and somehow there is a consensus about it (even for programmers from different countries). – Alex May 09 '12 at 16:43
  • This Q/A missed the point all together. An ADT is implemented by a data structure. For example a Queue is implemented as a linked list. – nativist.bill.cutting Oct 21 '13 at 15:13
  • @Alex I think `String is a data structure` is a misleading statement. String is a data type which represents a sequence of character. You can use many different data structures to implement string. The most common implementations of string uses an array. You can also used linked list or other data structures to implement string. – Quazi Irfan Feb 11 '18 at 05:48
  • @QuaziIrfan you might be right but it's a pretty gray area there. One could say to implement a linked listed data structure I can use an array. But this doesn't necessarily mean linked list is a data type, or does it? How do we separate a data type from a data structure? – Alex Feb 15 '18 at 23:45
  • @Alex I am no expert but here is my take. Comparing Data structure and Data type is like comparing [apples and oranges](https://en.wikipedia.org/wiki/Apples_and_oranges). Data types tell you what are the possible values of that type, and what operations are possible on that type. But you need a data structure to store the value on the memory. You can use any data types, but depending on the use case(performance, ease of use etc), you might chose one data structure over another. – Quazi Irfan Feb 16 '18 at 07:59
  • @Alex For example it makes sense to allocate 4 adjacent bytes for a primitive integer data type since 4 adjacent bytes are usually available is most use cases. But, if you need an integer type that needs to store super large numbers you would need better data structure to be able to run efficient algorithms on them. It turns out, simple structure like adjacent memory locations(or array data structure) are just good enough. The max range of current BigInteger implementation in Java in 2^Integer.MAX_VALUE. But what if you need to store even larger number and you need it to be performent as well? – Quazi Irfan Feb 16 '18 at 07:59
  • @Alex Maybe in those situation, arrays are not good enough anymore. Now you need more advanced data structure, i.e. probably distributed data structure, i.e. could be linked list that points to large arrays to different machines. – Quazi Irfan Feb 16 '18 at 08:00
  • @Alex Note that, among all these changes in the underlying data structure, the integer data type has remained the same(i.e. the possible values, and possible operations allowed on those values). But by implementing integer data type with different data structure you get different capabilities. You need data structure since you need a structure to represent the possible values the data type can represent in the memory. Hopefully, now you can see why you can not compare data structure and data types. – Quazi Irfan Feb 16 '18 at 08:06
5

The term refers to both, though things like ints and booleans are typically considered primitive data types (or primitive data structures). The term itself simply referes to anything that stores data in a specific way. Certainly int meets this definition just as well as something like a Hash table, only it's simpler.

Typically, when people use data structure, they refer to more complex data structures, and not the simpler ones but both meet the definition.

Oleksi
  • 11,874
  • 2
  • 53
  • 54
  • 2
    I don't think I've ever heard someone refer to an `int` as a "data structure". – Qwertie May 09 '12 at 16:12
  • 2
    @Qwertie me neither, but that's still what it is. It's called a "data type" more often, but that pretty much means the same thing as "data structure" – Oleksi May 09 '12 at 16:14
0

The simplest and very basic definition, which I have ever heard of data structures, is storing data into the memory in such a way that basic operations like insert, update, delete etc can be performed in an efficient way in terms of time and memory.

So, a data type tells the type of data we have stored into it. It can be integer, decimal, character , string or an object. This can be composite types or primitive types in addition to abstract data types.

But, we use data structures when we want to store any complex data in the memory. This is the reason why we hear only about data types like Arrays, Lists, Trees and Hashtables, and not for things like primitive data types

Nishant sethi
  • 109
  • 4