Fundamentals of Computer Programming with C# HTML version

Chapter 16. Linear
Data Structures
In This Chapter
In this chapter we are going to get familiar with some of the basic
presentations of data in programming: lists and linear data structures.
Very often in order to solve a given problem we need to work with a sequence
of elements. For example, to read completely this book we have to read
sequentially each page, i.e. to traverse sequentially each of the elements of
the set of the pages in the book. Depending on the task, we have to apply
different operations on this set of data. In this chapter we will introduce the
concept of abstract data types (ADT) and will explain how a certain ADT
can have multiple different implementations. After that we shall explore
how and when to use lists and their implementations (linked list, doubly-
linked list and array-list). We are going to see how for a given task one
structure may be more convenient than another. We are going to consider the
structures "stack" and "queue", as well as their applications. We are going
to get familiar with some implementations of these structures.
Abstract Data Structures
Before we start considering classes in C#, which implement some of the most
frequently, used data structures (such as lists and queues), we are going to
consider the concepts of data structures and abstract data structures.
What Is a Data Structure?
Very often, when we write programs, we have to work with many objects
(data). Sometimes we add and remove elements, other times we would like
to order them or to process the data in another specific way. For this reason,
different ways of storing data are developed, depending on the task. Most
frequently these elements are ordered in some way (for example, object A is
before object B).
At this point we come to the aid of data structuresa set of data
organized on the basis of logical and mathematical laws. Very often the choice
of the right data structure makes the program much more efficient – we could
save memory and execution time (and sometimes even the amount of code
we write).