Data Structure(자료 구조)란?

• 자료 구조란 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조직하는 방법이다.
• 자료 구조의 종류에는 여러가지가 있다. 하지만 모든 목적에 부합하는 자료구조는 없다. 따라서 각각의 자료구조가 갖는 장점과 한계를 잘 이해하고 상황에 맞게 올바른 자료 구조를 선택하고 사용하는 것이 중요하다.
• 각 언어가 가진 자료구조의 종류와 그것에 대한 사용 방법을 익히는 것이 중요하지만, 무엇보다 각 자료구조의 본질과 컨셉을 이해하고 상황에 맞는 적절한 자료 구조를 선택하는 것이 중요하다.

Array

Array 특징

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

• Array의 가장 큰 특징은 순차적(ordered)으로 데이터를 저장한다는 점이다.
• 자료구조에 저장하는 데이터는 일반적으로 요소(element)라고 한다.).
• Array는 주로 서로 연결된 데이터들을 순차적 으로 저장할때 사용한다.
• 순서가 상관 없더라도 서로 연결된 데이터들을 저장할때 일반적으로 사용된다.
• 그래서 array가 가장 자주 사용되는 자료구조중 하나가 되는 것이다.

기타 특징

• 삽입(insertion) 순서대로 저장된다. (즉, 새로 삽입되는 요소는 array의 새로운 꼬리가 된다.)
• 이미 생성된 리스트도 수정 가능(mutable).
• 동일한 값도 여러번 삽입 가능
• Multi-dimensional Array(다중차원 배열)
  • Array의 요소가 array가 될 수 있다. 이러한 array를 다중차원(multi-dimensional) array라고 한다. 일반적으로 2D (2차원) array가 많이 사용된다.
    

Array 내부 구조

• Array의 가장 큰 특징은 순차적으로 데이터를 저장하는 것이다.
• 이렇게 순서가 있다보니 당연히 순차적으로 번호를 지정할 수 있다. 마치 학교에서 이름을 부르지 않고 번호를 불르는 것과 동일한 개념이다. 이 번호를 index 라고 한다.
• Index는 0부터 시작된다. Index는 마이너스 부호를 가질 수 도 있습니다. 마이너스 index는 맨 마지막 요소 부터 시작합니다. 예를 들어, -1 은 맨 마지막 요소이다.

그렇다면 왜 Array가 순차적으로 데이터를 저장할 수 밖에 없을까?

• 그건 바로 실제 메모리 상에서, 즉 물리적으로 데이터가 순차적으로 저장되기 때문이다.

• 데이터에 순서가 있기 때문에

  • 1) index가 존재하며
    : 0부터 시작하는 index
  • 2) Indexing
    : Index를 사용해 특정 요소를 array(list)로 부터 읽어 들이는 것이 가능하고
  • 3) Slicing
    : 요소의 특정 부분, 즉 n번째 index부터 m번째 index까지 따로 분리해 조작하는 것이 가능하다.

    Array 단점

    1. Removing or Adding Elements

• 중간의 특정 요소를 삭제해야 하는 경우를 가정해보자.

• 순차적으로 담겨있는 데이터 중 특정 위치에 있는 중간의 요소가 삭제 되는 경우에,

• 항상 메모리가 순차적으로 이어져있어야 하기 때문에, 삭제된 요소로 부터 뒤에 있는 모든 요소들을 앞으로 한칸씩 이동시켜주어야 한다.

• 이뜻은 배열에서 요소를 삭제하는 것은 다른 자료 구조에 비해 느릴 수 있다는 뜻이다.

• 요소를 삭제하는 과정이 코드 상에서는 한 줄 이지만 실제 메모리 상에서 이루어지는 작업(operation)은 훨씬 커진다.(expensive operation)

• 중간에 요소가 추가 되는 경우도 마찬가지이다. 특정 위치에 새롭게 요소가 추가되는 경우에는 그 뒤의 요소들이 하나씩 밀리게 된다.

• 그렇기 때문에 Array 는 정보가 자주 삭제 되거나 추가되는 데이터를 담기에는 적절치 않다.

적절한 상황

• 순차열적인 데이터를 저장할 때
  • ex) 주식 가격. 어제의 2만원과 오늘의 2만원이 다름 >>> 값보다는 순서가 중요한 데이터
• 다차원 데이터를 다룰 때 >>> Multi-dimensional Array
• 어떠한 특정 요소를 빠르게 읽어야 할 때 >> index를 통해 곧바로 읽을 수 있기 때문
• 데이터의 사이즈가 급변하게 자주 변하지 않을 때
• 요소가 자주 삭제 되거나 추가되지 않을 때