지혜의 개발공부로그

Data Structure, Array

10 Jan 2020 | Data Structure

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
잘못된 부분이 있다면 댓글로 남겨주세요! :)

Array

동일한 데이터를 index를 활용하여 저장, 접근할 수 있는 것

  • 각 요소들에게는 index가 붙어져 있어야 한다.
  • 배열의 길이만큼은 순회한다.
  • 배열안 데이터의 유/무를 알아보기 위해서는 최소한 N회 루프를 돌아야한다.

Insert procedure in array

  1. 새로 들어갈 데이터가 포함된 공간을 생성
  2. 레퍼런스 카피 > 저장할 공간 직전까지
  3. 새로 만든 공간에 추가하고 싶은 데이터 저장
  4. 이전의 레퍼런스 카피해서 연결
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

  1. 하나 줄어든 길이의 저장공간을 만든다.
  2. 삭제하려고 하는 이전 값들은 그대로 카피한다.
  3. 없애는 operation은 아무것도 안한다.
  4. 삭제할 위치의 +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차원 적인 선형 공간이 아니기 때문에 더이상 배열이라고 할수가 없다.
즉, 선형 공간을 그대로 유지한다면 공간을 만드는게 불가능하다.

Related Posts