Intro to Data Structures for Programming - Comments

[QuantumQuest]

Greg Bernhardt submitted a new blog post

Intro to Data Structures for Programming

Continue reading the Original Blog Post.

 

[Wrichik Basu]

Another interesting article. The previous one was of great help to me. I used it as my defence when the teacher at my institution declared that my way of writing the algorithm was not the standard one.

I also remember what troubles I had to go through when the teacher couldn't explain what linked lists are. She was (and is still) confused, and as we were doing it in java where pointers don't exist, she was all the more confused. I remember explaining it to her at the end after reading it from javatpoint.com, but had this insight been there, it would have become easier.

I believe that @QuantumQuest would cover recursive data structures in the next insight. Keep writing such articles in computer science.

 

[anorlunda]

Good insight. Thank you @QuantumQuest . I think students will be thankful that you used Wikipedia for the references because of the universal accessibility.

I have a semantics question. The article is about collections where the operations Access, Insertion, Deletion, Search, Sorting, Copying, and Merge apply. Is there a generic name for that class of problems?

Other problems like matrix inversion, or error-correcting codes for a binary word, don't use those operations but they too need algorithms. They would be a different class of problems.

 

[QuantumQuest]

Good insight. Thank you @QuantumQuest . I think students will be thankful that you used Wikipedia for the references because of the universal accessibility.

Thank you @anorlunda. I hope that the insight will be of some help.

I have a semantics question. The article is about collections where the operations Access, Insertion, Deletion, Search, Sorting, Copying, and Merge apply. Is there a generic name for that class of problems?

Other problems like matrix inversion, or error-correcting codes for a binary word, don't use those operations but they too need algorithms. They would be a different class of problems.

The use of the appropriate data structure(s) in tandem with the most efficient algorithm(s) span a lot of domains of problems, where the algorithm(s) may point to what data structure(s) must be used or vice versa. Now, as I say in the tutorial, Access, Insertion, Deletion, Search, Sorting, Copying, and Merge is a general list of operations that give a sort of "template". There are operations defined on some ADTs that are identical, based on some of these or even different ones, depending on the ADT that we'll finally implement as a data structure. Now, a common feature pertaining to some of these "template" operations is the update element. This pertains to the "modifications" I say in the definition of a data structure, which is crucial to the efficient solution of a problem.

 

[Klystron]

Interesting distinction between abstract data type and data structure. Excellent pseudo-code. Thanks for the insights.
Looking forward to next article.

 

[rcgldr]

For data structures, the article could have included more types of structures, but I don't know how lengthy it would make such an article. The structures I can think off off hand are the intrinsic ones such as integers, floating point numbers, fixed point numbers, packed or unpacked decimal strings (mainframes), and software structure types, array, linked list, tree, queue, stack, ... . Perhaps a mention of ways to store dictionaries, such as the ones used for compression, such as sliding window (similar to a queue), or LZ78 / LZW (array of structures used like a stack with indexes used as links (to previous structure)). Other types include things like using an array of pointers or indexes to an array of structures for the order that the array is to be followed, and in one variation, where the indexes are used similarly to a linked list.

For a circular doubly linked list, sometimes a sentinel node is used, where the sentinel node is part of the circular linked list, and an empty list contains just the sentinel node. This is how std::list is implemented in Visual Studio.

 

[QuantumQuest]

For data structures, the article could have included more types of structures, but I don't know how lengthy it would make such an article. The structures I can think off off hand are the intrinsic ones such as integers, floating point numbers, fixed point numbers, packed or unpacked decimal strings (mainframes), and software structure types, array, linked list, tree, queue, stack, ... . Perhaps a mention of ways to store dictionaries, such as the ones used for compression, such as sliding window (similar to a queue), or LZ78 / LZW (array of structures used like a stack with indexes used as links (to previous structure)). Other types include things like using an array of pointers or indexes to an array of structures for the order that the array is to be followed, and in one variation, where the indexes are used similarly to a linked list.

For a circular doubly linked list, sometimes a sentinel node is used, where the sentinel node is part of the circular linked list, and an empty list contains just the sentinel node. This is how std::list is implemented in Visual Studio.

Thanks for the comment.

ADTs and Data Structures is a huge topic as we all know and also I mention in the tutorial, so I chose to present some elementary ADTs and data structures as an introduction, in a way that is (hopefully) comprehensible and at least, touches upon various important things and ideas. The target audience is beginner programmers and people in other fields that need to learn programming so my focus is on elementary ADTs and data structures used in general programming. In the next tutorial I'll present Queues, Trees, Sets and Graphs, as I mention in the present tutorial.

Now, while there are of course all these things you mention and many more, including (at least) most of them would not make for an intro tutorial as they're more advanced and / or specialized, but even in the case that someone decides to include them, the length of the tutorial would be skyrocketed taking into account preliminaries, main ideas and applications / examples for all of them and all this would finally make for an advanced tutorial. This is not to say of course that my choices regarding the material I present and its structure are perfect or even good and I don't make any such claim. Sure thing is that I tried to do it as best as I can, according to what I think would make a good intro which also gives the readers the motivation to study these topics - and beyond, further. It is my hope that it will be of some help.

 

