Data Structure, Array
10 Jan 2020 | Data Structure개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
잘못된 부분이 있다면 댓글로 남겨주세요! :)
Array
동일한 데이터를 index를 활용하여 저장, 접근할 수 있는 것
- 각 요소들에게는 index가 붙어져 있어야 한다.
- 배열의 길이만큼은 순회한다.
- 배열안 데이터의 유/무를 알아보기 위해서는 최소한 N회 루프를 돌아야한다.
Insert procedure in array
- 새로 들어갈 데이터가 포함된 공간을 생성
- 레퍼런스 카피 > 저장할 공간 직전까지
- 새로 만든 공간에 추가하고 싶은 데이터 저장
- 이전의 레퍼런스 카피해서 연결

x = ['a', 'b', 'c', 'd', 'e', 'f']
idxInsert = 2
valInsert = 'c'
y = range(6)
for i in range(0, idxInsert):
y[i] = x[i]
y[idxInsert] = valInsert
for i in range(idxInsert, len(x)):
y[i+1] = x[i]
x=y
y에 새로운 리스트가 만들어졌으니 x=y
를 함으로써 y의 배열(레퍼런스)구조를 x에 저장!
그렇다면 몇번의 operation이 필요했는가?
array를 이용해 무언가를 넣을때는 n번 의 operation이 필요하다.
Delete procedure in array
- 하나 줄어든 길이의 저장공간을 만든다.
- 삭제하려고 하는 이전 값들은 그대로 카피한다.
- 없애는 operation은 아무것도 안한다.
- 삭제할 위치의 +1 값은 -1해준 위치에서 저장한다.

idxDelete = 3
y = range(5)
for i in range(0, idxDelete):
y[i] = x[i]
for i in range(idxDelete+1, len(x)):
y[i-1] = x[i]
x=y
array를 이용해 무언가를 넣을때는 n-1번 의 operation이 필요하다.
Problem in Array
- 무엇이든지 넣거나 뺄때 N개의 검색이 필요하다.
- 즉 배열을 처음부터 끝까지 다 건들여야 insert, delete가 가능하다는 의미이다.
현실적으로 불가능.
어떤 마법이 있어서 줄 사이에 데이터가 들어갈만한 공간이 자동으로 만들어진다면?
배열 중간에 공간을 만들면 되지만 이는 1차원 적인 선형 공간이 아니기 때문에 더이상 배열이라고 할수가 없다.
즉, 선형 공간을 그대로 유지한다면 공간을 만드는게 불가능하다.