01-概述

定义

N个数据元素的有限序列。数据元素可以是原子类型，也可以是结构类型，视具体使用场景和需求而定。

线性结构的特点

1. 存在唯一的被称作“第一个”的元素
2. 存在唯一的被称作“最后一个”的元素
3. 除“第一个”元素之外，集合中的元素均只有一个“直接前驱”
4. 除“最后一个”元素之外，集合中的元素均只有一个“直接后继”

表示方法

不同的表示方法，代表了数据不同的存储形式，同时也直接决定了各自在不同存储场景下的优缺点表现。 线性表常见的表示方法为顺序表示法和链式表示法。

这里需要澄清的一点是：

线性表只是逻辑上的一种数据组织形式，我们通过不同的编程 语言来实现其定义时，可以选取不同的原子类型，或结构类型来实现。 这里提到的顺序表示法和链式表示法就是分别指通过编程语言中的数组和链表在内存上 的组织结构形式来实现。

1. 顺序表示法

用一组地址连续的存储单元依次存储线性表的数据元素，也叫顺序表。 在go以及其他众多语言中，对应数组类型。

length = 10
// 使用array进行表示
linkedList := [length]any // any是go中任意类型的意思，是interface{}的别名
// 使用slice进行表示，后续为了方便演示，采用该种方式实现代码
linkedList := make([]any, length)

需要注意连续的存储单元，这意味着：

1. 以整个线性表为操作对象时，进行某些操作可能比较笨重，可能需要移动、复制大量的元素
2. 但是以线性表中某个元素为操作对象时，就可以很方便的寻址并操作
3. 编程语言在申请内容时，会申请一段连续的内存空间。这里很可能出现总空余内存空间大于申请的量，但是因为可用空间不连续而导致的申请失败。

读写性能表现：

1. 对于线性表的某个元素而言：
   1. 读：可以随机访问到第i个元素，然后读取
      1. 空间复杂度：O(0)
      2. 时间复杂度：O(1)
   2. 写：可以随机访问到第i个元素，然后写入/更新值
      1. 空间复杂度：O(0)
      2. 时间复杂度：O(1)
2. 对于线性表整体而言：
   1. 读(遍历)：只要知道第一个元素的地址即可遍历整个线性表
      1. 空间复杂度：O(0)
      2. 时间复杂度：O(n)
   2. 写：向线性表中插入、删除元素时，较通用方案都需要开辟额外的存储单元来存储变更后的线性表。
      1. 空间复杂度：O(n)
      2. 时间复杂度：O(n)

注：随机指的是可以通过首个元素，通过公式等方法快速算出其他元素地址的能力。

2. 链式表示法

不要求逻辑上相邻的元素在物理存储单元上也相邻（相邻与不相邻皆可），只需要逻辑上的前一个元素可以获取直接后继元素的存储地址即可。 构成这样存储结构的数据成为节点，在go以及其他众多语言中，对应struct。 每个节点中包含本身信息的信息域和一个指向下一个节点的指针域。

type LinkedListNode struct {
   Next   *LinkedListNode `json:"next"`
   Data   any             `json:"data"`
} 

N个节点链接起来的这种存储结构称为链表。当n=0时，称之为空链表。

需要注意物理存储单元可以是连续的，也可以是离散的，这意味着：

1. 以线性链表中某个元素为操作对象时，进行某些操作可能比较笨重，可能需要遍历整个链表才可以达到目的
2. 但是以整个线性链表为操作对象时，比如向线性链表中插入、删除节点时，就可以很方便的通过修改指针来完成
3. 编程语言在申请内容时，因为不再有连续空间的要求，和数组相比，就更加容易申请成功内存。

读写性能表现：

1. 对于线性链表的某个元素而言：
   1. 读：只能顺序从第一个访问到第i个元素，然后读取
      1. 空间复杂度：O(0)
      2. 时间复杂度：O(n)
   2. 写：只能顺序从第一个访问到第i个元素，然后写入/更新值
      1. 空间复杂度：O(0)
      2. 时间复杂度：O(n)
2. 对于线性链表整体而言：
   1. 读(遍历)：只要知道第一个元素的地址即可遍历整个线性链表
      1. 空间复杂度：O(0)
      2. 时间复杂度：O(n)
   2. 写：向线性链表中插入、删除元素时，只需要通过修改指针指向即可，不需要额外的空间。
      1. 空间复杂度：O(0)
      2. 时间复杂度：O(1)

