Linked Lists:
A linked list, or one way list. Is a linear collection of
data elements. Called nodes, where the linear order is given by means of
pointers. That is, each node is divided into two parts: the first part contains
the information of the elements, and the second part, called the link field or
next pointer field, contains the address of the next node in the list.
Figure 5.2 is a schematic diagram of linked with 5 nodes.
Each node is pictured with two parts. The left part represent information part
of the node, which many contain an entire record of data items (e.g., NAME,
ADDRESS ,….). The right part represents the next pointer field of the node, and
there an arrow drawn from it to the next
node in the list. This follows the usual practice of drawing an arrow from a
field to a node when the address of the node appears in the give field . the
pointer of the last node contains a special value, called null pointer, which
in any invalid address.
 |
| linked list |
Fig. 5.2
linked list with 5 nodes
(In actual practice, 0 or a negative number is used for the
null pointer.) The null pointer, denoted by
x in the diagram, signals the end
of the list. The linked list also contains a list pointer variable-called
START or NAME – which contains the
address of the first node in the list; hence there is an arrow drawn from START
to the first node. Clearly , we need only this address in START to trace
through the list. A special case is the list that has no nodes. Such a list is
called the null list or empty list and is denoted by the null pointer in the
variable START.
For example :-
A hospital ward contain 12 beds, of which 9 are occupied as
shown in fig. 5.3. suppose we want an alphabetical listing of the patients.
This listing may be given by the pointer field, called next in the figure. We
use the variable START pointer to the first patient. Hence START contains 5,
since the first patient, Adams, occupies bed 5; Also , Adams’s pointer is equal
to 3, since Dean, next patient, occupies bed 3;
Dean’s pointer is 11, since Fields, the next patient,
occupies bed 11; and so on. The entry for the last patient (Samuels) contains
the null pointer, denoted by 0. (some arrows have been drawn to indicated the
listing of the first few patients.)
REPRESENTATION
OF LINKED LISTS IN MEMORY
Let LIST be linked list. Then LIST will be maintained in
memory , unless otherwise specified or implied, as follows. First of all, LIST
requires two linear arrays-we will call them here INFO and LINK-such that
INFO[K] and LINK[K] contain, respectively, the information part and the next
pointer of a node of LIST/ as noted above, List also requires a variable
name-such as START-which contains the location of the beginning of the list,
and a next pointer sentinel-denoted by NULL- which indicates the end of the
list. Since the subscript of the arrays INFO and Link will usually be positive,
we will choose NULL = 0, unless otherwise stated.
The following example of linked lists indicated that the
nodes of a list need not occupy adjacent element in the arrays INFO and LINK,
and that more than more than one list may be maintained in the same linear
arrays INFO and LINK. However, each list must have its pointer variable giving location of its first
node.
EXAMPLE: 5.2
Figure 5.4 pictures a linked list in memory where each node
of the list contains a single character. We can obtain the actual list of
characters, or, in other words, the string as follows:
START = 9, so INFO [90] = N is the first character.
LINK [9] = 3, SO INFO [3] = 0 is the second character.
LINK [3] = 6, so INFO [6] = (BLANK) is the third character.
LINK [6] = 11, so INFO [11] = E is the fourth character.
LINK [11] = 7, so INFO [7] = X is the fifth character.
LINK [7] = 10, so INFO [10] = I is the sixth character.
LINK [10] = 4, so INFO [4] = T is the seventh character.
LINK [4] = 0, the NULL value, so the list has ended.
In other words, NO EXIT is the character string.
NO EXIT REPRESENT IN LIST
`
No comments:
Post a Comment
Please do not enter any spam link in the comment box.