p. 405 · PDF 415

1 - 2 List

List (linked list) is a data structure that decides the arrangement of data with a pointer (i.e., position (or address) where element is recorded).

Enlarge original visual

Original source text

Figure 7-1  Image of list 

Source visual description

The original HEAD pointer leads to a sequence of element boxes. Each element includes its pointer field, and arrows connect the elements in order.

A list can also be represented by using an array. In this case, indexes that indicates the following elements are recorded in the pointers. Figure 7-2 shows an example of a list where an array is used.

Enlarge original visual

Original source text

Figure 7-2  Example of a list that uses an array 

Source visual description

The original example shows both an array containing data and pointers, and the linked order represented by those pointers.

Since an array is a data structure where the recording order of data has significance, insertion and deletion of data become manipulation of the entire array and are not efficient. By contrast,

p. 406 · PDF 416

in the case of a list where the recording order of data has no significance, insertion and deletion of data can be easily performed by just replacing the pointer. For example, for inserting data X that is newly added in element (5) between data 1 and data 2 in the list shown in Figure 7-2, the pointer of data 1 (i.e., data that is located just before the data to be inserted) and data X (i.e., data to be inserted) only need to be replaced. · 1 question

Enlarge original visual

Original source text

Figure 7-3  Example of inserting data in the list 

Source visual description

The original insertion drawing shows Data X and redirected links between Data 1 and Data 2.

On the other hand, for deleting data 2 from the list shown in Figure 7-2, the pointer of data 1 (i.e., data that is located just before the data to be deleted) can simply be replaced as shown in Figure 7-4. However, while data 2 is logically deleted from the list, data itself remains behind. Therefore, it is necessary to physically erase the data.

Enlarge original visual

Original source text

Figure 7-4  Example of deleting data from the list 

Source visual description

The original deletion drawing bypasses the Data 2 box while that box remains visible.

(1) Singly-linked list

Singly-linked list is a list that can trace data in only one direction. It is also referred to as a linear list, a single linked list, or a unidirectional list. Since each element just has a pointer that indicates the recording position of the next element, the amount of data is less. However, its applications are limited because data cannot be traced in the reverse direction. In the pointer of last element of the list, value (e.g., NULL, 0) that indicates end is recorded.

Enlarge original visual

Source visual description

Original List source layout. Source labels: .

(2) Doubly-linked list

Doubly-linked list is a list where data can be tracked in both directions because it has a forward pointer that indicates the recording position of the next element and a backward pointer that indicates the recording position of the previous element. It is also called a two-way list or a bidirectional list. Since elements can be tracked in both directions, it offers wider usage of data. However, the amount of data becomes large because more pointers are · 1 question

p. 407 · PDF 417

required, and processing (i.e., replacement of pointers) is also complex.

Enlarge original visual

Source visual description

Original List source layout. Source labels: .

(3) Circular list

Circular list is a list where all elements are linked in the form of a ring. When a circular list is implemented with a singly-linked list, the pointer to the last element points at the first element.

Enlarge original visual

Source visual description

Original List source layout. Source labels: .

A general list can be dynamically recorded in the storage area as required. Therefore, this data structure can be easily used even when the number of data items to be handled cannot be predicted. However, elements can only be traced in a sequential access, and therefore it is not suitable when some specific elements are to be processed most of the time. Even in singly-linked lists and circular lists, when a process is mostly performed on the last element of the list (for example, adding data in the last of the list), the tail pointer is used just like in a doubly-linked list. However, it is not possible to trace before the last element, and therefore, it does not result in any significant improvement of efficiency. (Efficiency hardly changes when the last element is deleted from the list.)