|
列表是一种常见的 ADT，用于保存有序数据，具有附加数据项、删除数据项、搜索数据项是否存在以及打印列表等操作。
List ADT 常见操作
| 相关操作 | 描述 |
|---|
| Append(list, x) | Inserts x at end of list | | Prepend(list, x) | Inserts x at start of list | | InsertAfter(list, w, x) | Inserts x after w | | Remove(list, x) | Removes x | | Search(list, x) | Returns item if found, else returns null | | Print(list) | Prints list’s items in order | | PrintReverse(list) | Prints list’s items in reverse order | | Sort(list) | Sorts the lists items in ascending order | | IsEmpty(list) | Returns true if list has no items | | GetLength(list) | Returns the number of items in the list |
1. Singly-linked lists
1.1 Singly-linked lists 注意的点
单链表是一种用于实现列表 ADT 的数据结构，其中每个节点都有数据和指向下一个节点的指针。
列表结构通常具有指向列表的第一个节点和最后一个节点的指针。
单链表的第一个节点称为head，最后一个节点称为tail。
单链表是一种位置列表：其中元素包含指向列表中下一个和/或前一个元素的指针的列表。
注：单链表中的RemoveAfter 操作，如果移除的是空值，则移除单链表的head值。
例：arr = 3, 57, 28, 40
ListRemoveAfter(arr, null)
操作之后的结果： 57, 28, 40
2. Array-based lists
2.2 Array-based lists 注意的点
基于数组的列表是使用数组实现的列表 ADT。基于数组的列表支持常见的列表 ADT 操作，例如追加、前置、插入后、删除和搜索。
相关操作与List 的抽象类型一致，在许多编程语言中，数组具有固定的大小。基于数组的列表实现将根据需要随着元素数量的变化动态分配数组。
如果在数组后面添加元素时，数组没有可以分配的空间，那么数组的allocationSize会增长之前的两倍。
例如：
allocationSize = 5
length = 5
arr = [10,20,30,5,40]
在arr后面添加元素，由于没有足够的分配空间，allocationSize会变为10。
对于数组来说，指定位置插入元素和删除元素会导致指定位置之后的元素前移或者后移，所以插入和删除的最坏情况时间复杂度是 O（N）。
|