04-静态链表实现

type StaticLinkedListNode struct {
	Next   int
	Data   any
	isHead bool
}

type StaticLinkedList struct {
	head     []*StaticLinkedListNode
	length   int
	capacity int
	//isCircular bool
	gcPool map[int]any // store deleted  element index, and reuse it in InsertByIndex func
}

// 初始化
func NewStaticLinkedList(cap int) (l *StaticLinkedList) {
	list := new(StaticLinkedList)
	list.capacity = cap
	list.gcPool = make(map[int]any)
	list.head = make([]*StaticLinkedListNode, 1, cap+1)
	list.head[0] = &StaticLinkedListNode{
		Next:   0,
		isHead: true,
	}

	return list
}

// 清空线性表中的数据
func NewStaticLinkedList(cap int) (l *StaticLinkedList) {
	list := new(StaticLinkedList)
	list.capacity = cap
	list.gcPool = make(map[int]any)
	list.head = make([]*StaticLinkedListNode, 1, cap+1)
	list.head[0] = &StaticLinkedListNode{
		Next:   0,
		isHead: true,
	}

	return list
}

func (s *StaticLinkedList) IsEmpty() bool {
	return s.length == 0
}

func (s *StaticLinkedList) GetLength() int {
	return s.length
}

// 获取线性表中位于指定索引的元素
func (s *StaticLinkedList) GetElementByIndex(index int) (any, error) {
	if index >= s.length || index < 0 {
		return nil, fmt.Errorf("index out of range")
	}

	var curr = 0
	for i := 0; i <= index; i++ {
		curr = s.head[curr].Next
	}

	return s.head[curr].Data, nil
}

// 获取线性表中与指定值相等元素的索引
func (s *StaticLinkedList) GetElementIndexByValue(element any) (int, error) {
	var curr = s.head[0].Next

	for i := 0; i < s.length; i++ {
		if s.head[curr].Data == element {
			return i, nil
		}
		curr = s.head[curr].Next
	}

	return 0, fmt.Errorf("can't find element %s in data", element)
}

// 获取线性表中与指定值相等元素的前一个元素
func (s *StaticLinkedList) GetPriorElement(element any) (any, error) {
	var previous, current = 0, 0

	for i := 0; i < s.length+1; i++ {
		if i == 0 { // skip head node
			previous = current
			current = s.head[current].Next
			continue
		}

		if s.head[current].Data == element {
			if i == 1 {
				return 0, fmt.Errorf("element %s has been found， but it's already the first element", element)
			}
			return s.head[previous].Data, nil
		}

		previous = current
		current = s.head[current].Next
	}

	return 0, fmt.Errorf("can't find element %s in data", element)
}

// 获取线性表中与指定值相等元素的后一个元素
func (s *StaticLinkedList) GetNextElement(element any) (any, error) {
	var current = 0

	for i := 0; i < s.length+1; i++ {
		if i == 0 { // skip head node
			current = s.head[current].Next
			continue
		}

		if s.head[current].Data == element {
			if i == s.length {
				return 0, fmt.Errorf("element %s has been found, but it's already the last element", element)
			}

			nextIndex := s.head[current].Next
			return s.head[nextIndex].Data, nil
		}

		current = s.head[current].Next
	}

	return 0, fmt.Errorf("can't find element %s in data", element)
}

// 在线性表中指定索引处插入元素
// InsertByIndex you can insert element into the list, between head and tail, or you will get over range error
func (s *StaticLinkedList) InsertByIndex(index int, element any) error {
	if index >= s.length+1 || index < 0 {
		return fmt.Errorf("index is out of range")
	}

	// if new length great than cap, just return err
	if s.length+1 > s.capacity {
		return fmt.Errorf("new length can't longer than capacity")
	}

	var previous = 0
	var curr = 0
	for i := 0; i <= index; i++ {
		previous = curr
		curr = s.head[curr].Next
	}

	node := &StaticLinkedListNode{
		Data: element,
	}

	gcIndex := -1
	if len(s.gcPool) > 0 {
		for gcIndex = range s.gcPool {
			break
		}
	}

	realIndex := s.length + 1 // default there isn't gc element
	if gcIndex >= 0 {
		realIndex = gcIndex // There is gc element, set to real index
		s.head[gcIndex] = node
		delete(s.gcPool, gcIndex)
	} else {
		s.head = append(s.head, node) // There isn't gc element
	}

	s.head[previous].Next = realIndex
	s.head[realIndex].Next = curr

	s.length += 1

	return nil
}

// 获在线性表中指定索引处删除元素
// DeleteByIndex you can delete element by index, between head and tail, or you will get over range error
func (s *StaticLinkedList) DeleteByIndex(index int) (deletedElement any, err error) {
	if index >= s.length || index < 0 {
		return nil, fmt.Errorf("index is out of range")
	}

	var previous, curr = 0, 0
	for i := 0; i <= index; i++ {
		previous = curr
		curr = s.head[curr].Next
	}

	deletedElement = s.head[curr].Data
	s.gcPool[curr] = deletedElement
	s.head[previous].Next = s.head[curr].Next

	s.length -= 1

	return deletedElement, nil
}

// 遍历打印所有元素
func (s *StaticLinkedList) Traverse(f func(data any)) {
	current := s.head[0].Next
	for i := 0; i < s.length; i++ {
		f(s.head[current].Data)
		current = s.head[current].Next
	}
}