Transcript linked list

Chapter 11
Data
Structures
OBJECTIVES
After reading this chapter, the reader should
be able to:
Understand arrays and their usefulness.
Understand records and the difference between an array and
a record.
Understand the concept of a linked list and the difference
between an array and a linked list.
Understand when to use an array and when to use a linked-list.
Data Structures

Data structure
uses a collection of related variables that can be
accessed individually or as a whole.

Data structure
a scheme for



organizing related pieces of data.
allowing different operations to be performed on the data.
The basic types of data structures include:






files
lists
arrays
records
trees
tables
11.1
ARRAYS
Array

Array
a fixed-size, sequenced collection of
elements of the same data type.

The subscripts indicate the ordinal number
of the element counting from the beginning
of the array.
Twenty individual variables
Figure 11-1
Figure 11-2
Processing individual variables
Figure 11-3
Arrays with subscripts and indexes
Figure 11-4
Processing an array
Figure 11-5

Frequency array
Show the number of elements with the same
value found in a series of numbers.
Figure 11-6

Histogram
A pictorial representation of a frequency array.
Figure 11-7- Part I
Two-dimensional array
Memory layout
Figure 11-8

Row-major storage
11.2
RECORDS
Record

Record
a collection of related elements, possibly of
different types, having a single name.
Each element in a record is called a field.

Difference

all elements – same type
 Record: elements – same or different types.
 Array:
Figure 11-9
Records
Note:
The elements in a record can be of the
same or different types.
But all elements
in the record must be related.
11.3
LINKED
LISTS
Linked list





Linked list
an ordered collection of data in which each element
contains the location of the next element.
Each element contains two parts: data and link.
The link contains a pointer (an address) that identifies the
next element in the list.
Singly linked list
The link in the last element contains a null pointer,
indicating the end of the list.
Figure 11-10
Linked lists
Figure 11-11
Node

Nodes : the elements in a linked list.

The nodes in a linked list are called self-referential records.
Each instance of the record contains a pointer to another
instance of the same structural type.

Figure 11-12
Inserting
a node
Figure 11-13
Deleting a node
Figure 11-14
Traversing a list