Information Technology Reference
In-Depth Information
Fig. 4.5. A linked list is an example of
a dynamic data structure that makes
it easy to remove or add items to a list.
(a) This shows the structure of a linked
list with each entry in the list having a
pointer
to the memory location of the
next element. (b) This illustrates how
easy it is to delete a node from the
linked list by just changing the pointer.
(a)
Head
Pointer
Name
Pointer
Name
NIL
Name
Pointer
(b)
Old Pointer
Removed
Head
Pointer
Name
Pointer
Name
NIL
Name
Pointer
New Pointer
items can usually be specified in advance. The same is not true for most types of
lists. The membership list for a sports club, for example, will grow and shrink as
new members join and old members leave. If we store a list of names in an array
of fixed length using sequential memory locations in the computer, removing
or adding names becomes very laborious because the data in the list must be fre-
quently reshuffled to keep them in the right order in memory. These problems
can be avoided if we do not store items in the list in a sequential memory block
but just in any convenient area of memory. To store the contents of the list,
each name in the list is stored in some location along with a
pointer
- a memory
address - to the location of the next name on the list (
Fig. 4.5a
). Deleting or
adding names is now straightforward because it just requires changing a single
pointer (
Fig. 4.5b
). With pointers, the address of the data storage location can
be kept separately from the actual data. Retrieving the data is thus a two-step
process - getting the address of the storage location and then going to that
location to get the data. Other common dynamic data structures are LIFO (Last-
In-First-Out) stacks, collections of items in which only the most recently added
item may be removed, and FIFO (First-In-First-Out) queues, collections of items
in which only the earliest added item may be removed.
Programming with objects: from SIMULA to C++
An important idea in object-oriented programming is
data abstraction
,
which focuses on classes, objects, and types of data in terms of how they
function and how they can be manipulated, while hiding details of how the
work is carried out. The idea of data abstraction can be traced back to two
Norwegian computer scientists, Kristen Nygaard and Ole-Johan Dahl (
B.4.3
).
They first presented their programming language SIMULA 67 in March 1967.
They were interested in using computers to run simulations and needed the
language to support subprograms that could stop and later restart at the place
they had stopped. To do this, Nygaard and Dahl introduced the idea of a
class
.
The key property of a class is that a data structure and the routines that
manipulate that data structure are packaged together. This led to the impor-
tant idea of
abstract data types
, sets of objects that share a common structure
and behavior.
Abstract data types were actually present in the original FORTRAN
language. There was a built-in
floating-point
data type, which represented
B.4.3. Ole-Johan Dahl (1931-2002)
(left) and Kristen Nygaard (1926-
2002) were first to introduce classes
and objects in their Simula program-
ming language.
Search WWH ::
Custom Search