[데이터 구조 원리 와 응용 (Golang 설명)] ① 배열

                                                  .-.          .- 
                             .-,.--..-,.--.        \ \        / / 
                        __   |  .-. |  .-. |   __   \ \      / /  
                     .:--.'. | |  | | |  | |.:--.'.  \ \    / /   
                    / |   \ || |  | | |  | / |   \ |  \ \  / /    
                    `" __ | || |  '-| |  '-`" __ | |   \ `  /     
                     .'.''| || |    | |     .'.''| |    \  /      
                    / /   | || |    | |    / /   | |_   / /       
                    \ \._,\ '|_|    |_|    \ \._,\ '|`-' /        
                     `--'  `"               `--'  `" '..'   

Golang
Online Go tutorial
1.1 원리
배열 (Array) 은 선형 표 데이터 구조 로 메모리 에 연속 적 인 저장 공간 을 신청 하여 같은 유형의 데 이 터 를 저장 하 는 데 사용 된다.
배열 을 제외 하고 링크, 스 택, 대기 열 은 모두 선형 표 구조 이다.
아래 표 에 따라 무 작위 접근 을 실현 하 다
컴퓨터 는 모든 메모리 셀 에 주 소 를 할당 한 다음 이 주 소 를 통 해 메모리 의 데 이 터 를 방문 합 니 다. 배열 의 요 소 를 방문 할 때 다음 주소 지정 공식 에 따라 접근 합 니 다.
$$ a[i]\_address = base\_address + i * data\_type\_size $$
그 중 $a [i] \address $a [i] 의 주 소 를 표시 합 니 다. $base \address $는 컴퓨터 가 할당 한 배열 의 주 소 를 표시 합 니 다. $data \type\_size $는 배열 의 모든 요소 의 크기 를 표시 합 니 다. 데이터 형식 이 정형 int 라면 $data \type\_size $는 4 바이트 와 같 습 니 다.
1.2 관련 조작 과 분석
끼어들다
배열 의 k 번 째 위치 에 데 이 터 를 삽입 하려 면 배열 의 k ~ n 위치 이 부분의 요 소 를 뒤로 옮 겨 야 합 니 다.

배열 끝 에 요 소 를 삽입 하면 데 이 터 를 이동 할 필요 가 없습니다. 가장 좋 은 시간 복잡 도 는 $O (1) $

입 니 다.

배열 의 머리 에 요 소 를 삽입 하려 면 전체 배열 을 옮 겨 야 합 니 다. 최 악의 시간 복잡 도 는 $O (n) $

입 니 다.

우리 가 배열 의 모든 위치 에 요 소 를 삽입 할 확률 이 같다 고 가정 하면 평균 시간 복잡 도 는 $(1 + 2 +... n) / n = O (n) $

이다.
삭제
삽입 데이터 와 유사

가장 좋 은 상황 시간 복잡 도 는 $O (1) $

최 악의 경우 시간 복잡 도 는 $O (n) $

평균 상황 시간 복잡 도 는 $O (n) $

1.3 사고

왜 대부분의 프로 그래 밍 언어 에서 데 이 터 는 1 부터 가 아니 라 0 부터 번 호 를 매 겨 야 합 니까?

배열 과 링크 의 차이 점 은?

프로 그래 밍 에서 배열 을 직접 사용 합 니까? 프로 그래 밍 언어 로 제공 하 는 용기 류 (예 를 들 어 자바 의 Array List, C + STL 에서 Vector) 를 사용 합 니까? 용기 류 는 어떤 우열 이 있 습 니까?

* JVM 의 태그 제거 쓰레기 회수 알고리즘 원리 와 배열 의 관 계 를 알 아 보 시 겠 습 니까?

* 산 목록 의 원리, 산 목록 의 조회 시간 복잡 도?

1.4 LeetCode 연습

두 수의 합

삼 수의 합

다음 줄

나선 행렬

1.5 단순 실현

package main

import "fmt"

type Array interface {
    Get(i int) interface{}
    Set(i int, element interface{})
    Len() int
    Remove(i int)
    Insert(i int, element interface{})

    //     ，  
    Print()
}

type array struct {
    data []interface{}
}

func (a *array) Print() {
    fmt.Println(a.data)
}

func (a *array) Get(i int) interface{} {
    return a.data[i]
}

func (a *array) Set(i int, element interface{}) {
    a.data[i] = element
}

func (a *array) Len() int {
    return len(a.data)
}

func (a *array) Remove(i int) {
    for ; i < a.Len() - 1; i++ {
        a.data[i] = a.data[i+1]
    }
    a.data = a.data[:a.Len()-1]
}

func (a *array) Insert(i int, element interface{}) {
    a.data = append(a.data, 0)
    for j:= a.Len()-1; j > i; j-- {
        a.data[j] = a.data[j-1]
    }
    a.data[i] = element
}

func NewArray(n int) Array {
    return &array{data: make([]interface{}, n)}
}

func main() {
    //     
    arr := NewArray(3)
    arr.Set(0, "hello")
    arr.Set(1, "world")

    fmt.Println(arr.Get(0))
    arr.Print()

    arr.Insert(0, "mike")
    arr.Print()

    arr.Remove(3)
    arr.Print()

}