线性表的基础操作

线性表的基础操作抽象为以下几种：

1. ClearList: 将原有的线性表中的数据清空
2. IsEmpty：判断线性表是否为空表
3. GetLength：获取当前线性表中数据的长度
4. GetElementByIndex：获取线性表中位于指定索引的元素
5. GetElementIndexByValue：获取线性表中与指定值相等元素的索引
6. GetPriorElement：获取线性表中与指定值相等元素的前一个元素
7. GetNextElement：获取线性表中与指定值相等元素的后一个元素
8. InsertByIndex：在线性表中指定索引处插入元素
9. DeleteByIndex：在线性表中指定索引处删除元素
10. Traverse：遍历打印所有元素

Golang中的表示

之前说过线性表只是逻辑上的一种数据组织形式，在golang中上述操作进行抽象， 就得到了以下的接口(interface)定义

// LinearList 定义了线性表所具有的公共操作
type LinearList interface {
	ClearList()
	IsEmpty() bool
	GetLength() int
	GetElementByIndex(index int) (any, error)
	GetElementIndexByValue(element any) (int, error)
	GetPriorElement(element any) (any, error)
	GetNextElement(element any) (any, error)
	InsertByIndex(index int, element any) error
	DeleteByIndex(index int) (any, error)
	Traverse()
}

Golang中的实现

在Go中，任何一个类型，只要实现了某个接口定义的所有方法列表，就说明改类型 实现了该接口。后续两节将分别以顺序表和链表为存储组织形式来对线性表进行实现。

算法

这里将第二章的第一节出现的算法进行实现，算法序号和原书中的序号保持一致。 注意：

1. 下面出现的LinearList是go中的interface，只是逻辑上的概念
2. 因为只要实现了interface的类型都可以作为参数传递给该方法，所以这里既可以使用线性表,也可以使用链表作为具体实现。

algo-2.1 两个线性表的并集

实现两个线性表的并集： A = A 并 B

// Union two list, just like A = A Union B
func Union(a, b LinearList) error {
	aLen, bLen := a.GetLength(), b.GetLength()
	for i := 0; i < bLen; i++ {
		bElement, err := b.GetElementByIndex(i)
		if err != nil {
			return err
		}
		_, err = a.GetElementIndexByValue(bElement)
		if err != nil && strings.Contains(err.Error(), "can't find element") {
			if err := a.InsertByIndex(aLen, bElement); err != nil {
				return err
			}
			aLen = a.GetLength()
		} else if err != nil {
			return err
		} else if err == nil {
			continue
		}
	}
	return nil
}

algo-2.2 两个有序线性表的合并

实现将两个有序线性表的合并，合并生成的线性表依然有序

// MergeList Merge two non-decreasing order list into a new non-decreasing order list
func MergeList(a, b LinearList) (LinearList, error) {
	result := model.NewSingleLinkedList(false)
	var i, j = 0, 0
	for i < a.GetLength() && j < b.GetLength() {
		aElement, err := a.GetElementByIndex(i)
		if err != nil {
			return nil, err
		}

		bElement, err := b.GetElementByIndex(j)
		if err != nil {
			return nil, err
		}

		ok, err := utils.LessThenOrEqual(aElement, bElement)
		if err != nil {
			return nil, err
		}
		if ok {
			if err := result.InsertByIndex(result.GetLength(), aElement); err != nil {
				return nil, err
			}
			i++
		} else {
			if err := result.InsertByIndex(result.GetLength(), bElement); err != nil {
				return nil, err
			}
			j++
		}
	}

	for i < a.GetLength() {
		aElement, err := a.GetElementByIndex(i)
		if err != nil {
			return nil, err
		}
		if err := result.InsertByIndex(result.GetLength(), aElement); err != nil {
			return nil, err
		}
		i++
	}

	for i < b.GetLength() {
		bElement, err := b.GetElementByIndex(i)
		if err != nil {
			return nil, err
		}
		if err := result.InsertByIndex(result.GetLength(), bElement); err != nil {
			return nil, err
		}
		i++
	}

	return result, nil
}

其他同类文章

• 数据结构 · 算法-2.4
• 数据结构 · 算法-2.3
• 数据结构 · 05-双向链表实现
• 数据结构 · 04-静态链表实现
• 数据结构 · 算法-2.2