数据结构- 数组与链表

数组

数组（array）是一种线性数据结构，元素的位置称之为索引，在内存中存储的是连续索引的位置

常用操作

初始化数组

/* 初始化数组 */
var arr [5]int
// 在 Go 中，指定长度时（[5]int）为数组，不指定长度时（[]int）为切片
// 由于 Go 的数组被设计为在编译期确定长度，因此只能使用常量来指定长度
// 为了方便实现扩容 extend() 方法，以下将切片（Slice）看作数组（Array）
nums := []int{1, 3, 2, 5, 4}

访问元素

数组元素基于连续地址

得出：元素内存地址=数组内存地址（首元素地址）+元素长度×元素索引（内存地址偏移量）

插入元素

中间插入一个元素时，该元素的所有元素往后移动一位

/* 在数组的索引 index 处插入元素 num */
func insert(nums []int, num int, index int) {
    // 把索引 index 以及之后的所有元素向后移动一位
    for i := len(nums) - 1; i > index; i-- {
        nums[i] = nums[i-1]
    }
    // 将 num 赋给 index 处的元素
    nums[index] = num
}

删除元素

中间删除一个元素时，该元素的所有元素往前移动一位

/* 删除索引 index 处的元素 */
func remove(nums []int, index int) {
    // 把索引 index 之后的所有元素向前移动一位
    for i := index; i < len(nums)-1; i++ {
        nums[i] = nums[i+1]
    }
}

遍历数组

/* 遍历数组 */
func traverse(nums []int) {
    count := 0
    // 通过索引遍历数组
    for i := 0; i < len(nums); i++ {
        count += nums[i]
    }
    count = 0
    // 直接遍历数组元素
    for _, num := range nums {
        count += num
    }
    // 同时遍历数据索引和元素
    for i, num := range nums {
        count += nums[i]
        count += num
    }
}

查找元素

/* 在数组中查找指定元素 */
func find(nums []int, target int) (index int) {
    index = -1
    for i := 0; i < len(nums); i++ {
        if nums[i] == target {
            index = i
            break
        }
    }
    return
}

扩容数组

/* 扩展数组长度 */
func extend(nums []int, enlarge int) []int {
    // 初始化一个扩展长度后的数组
    res := make([]int, len(nums)+enlarge)
    // 将原数组中的所有元素复制到新数组
    for i, num := range nums {
        res[i] = num
    }
    // 返回扩展后的新数组
    return res
}

数组的优点与局限性

数组存储在连续的内存空间内，且元素类型相同。这种做法包含丰富的先验信息，系统可以利用这些信息来优化数据结构的操作效率。

空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。
支持随机访问：数组允许在 �(1) 时间内访问任何元素。
缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。

连续空间存储是一把双刃剑，其存在以下局限性。

插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。
长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。
空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。

链表

线性数据结构，每一个元素都是节点对象，通过”引用“连接分散内存

type ListNode struct {
    Val  int
    Next *ListNode
}

常见操作

package list

type ListNode struct {
	Val  int
	Next *ListNode
}

func NewListNode(val int) *ListNode {
	return &ListNode{
		Val:  val,
		Next: nil,
	}
}

/* 在链表的节点 n0 之后插入节点 P */
func insertNode(n0 *ListNode, P *ListNode) {
	n1 := n0.Next
	P.Next = n1
	n0.Next = P
}

// 删除链表中特定值的节点
func deleteNodeWithValue(head *ListNode, val int) *ListNode {
	// 如果要删除的节点是头节点
	if head.Val == val {
		return head.Next
	}
	current := head
	for head.Next != nil {
		if current.Next.Val == val {
			current.Next = current.Next.Next
			break
		}
		current = current.Next
	}
	return head
}

/* 访问链表中索引为 index 的节点 */
func access(head *ListNode, index int) *ListNode {
	for i := 0; i < index; i++ {
		if head == nil {
			return nil
		}
		head = head.Next
	}
	return head
}

/* 查找某索引的节点 */
func searchNode(head *ListNode, target int) int {
	index := 0
	for head != nil {
		if head.Val == target {
			return index
		}
		head = head.Next
		index++
	}
	return -1
}