## 3-1 LINEAR LIST CONCEPTS

Linear lists can be divided into two categories: general and restricted.

In a general list, data can be inserted and deleted anywhere and there are no restrictions on the operations that can be used to process the list. Such as the random list, ordered list.

In a restricted list, data can only be added or deleted at the ends of the structure and processing is restricted to operations on the data at the ends of the list. Such as the first in-first out(FIFO) list and the last in-first out(LIFO) list.

Now, we turn out attention to linear lists that are stored in structures that do not require physical adjacency: linked lists.

A linked list is an ordered collection of data in which each element contains the location of the next element.

Easy to inserted and deleted. Not necessary to shift elements of a linked list to make room for a new element or to delete an element.
We can not use the Interval Search algorithm – Binary Search to retrieval, because the elements of the linked list are not physically sequenced.

### Nodes

A node in a linked list is a sturcture that has at least two fields: one contains the data, the other the address of the next node in the sequence.

The nodes in a linked list are called self-referential structures.

One attributes of a linked list is that there is not a physically relationship between the nodes.

The pointer to the begging of the list is known as a head pointer.

When a node contains data about a list, the data are known as metadata(元数据).

### Create List

[code lang=”cpp”] // pseudocode // list.head for pointer to head node // list.count for the total numbers of the elements list.head = null list.count = 0 [/code]

### Insert Node

#### Insert into Empty List

[code lang=”cpp”] // pNew for the node inserted into the list pNew.next = list.head list.head = pNew [/code]