Definition and Basic Operations of Linear Lists 003

Learning Requirements

As mentioned earlier, the logical structure of data consists of linear structures and non-linear structures. The elements of a linear structure have a 1:1 relationship with predecessors and successors. Non-linear structures include sets, graphs, and trees.

This article discusses linear lists, which are linear structures, and requires an understanding of the definition and basic operations of linear lists.

Definition and Basic Operations of Linear Lists

【1】Definition of Linear Lists

Example of a linear list:

The English alphabet consisting of the letters A, B, C, D ... Z, making up 26 letters.

A linear list (Linear List) can represent a finite sequence composed of n (n ≧ 0) data elements (nodes), where the number of elements n is referred to as the length of the list. When n = 0, it is called an empty linear list.

【2】Types of Linear Lists

A linear list is a type of logical structure in data structures, and in terms of storage structures, it can have a sequential storage structure and a linked storage structure; the former is called a sequential list, and the latter is called a linked list.

(1) Sequential List

In a sequential list, each element in the linear list is stored in a specified contiguous block of storage space according to its logical order.

The sequential list has two characteristics: first, it has random access capability, meaning that knowing its location (node index) allows immediate access to it. The second characteristic is that the sequential list requires contiguous storage space.

When performing insertion operations in a sequential list, multiple elements need to be moved.

(2) Linked List

In a linked list storage structure, each structure contains not only the information of the stored element but also the information about the logical relationship between elements. Linked lists can include singly linked lists, doubly linked lists, circular singly linked lists, circular doubly linked lists, and static linked lists.

Linked lists do not support random access and must be accessed starting from the HEAD; additionally, each node in the linked list must allocate space to store a pointer to the next node's location, allowing nodes in the linked list to be scattered anywhere in memory.

The following image shows a singly linked list.

[Image: https://www.studytonight.com/data-structures/linear-linked-list]

Test

1. If a linear list of 6 data elements is stored in an array in sequential storage mode, and the storage address of the first element is 1000, while the storage address of the sixth element is 1040, what is the storage address of the last element?

   A. 1112
   B. 1120
   C. 1124
   D. 1128

2. A linear list is a type of data structure composed of n data elements, where n can take the value of:

   A. 0 or any positive integer
   B. Non-negative integers
   C. Any positive integer or ∞
   D. Some positive integer

3. Among the storage methods of linear lists, the storage structure that allows random access to any element in the list is ____.

4. Which of the following options is an advantage of sequential storage structure?

   A. Convenient for insertion operations
   B. Convenient for deletion operations
   C. High storage density
   D. Convenient for storing various logical structures

5. In a certain linear list, the most commonly used operations are to insert an element after the last element and delete the first element. Among the following storage structures, the one that saves operation time the most is:

   A. Singly linked list
   B. Singly circular linked list with only a head pointer
   C. Doubly linked list
   D. Singly circular linked list with only a tail pointer

Note: The following article will introduce;

6. When using a singly linked list without a head node to store a queue, during a deletion operation:

   A. Only modify the head pointer
   B. Only modify the tail pointer
   C. Both head and tail pointers must be modified
   D. Both head and tail pointers may need to be modified

Note: The following article will introduce;

Answers: 1. B; 2. A; 3. Sequential storage structure; 4. C; 5. D; 6. D;