[rcgldr]

I should have not clumped all this stuff together. As a better response to the article, typically, when used for data structures (versus nested functions), stacks (lifo) and queues (fifo) are explained at the same time. The other stuff I mentioned, like trees, is more advanced and would make sense to be presented later. Packed or unpacked decimal is mostly a mainframe concept, although even the Intel 8080 includes a decimal adjust after addition instruction (DAA) for packed decimal, but again this is a more advanced data type, and also would make sense to present later.

 

[Klystron]

As previously noted the author @QuantumQuest uses hypertext links effectively, including blinks to earlier tutorials and hyperlinked explanatory wiki articles. Perhaps 'internal linkages' could be used in ostensibly beginning text that expands the topic to include advanced material while simplifying lessons for the beginner and non-programmer. Nested hierarchies in other words, perhaps linking two knowledge streams Beginning Programming Tutorials & Advanced Software Engineering Concepts.

Pointers make a good exemplar. The beginning tutorial (level 2 ?) introduces pointers and dereferencing using pseudo-C. A link to a parallel advanced tutorial would expand on the topic including relevant background mathematics and theory. The relationship between data structures and functions seems an excellent path to understanding how to apply algorithms to solve problems.

 

[QuantumQuest]

As a better response to the article, typically, when used for data structures (versus nested functions), stacks (lifo) and queues (fifo) are explained at the same time.

Yes, you're right that explaining them at the same time is a good idea and initially I had this in mind but as I added more material to complete the first tutorial - in order to present things I regard as necessary, and also, due to other things I finally put in, the whole thing became pretty lengthy, so I decided to stop at stacks and present queues in the next tutorial but in any case, the topic can be presented equally well the way I'm doing it and in fact, this is the way I was taught about these subjects in the past.

 

[QuantumQuest]

As previously noted the author @QuantumQuest uses hypertext links effectively, including blinks to earlier tutorials and hyperlinked explanatory wiki articles. Perhaps 'internal linkages' could be used in ostensibly beginning text that expands the topic to include advanced material while simplifying lessons for the beginner and non-programmer. Nested hierarchies in other words, perhaps linking two knowledge streams Beginning Programming Tutorials & Advanced Software Engineering Concepts.

Pointers make a good exemplar. The beginning tutorial (level 2 ?) introduces pointers and dereferencing using pseudo-C. A link to a parallel advanced tutorial would expand on the topic including relevant background mathematics and theory. The relationship between data structures and functions seems an excellent path to understanding how to apply algorithms to solve problems.

Undoubtedly, there are many ways to present and structure things in a tutorial and mine is just one of them, which of course cannot claim any sort of perfection but of course there is some rationale behind it. The first tutorial has a number of fundamental concepts about algorithms and in the second tutorial I point out, almost from the outset, that

The reader is assumed to have sufficient familiarity with the topics presented in the first part and also some basic familiarity with at least one procedural programming language.

So, I explicitly assume that the reader has already the basics of at least one procedural programming language under his / her belt, including (at least) the basics of pointer manipulation. This is due to the fact that my main motivation for writing this series of tutorials is to refer to fundamental definitions and concepts about algorithms and data structures, in the context of general programming, for the first two tutorials and then in the third tutorial, give some historical context about programming , some general concepts and a number of practical things about programming and of various tools of the trade, drawn from my own experience. The fourth tutorial will be about some elements of history / evolution of the web, some general concepts and practical things about web development along with some tools, again drawn from my own experience. Data structures and algorithms is an often - partially or more than that, overlooked concept by many beginner - and even intermediate, programmers, in various scientific fields and contexts.

So, it is not my goal to teach programming in some programming language as, obviously, this is something that can be learned well only through a formal programming course combined with the relevant texts and tutorials and lots of practice and preferably professional experience or in the case of people who try to teach themselves programming, through good textbooks and tutorials and with a lot of efforts and (again) preferably, professional work.

Consequently, in this second tutorial as also in its next part, I refer to some fundamental concepts of programming briefly enough and I give some real code either in the form of examples or in the main text of the tutorial but my goal is to point out the importance of various algorithms / elementary data structures in the context of problem solving. Code is used - along with a number of comments, for a more practical understanding of a presented concept but not for teaching programming itself.

 

[rcgldr]

As a better response to the article, typically, when used for data structures (versus nested functions), stacks (lifo) and queues (fifo) are explained at the same time.

Yes, you're right that explaining them at the same time is a good idea and initially I had this in mind but as I added more material to complete the first tutorial - in order to present things I regard as necessary, and also, due to other things I finally put in, the whole thing became pretty lengthy, so I decided to stop at stacks and present queues in the next tutorial but in any case, the topic can be presented equally well the way I'm doing it and in fact, this is the way I was taught about these subjects in the past.

Perhaps the title should be changed then, like part 2 of a series of articles rather than "data structures". The article starts off as a continuation of the prior article, explains Turing Machines, includes several algorithms (sequential search, binary search, bubble sort, selection sort), explains linked lists, stacks, but not queues.