《DATA STRUCTRUES A Psuedocode Approach with C++》Chaper 3. Linked List Learn Note

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

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.
Disadvantages:
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.

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

Create List

// pseudocode
// list.head for pointer to head node
// list.count for the total numbers of the elements
list.head = null
list.count = 0

Insert Node

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


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: 技术, 数据结构, 算法, 随记 | 标签: , , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据