数组

实现数组的基本数据结构

  • 数组的基本数据结构的实现
  • 插入,删除, 更新

思路

数组是一系列连续的数据集合,有固定的长度和下标,根据下标访问查找时间复杂度O(1),删除时间复杂度也是O(1)。

实现目标

  • 使用Go语言实现基本的数组数据结构
  • 通过Go实现数组的基本操作

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
package array

import (
"errors"
"fmt"
)

type Array struct {
data []int
length int
}

func NewArray(capcity int) *Array {
if capcity <= 0 {
return nil
}

return &Array{
data: make([]int, capcity, capcity),
length: 0,
}
}

func (self *Array) IsOutOfRange(index int) bool {
if index < 0 || index >= cap(self.data) {
return true
}

return false
}

func (self *Array) Len() int {
return self.length
}

// find specfic data index value
func (self *Array) FindIndexByData(data int) int {
for index, value := range self.data {
if value == data {
return index
}
}

return -1
}

func (self *Array) FindDataByIndex(index int) (int, error) {
if self.IsOutOfRange(index) {
return -1, errors.New("Out of range when find")
}

return self.data[index], nil
}

// Delete elements by sepecific value
func (self *Array) Delete(index int) (int, error) {
if self.IsOutOfRange(index) {
return -1, errors.New("Out of range when delete!")
}

v := self.data[index]

for i:=index; i< self.Len() - 1; i++ {
self.data[i] = self.data[i] + 1
}

self.length--

return v, nil
}

func (self *Array) Insert(index int, data int) (bool, error) {
if self.IsOutOfRange(index) {
return false, errors.New("Out of range when insert")
}

if self.Len() == cap(self.data) {
return false, errors.New("Capcity is full when insert")
}

for i := self.length-1; i >= index ; i-- {
fmt.Println("Insert: ", self.data, i, index)

self.data[i] = self.data[i-1]
}

self.data[index] = data

self.length++

return true, nil
}

func (self *Array) Append(data int) (bool, error) {

if self.Len() == cap(self.data) {
return false, errors.New("Capcity is full when insert")
}

return self.Insert(self.length, data)
}

func (self *Array) Prepend(data int) (bool, error) {
if self.Len() == cap(self.data) {
return false, errors.New("Capcity is full when insert")
}

return self.Insert(0, data)
}

func (self *Array) Print() {
var formatString string
for i :=0; i < self.length; i++ {
formatString += fmt.Sprintf("|%+v", self.data[i])
}

fmt.Println(formatString)
}