[DataStructure] Array/List

긴급 노선변경!!!!!

JAVA와 친해지겠다고 JAVA로 공부한다고 까불다가... 혼쭐났습니다...

이후 블로깅은 python을 기준으로 블로깅합니다! ㅎㅎ

Array

순차적으로 데이터를 저장하는 자료구조

• Array의 가장큰 특징은 순차적(ordered)으로 데이터를 저장한다는 것 입니다.
  - 순서가 있다 = indexing & slicing이 가능하다
• Array는 주로 서로연결된 데이터들을 순차적으로 저장할때 사용합니다.
• 순서가 상관없더라도 연결된 데이터들을 저장할때 일반적으로 사용됩니다.
• 메모리상에서도 순차적으로 저장됩니다.(차후 나올 LinkedList와 차이점)

기타 특징

• 삽입(insertion) 순서대로 저장됩니다.(새로 삽입되는 요소는 array의 새로운 tail이 됩니다)
• Array는 수정이 가능합니다 (mutable)
• 동일한 값도 여러번 삽입이 가능합니다(중복을 허용합니다)
• Multi-dimensional Array(다중차원 배열)(python에서 2차원 list라고 표현)
  - Array의 요소가 array로 구성된 Array (일반적으로 2D array가 많이 사용됩니다.)
  
  

Array 내부 구조

 

• 순서가 있으니 순차적으로 번호를 지정할 수 있습니다.아래 나와있는 번호들을 index라고 부릅니다.
• index는 0 부터 양수로 진행되지만 음수일 수 있습니다(음수일때는 맨마지막 요소 부터시작합니다.)
  - ex) -1은 맨마지막 요소 , -3은 마지막에서 3번째 요소
• 이전에 언급했듯이 그림과같이 메모리상에서도 순차적으로 저장됩니다(물리적으로 데이터가 순차적으로 저장)

Array가 순차적으로 데이터를 저장할 수 밖에 없는 이유

• 앞서 설명하였듯이 실제 메모리상에 물리적으로 데이터가 순차적으로 저장되기 때문이다.
• 데이터에 순서가있기에 다음 사항들이 가능하다
  - indexing : index를 사용해 특정 요소를 array로 부터 읽어 들이는것
  - Slicing : 요소 특정 index부터 특정 index까지 따로 분리해 조작하는것이 가능하다 

단점

단점이되는 예시를 몇개 들어보려고합니다.

Removing or Adding Elements

• 중간에 요소가 삭제되는경우 해당요소 보다 뒤에있는 요소들을 앞으로 위치를 이동시켜줘야합니다(shift라고표현함)
  - 항상 메모리는 순차적으로 이어져야 하기 때문에!
• 즉 배열에서 요소를 삭제하는것은 다른 자료구조에 비해 느릴 수 있다는 뜻이다.
• 요소를 삭제하는 코드는 한줄이지만 실제 메모리상에서 이루어지는 작업(operation)은 훨씬 커집니다(expensive operation)
• 중간에 요소를 추가하는것 역시 같은일이 일어납니다(추가시에는 좌시프트가 일어납니다)
• 그렇기에 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절치 않을 수 있습니다.

Array Resizing

• Resizing이란, 말 그대로 사이즈를 다시 조정한다는 뜻
• 배열은 메모리가 순차적으로 채워지기 때문에 배열이 처음 생성될때 어느정도 메모리를 미리 할당합니다.
• 이를 전문용어로 pre-allocation이라고 하는데 이로인해 추가되는 요소들도 순차적으로 메모리에 저장할 수 있습니다.
• 하지만 요소들이 처음 할당한 메모리 이상으로 많아진다면 resizing을 하게됩니다.
• 이때 일어나는 일을 아래에 설명해보겠습니다
  - 100개의 메모리 공간이 다 차서 100개를 추가해야되는경우
  - 200개 크기의 메모리를 생성 > 기존의 100개를 복사 > 그다음 101번부터 순차적으로 추가
  - 원래 있던 배열을 새로운 배열안에 집어넣는 대공사를 하게 됩니다.
• 그렇기에 Array는 사이즈 예측이 잘안되거나 변동성이 큰 데이터를 다루기에는 적절치 않습니다.
• 일반적으로 대부분의 언어에서는 pre-allocation과 resizing을 자동으로 실행합니다.

그렇다면 Array는 언제 사용해야 할까!?

• 순차적으로 데이터를 저장할때(순서가 중요할때)
• 다차원 데이터를 다룰 때  -  Multi-dimensional Array
• 어떠한 특정 요소를 빠르게 읽어야 할 때 >> index를 통해 곧바로 읽을 수 있기 때문
• 데이터의 사이즈가 급변하게 자주 변하지 않을 때
• 요소가 자주 삭제되거나 추가되지 않을때

실사용 예