Page 102 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 7: Linked Lists

Notes
Figure 7.3: Adding Second Node

head

10 12

Source: http://www.cs.cmu.edu/~ab/15-123S09/lectures/Lecture%2010%20-%20%20Linked%20List%
20Operations.pdf
7.1.4 Representation of Linked Lists in Memory

Let LIST be a linked list. Then LIST will be maintained in memory 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 the information part and the next pointer field of a node of LIST respectively.
START contains the location of the beginning of the list, and a next pointer sentinel-denoted by
NULL-which indicates the end of the list.
The following examples of linked lists indicate that more than one list may be maintained in the
same linear arrays INFO and LINK. However, each list must have its own pointer variable
giving the location of its first node.

Example: Figure 7.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:

Figure 7.4: A Linked List in Memory

Source: http://www.csbdu.in/econtent/DataStructures/Unit1-DS.pdf
START = 9, so INFO[9] = N is the first character.
LINK[9] = 3, so INFO[3] = O is the second character.
LINK[3] = 6, so 1NFO[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.

LOVELY PROFESSIONAL UNIVERSITY 95