Why is behavior included in the definition of a data structure?

Question

When reading about ADT's and data structures it is common that the ADT Stack is implemented in at least two ways. Either based on an Array or Linked List. From these examples I tend to think that the way in which the data is organised determines the efficiency of the behaviors that work on that data. So if someone was to ask me what a data structure is, I would have to say organised data or structured data.

Goodrich and Tamassia: "A data structure is a systematic way to organise and access data"

Wiki: "a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data"

A data structure to me seems like a particular way the organise the data to enable efficient behaviors. Why is it necessary to include access to the data in the definition of a data structure?

Answer 1

You have to make a distinction between abstract data structures and "data structure".

An abstract data structure (for instance the stack) is usually understood as the description of a collection of operations, and the semantic expected from those operations. It is only a specification, an interface.

A data structure (for instance a doubly-linked list) is indeed a way to organize data in memory, usually presented together with some operations on it. A data structure is thus usually given as an implementation of some ADT, but I would not say that this is necessary.

That being said, this distinction is mostly useful when learning about algorithms, as there is no theory relying on those notions. Definitions will vary depending on the teacher or the particular book you are looking at. It is useful to make this distinction because you can imagine taking any ADT and realizing it with any data structure (so I can try to implement a stack using a binary tree, say), thus giving you many potential solutions, some of them better than others.

Answer 2

The definition given in this Textbook says that

A data structure is a way to store and organize data in order to facilitate access and modifications.

Again, highlighting key words:

A data structure is a way to store and organize data in order to facilitate access and modifications.

---

Now, analogous to real world, if we want to store something, there are multiple ways.

Example : We want to store our Office Uniforms

• One way is to pile them up, one on top of other. So, you come, keep your uniform, and at next day, pick the topmost uniform, as it is easy to pick.
  What will happen? You essentially end up wearing same clothes again and again.

  

• Another way is to use Hangers, and Closet Rod. Assuming you have 7 clothes, and Office is 7-days working. So, you come, keep your uniform at one end of closet, and next day, pick clothes from another end.
  What will happen? You will realize that after 7 days, you will have to wear same clothes again, but at least for tomorrow, you will have new uniform.

  

So, we essentially have Stored Data, and in fact organized data in proper form. Which is Best? Well, it depends. Piling up is convenient, but Hanger One is Better for Choices. Note that even in pile up, or hanger we might want to access any clothes in between the pile. And may want to modify, maybe wash or iron that clothes.

Thus, when you are storing something, you should be able to access them.

---

In computer, we store data at different memory locations, if definition was limited to organized data or structured data, we missed out important point that we should be able to access data. In every data structure, you should be able to access each and every data, else storing them would be of not use.

By accessing, we mean that sufficient information and techniques should be there to get each and every data.

• Array : We should know actual length of array, and starting address, we then can traverse linearly
• Linked List : We should know address of head node, we then can traverse linearly
• Tree : We should know address of Root Node, we then can traverse in Pre-Order, Post-Order or In-Order. These techniques guarantee that each and every element will be accessed.

Thus, accessing itself means sufficient techniques and information are there. Moreover, this property of accessing should be preserved even after applying operations.

Example : Linked List Insertion

Here, we have three steps.

 - Establish link : 2 to New 
 - Establish link : New to 3 
 - Breaking link :  2 to 3

An observation will help us know that Establish link : 2 to New will automatically do Breaking link : 2 to 3

Thus, we have 2 steps only, this can be done in 2! ways i. e. 2 ways:

WAY1:

 - Establish link : 2 to New 
 - Establish link : New to 3 

Is this correct?

No!

Why?

While establishing link 2 to New, we have broken link 2 to 3. Now, we can't establish link New to 3, as we have lose access to 3. Initially, 2 has access of address of 3. But, now we don't have.

What's the correct way then?

WAY2:

- Establish link : New to 3 
- Establish link : 2 to New 

We can get address of 3, as it is pointed by 2, and we have broken link later on. 

Thus, you can see that accessing is important part of Data Structures Definition. There are Multiple way to do certain operation on Data Structures, this access helps us in putting restrictions on some of these way.

After doing any operation, data structure should remain a data structure. If definition was limited to organized data or structured data, then after doing Way 1, definition of data structure was not violated. But definition get violated in Way 1, if we add access part in definition, and we came to know that this way isn't correct!

---