I am familiar with the idea of linearity in data structures. But I'm curious about which data structures are linear and which are non-linear. Can someone provide a list of both types of data structures that we often utilize? My source of knowledge is Scaler Academy and GFG. Could someone please clarify in detail?
Data Structures, Linear and Non-Linear (1 Viewer)
- Thread starter bettey12
- Start date
- Local time
- Today, 09:49
- Joined
- Feb 28, 2001
- Messages
- 27,196
I have moved this question to a different heading because the Sample Databases area is restricted. You will get more visibility in this area.
- Local time
- Today, 09:49
- Joined
- Feb 28, 2001
- Messages
- 27,196
Now to answer your question...
Imagine a family tree diagram with siblings included. You traverse the tree based on two "parent" links - and each parent has its own parents (and siblings). Each person may also have some number of children (literal as well as "child nodes"). This is a hierarchical non-linear structure. Because it has generational "levels" you have to traverse it in a more complex manner. Frequently you must use recursion to enumerate and elaborate the members of the structure.
Among my other interests, I have traced my own genealogy back a few hundred years, all the way from Essex, England to south Louisiana. And my wife's ancestry goes to Acadia, Nova Scotia in the early 1700s - which makes her a member of one of the oldest Cajun families in the area. The data structure there is a total nightmare, particularly since in one case I have a person who has (a) a father who was her mother's husband, (b) her biological father, (c) her adopted father, and (d) after her adopted mother's divorce, a stepfather. Four fathers. As a result, several half-sibs and several adopted aunts and uncles and step-aunts and step-uncles. DEFINITELY a non-linear structure there - and I have it on my computer using EAV techniques (see below).
A disk using NTFS formatting has a hierarchical structure. It's another case where you need recursion to manage the structure. So if you are for some reason recording file locations in a data structure, it might also have to be hierarchical to properly preserve characteristics, i.e. make the map match the territory.
I mentioned above a data structure we sometimes use called EAV, or Entity-Attribute-Value. It is a variant of the idea of object-oriented programming (OOP). In either the EAV or OOP case there is some object and we enumerate a variable number of things that we know about it. An EAV record has a pointer or designator to the object it represents, an attribute name or code, and the value associated with that attribute. The difference between EAV records and OOP records is that usually (but not always), the OOP records for a given object type have a fixed number of attributes, some of which might be empty, null, or zero. The EAV records can be any number required even for two objects of the same type. (Take, for example, a car with all sorts of optional add-on packages.) In each case these are non-linear with respect to the attributes because first you have to find the object, then you have to find its attributes, then maybe go back for another object and repeat the process.
We sometimes get work-flow scheduling questions here. In scheduling there is the concept of a queue with priorities. You have a bunch of things to do. Some are urgent. Some of them are important but not life-threatening. Some of them are just routine. Some of them could theoretically wait until Hell freezes over. How do you manage this? There are two main ways. One involves a single linear queue and you sort the queue according to the priority of each item, highest priority first, other attributes second. There is another way involving multiple queues where each queue is associated with one priority and you put each item in the correct queue. Then, if someone comes along asking for that "thing" to be given higher priority, you can move it. Usually by removing first, then changing the priority attribute, then re-threading it into the queue. That mobility technically makes it a non-linear system. (See below my discussion of "projection" and realize that the single-queue pre-sorted case is merely a method of projection.)
There are other data structures we use that are non-linear. What they have in common is something that sub-divides the group of data in more than one way such that a single loop through the structure won't catch everything, you need some type of nested looping to account for multiple dimensions, or recursion where there is a multi-membered relationship. Whether it is priority or generations or sub-folders, these are examples of non-linear structures.
You can make the argument that unless you are using multi-threaded processor technology, the program is a single-threaded process and has to be processed linearly. And that is true. But the programs that traverse these structures are technically doing something called "projection" - which is the way that you reduce the number of dimensions of something so as to be able to represent it at all. Think of an Earth globe in school and a pull-down geographic map - in which case the map is a 2-dimensional projection of the 3-dimensonal globe. Well, making an algorithm to linearly traverse a non-linear or multi-dimensional structure is just another form of projection. And the tip-off that you have a non-linear structure is that your algorithm needs more than one loop or more than one list of attributes to completely traverse the list. Sometimes this means that the distinction is subtle - like OOP attributes. Sometimes it bludgeons you - like a multi-dimensional hierarchy.
Imagine a family tree diagram with siblings included. You traverse the tree based on two "parent" links - and each parent has its own parents (and siblings). Each person may also have some number of children (literal as well as "child nodes"). This is a hierarchical non-linear structure. Because it has generational "levels" you have to traverse it in a more complex manner. Frequently you must use recursion to enumerate and elaborate the members of the structure.
Among my other interests, I have traced my own genealogy back a few hundred years, all the way from Essex, England to south Louisiana. And my wife's ancestry goes to Acadia, Nova Scotia in the early 1700s - which makes her a member of one of the oldest Cajun families in the area. The data structure there is a total nightmare, particularly since in one case I have a person who has (a) a father who was her mother's husband, (b) her biological father, (c) her adopted father, and (d) after her adopted mother's divorce, a stepfather. Four fathers. As a result, several half-sibs and several adopted aunts and uncles and step-aunts and step-uncles. DEFINITELY a non-linear structure there - and I have it on my computer using EAV techniques (see below).
A disk using NTFS formatting has a hierarchical structure. It's another case where you need recursion to manage the structure. So if you are for some reason recording file locations in a data structure, it might also have to be hierarchical to properly preserve characteristics, i.e. make the map match the territory.
I mentioned above a data structure we sometimes use called EAV, or Entity-Attribute-Value. It is a variant of the idea of object-oriented programming (OOP). In either the EAV or OOP case there is some object and we enumerate a variable number of things that we know about it. An EAV record has a pointer or designator to the object it represents, an attribute name or code, and the value associated with that attribute. The difference between EAV records and OOP records is that usually (but not always), the OOP records for a given object type have a fixed number of attributes, some of which might be empty, null, or zero. The EAV records can be any number required even for two objects of the same type. (Take, for example, a car with all sorts of optional add-on packages.) In each case these are non-linear with respect to the attributes because first you have to find the object, then you have to find its attributes, then maybe go back for another object and repeat the process.
We sometimes get work-flow scheduling questions here. In scheduling there is the concept of a queue with priorities. You have a bunch of things to do. Some are urgent. Some of them are important but not life-threatening. Some of them are just routine. Some of them could theoretically wait until Hell freezes over. How do you manage this? There are two main ways. One involves a single linear queue and you sort the queue according to the priority of each item, highest priority first, other attributes second. There is another way involving multiple queues where each queue is associated with one priority and you put each item in the correct queue. Then, if someone comes along asking for that "thing" to be given higher priority, you can move it. Usually by removing first, then changing the priority attribute, then re-threading it into the queue. That mobility technically makes it a non-linear system. (See below my discussion of "projection" and realize that the single-queue pre-sorted case is merely a method of projection.)
There are other data structures we use that are non-linear. What they have in common is something that sub-divides the group of data in more than one way such that a single loop through the structure won't catch everything, you need some type of nested looping to account for multiple dimensions, or recursion where there is a multi-membered relationship. Whether it is priority or generations or sub-folders, these are examples of non-linear structures.
You can make the argument that unless you are using multi-threaded processor technology, the program is a single-threaded process and has to be processed linearly. And that is true. But the programs that traverse these structures are technically doing something called "projection" - which is the way that you reduce the number of dimensions of something so as to be able to represent it at all. Think of an Earth globe in school and a pull-down geographic map - in which case the map is a 2-dimensional projection of the 3-dimensonal globe. Well, making an algorithm to linearly traverse a non-linear or multi-dimensional structure is just another form of projection. And the tip-off that you have a non-linear structure is that your algorithm needs more than one loop or more than one list of attributes to completely traverse the list. Sometimes this means that the distinction is subtle - like OOP attributes. Sometimes it bludgeons you - like a multi-dimensional hierarchy.
- Local time
- Today, 10:49
- Joined
- Feb 19, 2002
- Messages
- 43,314
Linear structures are implemented as "flat" files such as .txt and .csv and arrays. The data, i.e. fields/records are stored end to end. one after another. So rec1, fld1, fld2, fld3, rec2, fld1, fld2, fld3, etc. Proximity rather than pointers dictate the organization.
Relational databases are non-linear except at the very lowest level of storage. At the lowest level, records and fields are stored the same way they are in flat files. The difference is that the database engine has the ability to move them around and replace them with pointers if an updated record can't be placed back into its original space. Between records 2 and 4 sits record 3 and it is 100 bytes. If you update it and a text field becomes longer so the record is now 105 bytes, the database engine can't put it back where it was so one solution is a pointer to tell the engine where to find the replacement. In some situations, if there is sufficient free space, the database engine might replace an entire block (physical record, sector, whatever the OS calls the unit at which physical I/O is performed for a particular device) so that record 3 can go back where it was between records 2 and 4.
Relational databases are non-linear except at the very lowest level of storage. At the lowest level, records and fields are stored the same way they are in flat files. The difference is that the database engine has the ability to move them around and replace them with pointers if an updated record can't be placed back into its original space. Between records 2 and 4 sits record 3 and it is 100 bytes. If you update it and a text field becomes longer so the record is now 105 bytes, the database engine can't put it back where it was so one solution is a pointer to tell the engine where to find the replacement. In some situations, if there is sufficient free space, the database engine might replace an entire block (physical record, sector, whatever the OS calls the unit at which physical I/O is performed for a particular device) so that record 3 can go back where it was between records 2 and 4.
- Local time
- Today, 09:49
- Joined
- Feb 28, 2001
- Messages
- 27,196
Here is the simplest example of a linear structure used in linear fashion as it might apply to databases and/or VBA.
Take the sum of an array of numbers. OR in SQL, use the SUM() aggregate function on a single field in a recordset. OR in Access VBA use the DSUM Domain Aggregate function on a single field in a recordset. The count or COUNT() or DCOUNT is another example.
Here is a simple-minded example of a non-linear structure: A sales-tracking system where you have an Invoice and Line Items within the invoice. This is also an example of a parent/child dependency, which might be a good indicator of at least a simple non-linear case. NOTE: IF you only care about the invoice and customer information, it might be closer to linear. BUT the moment you care about line items, ... NON-linear. In some cases, linearity depends on intent.
Here's another simple-minded non-linear case: Finding a specific file on disk using Windows Explorer to "drill down" into the folders until you find the file AND it wasn't in the top-level folder on that drive and wasn't in the first folder within that top-level folder.
Take the sum of an array of numbers. OR in SQL, use the SUM() aggregate function on a single field in a recordset. OR in Access VBA use the DSUM Domain Aggregate function on a single field in a recordset. The count or COUNT() or DCOUNT is another example.
Here is a simple-minded example of a non-linear structure: A sales-tracking system where you have an Invoice and Line Items within the invoice. This is also an example of a parent/child dependency, which might be a good indicator of at least a simple non-linear case. NOTE: IF you only care about the invoice and customer information, it might be closer to linear. BUT the moment you care about line items, ... NON-linear. In some cases, linearity depends on intent.
Here's another simple-minded non-linear case: Finding a specific file on disk using Windows Explorer to "drill down" into the folders until you find the file AND it wasn't in the top-level folder on that drive and wasn't in the first folder within that top-level folder.
