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.
3-2 LINKED LIST CONCEPTS
A linked list is an ordered collection of data in which each element contains the location of the next element.
Advantages for linked list data sturcture:
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.
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.
Linked List Data Structure
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.
Head Node Structure
When a node contains data about a list, the data are known as metadata(元数据).
3-3 LINKED LIST ALGORITHMS
// pseudocode // list.head for pointer to head node // list.count for the total numbers of the elements list.head = null list.count = 0
Insert into Empty List
// pNew for the node inserted into the list pNew.next = list.head list.head = pNew
Insert at Beginning
pNew.next = list.head list.head = pNew
Insert in Middle
pNew.next = pPre.next pPre.next = pNew
Insert at End
pNew.next = pPre.next( which is nullptr ) pPre.next = pNew