Data Structure Array & Tuple

박상영·2020년 6월 8일
0

Data Structure

Data Structure란?

  • 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조직하는 방법

  • 자료구조의 종류에는 여러가지가 있다. 하지만 모든 목적에 부합하는 자료구조 또한 없습니다.
    각각의 자료구조가 갖는 장점과 한계를 이해하고 상황에 맞게 올바른 자료 구조를 선택하고 사용하는것이 중요하다

  • 자료구조는 언어별로 지원하는 양상이 다르다

  • 각 언어가 가진 자료구조의 종류와 그것에 대한 사용 방법을 익히는것이 중요하지만, 무엇보다 각 자료구조의 본질과 컨셉을 이해하고 상황에 맞는 적절한 자료구조를 선택하는 것이 중요

왜 Data Structure 를 사용할까?

  • 자료구조는 상황과 문맥에 맞게 데이터를 담을 수 있는 적절한 구조를 말합니다.
    실생활에서 상황에맞는 도구를 찾는것처럼

  • 데이터에 맞는 적절한 자료구조를 사용하는 것은 전체 개발 시스템에 큰 영향을 끼친다.

자료 구조의 분류

  • Primitive Data Structure(단순 구조)
    프로그래밍에서 사용되는 기본 data type

  • None-Primitive Data Structure(단순하지 않은 구조)
    단순한 데이터를 저장하는 구조가 아닌 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료구조

  • Linear Data Structure(선형 구조)
    저장되는 자료의 전후 관계가 1:1 (List, Stacks, Queues)

  • Non-Linear Data Structure(비선형 구조)
    데이터 항목 사이의 관계가 1:n 또는 n:m (Graphs, Trees)

일반적으로 가장 자주 사용 되는 자료 구조

  • Array(python -> List)

  • Tuple

  • Set

  • Dictionary

  • Stack & Queue

  • Tree

Array(python -> List)

  • Array(List)는 가장 기초적이고 단순하면서도 가장 자주 사용 되는 자료 구조

Array 특징

  • 자료구조에 저장하는 데이터는 일반적으로 요소(element)라고 한다.

  • Array는 주로 서로 연결된 데이터들을 순차적 으로 저장할때 사용

  • 순서가 상관 없더라도 서로 연결된 데이터들을 저장할때 일반적으로 사용

  • insertion(삽입) 순서대로 저장한다.

  • 이미 생성된 Array(List)도 수정가능

  • 동일한 값도 여러번 insert 가능

  • Multi-dimensional Array(다중차원 배열)
    Array의 element 가 array가 될수있다.(result = [[1, 2, 3], [4, 5, 6], [7, 8, 9]])

Array 의 내부 구조

  • 순차적으로 데이터를 저장하기때문에 순차적으로 번호(index)를 지정할수있다.

  • index는 0부터 시작되고, 마이너스 부호(-) 를 가질수도 있다.
    마이너스 부호가 붙으면 맨 마지막element 부터 시작한다. 마이너스 부호는 result[0][-1] == 3 처럼 "-1" 부터 시작한다.

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

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

1) index가 존재하며 0부터 시작하는 index

2) index를 사용해 특정 요소를 array(list)로 부터 읽어들이는것이 가능(indexing)

3) 요소의 특정 부분, n번째 index부터 m번째 index까지 따로 분리해 조작하는것이 가능(Slicing)

Array의 단점

1. Removing or Adding Elements

  • 순차적으로 담겨있는 데이터 중 특정 위치에 있는 중간의 요소가 삭제되는 경우에 항상 메모리가 순차적으로 이어져있어야 하기 때문에, 삭제된 요소로 부터 뒤에 있는 모든 요소들을 앞으로 한칸씩 이동시켜야한다.

  • 위에 말한것을 실행하기때문에 다른 자료 구조에 비해 느릴수있다.

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

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

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

2. Array Resizing

  • Array는 메모리가 순차적으로 채워지기때문에 배열이 처음 생성될 때 어느 정도 메모리를 미리 할당한다.(pre-allocation)

  • 메모리를 pre-allocation 함으로써 새로 추가되는 요소들도 순차적으로 메모리에 저장될 수 있다. 하지만 요소들이 처음 할당된 메모리 이상으로 많아진다면 Resizing이 필요하다.(메모리 추가 할당)

  • Array는 사이즈 예측이 안되는 데이터를 다루기에는 적절치 않다.

  • 일반적으로 대부분의 언어에서는 배열의 메모르 pre-allocation과 resizing을 자동실행한다.

언제 사용하면 적절할까

  • 순차열적인 데이터를 저장할 때

  • 다차원 데이터를 다룰 때(Multi-dimensional Array)

  • 어떠한 특정 요소를 빠르게 읽어야 할 때(index를 통해 바로 읽기 가능)

  • 데이터의 사이즈가 급변하게 자주 변하지않을 때

  • 요소가 자주 삭제 되거나 추가되지 않을 때

Tuple

  • List와 마찬가지로 데이터를 순차적으로 저장할 수 있는 순열 자료구조

  • 한번 정의되면 수정할수없다

  • 2~3개 정도의 적은 수의 소규모 데이터를 저장할 때 많이 사용

  • 함수에서 리턴 값을 한 개 이상 리턴하고 싶을때 자주 사용

Tuple의 장점

  • 간단한 값을 빨리 표현하고 싶을 때 많이 사용
    ex) 함수에서 리턴 값을 한 개 이상 리턴하고 싶을 경우(지도 좌표...etc)

Tuple의 단점

  • 데이터가 무슨 의미인지 명확하지 않다.

  • 데이터의 의미를 문맥을 보고 가정해야한다.

언제 사용하면 적절할까

  • Array(List) 를 쓰기엔 간단한 데이터를 표현할 때 사용
    Tuple이 Array보다 더 가볍고 메모리를 더 적게 사용
cordinations = [
    (1, 2),
    (3, 4),
    (5, 6)
]
profile
backend

0개의 댓글