上一节我们介绍了线性表的概念，这一节阐述线性表的顺序存储实现。
顺序表
顺序表最大的特点就是：元素在内存中存储的位置是连续的，因此只要已知首地址就可以通过首地址 + 偏移量访问到顺序表中的元素。
但也因为这个特点，顺序表的插入和删除操作会比较麻烦，因为插入和删除操作会导致后面所有的元素需要移动，而移动元素的时间复杂度是 O(n)。
由于高级语言中的数组就是顺序表的实现，因此顺序表的实现通常都非常简单。
一个顺序表 Header 可定义结构如下：
1type SeqList struct {
2 data []interface{}
3 length int
4}
其中 data 是一个数组，用来存储顺序表中的元素，length 是顺序表中元素的个数。
初始化
初始化顺序表的方法如下：
1func NewSeqList() *SeqList {
2 return &SeqList{
3 data: make([]interface{}, 0),
4 length: 0,
5 }
6}
Go 的 slice 是可以动态扩展的，因此我们初始化顺序表的时候只需要初始化一个空的 slice 即可。
插入
插入操作的方法如下：
1func (l *SeqList) Insert(index int, value interface{}) error {
2 if index < 0 {
3 return errors.New("index out of range")
4 }
5
6 if l.length <= cap(l.data) {
7 l.data = append(l.data, value)
8 }
9 for i := l.length; i > index; i-- {
10 l.data[i] = l.data[i-1]
11 }
12 l.data[index] = value
13 l.length++
14 return nil
15}
插入操作的时间复杂度是 O(n)，因为插入操作会导致后面所有的元素需要移动。
删除
删除操作的方法如下：
1func (l *SeqList) Delete(index int) (interface{}, error) {
2 if index < 0 {
3 return nil, errors.New("index out of range")
4 }
5
6 value := l.data[index]
7 for i := index + 1; i < l.length; i++ {
8 l.data[i - 1] = l.data[i]
9 }
10 l.length--
11 return value, nil
12}
取操作是非常显然的，就不再赘述了。
一些练习
每个章节都会挑一些习题，同时给出一些思路。不会找很难的习题，只是为了让大家对这一章的内容有一个更深入的理解。有时候会给一些类型题的解题思路。
LeetCode 27 移除元素
这道题和他的姊妹题 26. 删除排序数组中的重复项 非常类似，只不过这道题是删除指定的元素，而不是重复的元素。这道题会更简单一些。
它唯一的难点在于要求 O(1) 的空间复杂度，也就是不能使用额外的数组来存储结果。
最暴力的解法是遇到 val 就删除，虽然它的时间复杂度是 $O(n^2)$，但测试是可以通过的。
1func removeElement(nums []int, val int) int {
2 size := len(nums)
3 for i := 0; i < size; i++ {
4 if nums[i] == val {
5 for j := i + 1; j < size; j++ {
6 nums[j - 1] = nums[j]
7 }
8 i--
9 size--
10 }
11 }
12 return size
13}
由于每次删除都要前移，优化的方法是使用所谓 “双指针” 的方法.
所谓双指针，其实不一定真的是一个物理意义上的指针，实际上这里的指针是一个抽象概念，它使用两个变量来存储当前遍历位置的数组下标，也算是一种 “指针“。
双指针指我们定义一个快指针，和一个慢指针，快指针用来遍历数组，慢指针用来记录当前不是 val 的元素的位置，当快指针遇到不是 val 的元素时，就将它赋值给慢指针对应的元素，然后慢指针向前移动一位。
一个更通用的定义是：
- 快指针用来寻找新数组的元素，即不含有目标元素的数组
- 慢指针指向更新新数组下标的位置
这样一来，保证了 nums[0..slow) 中的元素都不重复，当 fast 遍历完整个数组时，slow 指向的位置就是新数组的长度。
数组中的元素是无法删除的，只能被覆盖。所以我们可以使用快慢指针来覆盖掉所有的 val 元素，最后返回慢指针的位置即可。
1func removeElement(nums []int, val int) int {
2 size := len(nums)
3 slow := 0
4 for fast := 0; fast < size; fast++ {
5 if nums[i] != val {
6 nums[slow] = nums[fast]
7 slow++
8 }
9 }
10 return slow
11}
非常类似的相同解法的题目还有 283. 移动零 和 26. 删除排序数组中的重复项。
LeetCode 9 回文数
这道题的解法非常简单，就是将数字转换成字符串，然后判断字符串是否是回文串即可。
又是一道双指针，双指针在数组题目当中是很常见的。
1func isPalindrome(x int) bool {
2 s := []rune(strconv.Itoa(x))
3 left := 0
4 right := len(s) - 1
5 for left <= right {
6 if s[left] != s[right] {
7 return false
8 }
9 left++
10 right--
11 }
12 return true
13}
评论