Question about data structures

[ALine]

I do not fully comprehend what a data structure "is." Are they the bounds in which computers act on in order to prevent computational confusion? Why do they exist? Why not just make everything abstract strings or use just a single data type? Does it have any relationships with sets in mathematics? Is there a relationship with and mathematics? What is the "use" and "function" of data structures? 

Thank you in advance for answering my questions.

ok, so I believe that data structures act as a sort of "specialized cell" for information. In which they are processed differently in different possible sections of memory. However that does not answer what there relationship is with mathematics. May it has something to do with the concept of "mapping" from different "spaces" however I still need to gain a handle on that concept.

[LaurieAG]

A data structure is created in a database to store and query the data from a program in the most efficient/effective way. The structure of the data is modeled in various ways.

https://en.wikipedia.org/wiki/Relational_database

One example of a programs data structure is an Entity Relationship diagram. There are many other ways to model data structures including Data Structure Diagrams, Data Flow Diagrams and NIAM for object oriented projects. The best method for modelling data structures depends on the nature of the data and many of the above methods can be used in conjunction with each other.

https://en.wikipedia.org/wiki/Entity–relationship_model

https://en.wikipedia.org/wiki/Data_structure_diagram

https://en.wikipedia.org/wiki/Data-flow_diagram

https://en.wikipedia.org/wiki/Object-role_modeling

[Strange]

As well as databases, data structures have a more general meaning in programming as a way of organising data.

One of the simplest structures is an array, where you have a number of things in consecutive locations in memory and you can select one by an index (its position in the array). That is useful for a lot of things: you can go through them in order, you can straight to any specific item, etc. But if you want insert something in the middle (to keep them in alphabetical order, say) then you have to move everything up in memory to make room for it. Som this can be slow.

So if you want to be able to go through in order but also quickly add and remove items (but don't care about going straight to item N) then you might put them in a "linked list" data structure. (And if you need to be able to go through the list backwards and forwards, then you might use a doubly-linked list.)

If you need faster access the the Nth item, then maybe a tree structure.

Or, if you want to look up things by name, then you might use a "dictionary", which is like an array, but instead of indexing it by number you can use arbitrary strings.

The best data structure for a problem often depends on the algorithm (and vice versa). So you will often find computer science books with titles like "Data structures and algorithms" (I had a good one by Sedgewick, but it is probably out of print now. I'm sure there are others.)

[Sensei]

Data structures exist even outside of computer science.

Take for example the real paper book and analyze what is needed to store the all its data.

Each page has page number. It is integer primitive data type, starting from 1.

Each page has contents. Usually text. It is string data type (in some languages primitive data type, in other e.g. C/C++ object).

So to store single page, you can make data structure like below:

struct Page {
	 int Page_Number;
	string Contents;
};

Now we have to put pages inside of book structure. We can do it using array of pages (structure inside of structure). Or we can store just pointer (address) to the first page element. Or we can use array/list OOP objects with template class..

struct Book {
	 string Title;
	 string Author;
	 string Description;
	 int Page_Count; // total number of pages in the book
	 struct Page Pages[ 100 ];
};

In C/C++ we can store pages as dynamically allocated array, and store just pointer to the first Page:

 struct Page *Pages;

or dynamically allocated each Page alone:

struct Page **Pages;

or

struct Page *Pages[];

or we can create static array with predefined quantity:

 struct Page Pages[ 100 ];

(less recommended because you can't exceed maximum predefined quantity, but requiring less work from programmer for allocation and freeing memory).

The best (for programmer) in C++ (or other OOP language) will be something like:

array<Page> Pages;

or

array<Page *> Pages;

It is special template class. https://en.cppreference.com/w/cpp/language/templates

 

We can go further with this example. Expand book by list of chapters. Index of keywords etc. etc.

Shelf/library of books. With index of authors, index of titles.

 

The simplest algorithm of searching for keyword will have to go through the all books in the library one by one (iteration) and check every page of a book (yet another iteration), and search for sub-string inside of page.Contents and print which book, at which page, at which row of a page has keyword we're interested in.

 

ps. Imagine book without page numbers, without chapters, without indexes. Imagine library without books on shelves sorted in alphabetical order. It would be complete disorder. Searching for any kind of data would be tremendously complicated and tiresome.

Edited May 14, 2020 by Sensei