[Contiguous data structures] List

basics

C++ 을 사용하기에 앞서 C++을 사용한 Object Oriented Programming이 어떤 것이고 쓰면 뭐가 좋은지 살펴본다.
OOP는 data 와 operation(method)를 하나로 묶어서 구조체 형태로 사용하는데 이를 ADT라고 한다. 학생 데이터 베이스에 학생 정보만 있는게 아니라 학생 정보를 관리할 동작(추가, 삭제 등)을 하나로 보는 것이다.

ADT(Abstract Data Type)

어떻게 해야 사용할 수 있을 지가 아니라 어떤 기능을 사용할 수 있을 지 알려주기 위한 구조

Tell what the program must do, but not how

• Information hiding

  public interfaces/methods만을 통해 데이터에 접근할 수 있으므로 접근 제어 가능

• encapsulation

  • Data + Operation

구현과 독립되어 명시된 자료 구조로 요소의 조직, 관리, 저장 방식을 정의한다. 사용자의 관점에서 접근과 수정이 훨씬 쉬워진다.
-> 시스템 사용자 관점에 필수적인 구조!

ADT basic operations

• Constructor : a new instacne_default is parameterless
• Transformer :

  append
  insert
  remove
  update
  clear

• Observer : the state of the data

  size
  isFull
  find
  getItem

Abstraction

구현으로부터 논리적 특성을 분리했다. = values와 operation만 생각한다.
예를 들면, 학생 이름(value)를 한 번에 관리하려면 추가 기능(add)이 필요하겠군 이렇게만 생각하고 어떤 data type, 내부 논리(this -> name), 메모리 관리 등은 고려하지 않아도 된다는 것이다.

---

Data Structure

자료 구조를 배우는 이유는, 데이터를 저장, 검색하려면 그에 맞는 구조가 필요하기 때문이다. 밑에서도 볼 거지만 데이터 배치 방법에 따라 저장, 검색에 사용되는 시간 복잡도가 다르다.

Time Complexity: Estimate the number of computations of the worst case to find more efficient algorithms.

Composite Data Type - Object

우리는 변수 하나에 여러 개의 값을 담은 Composite data type(Object)을 사용할 거다. Object를 사용하면 타입이 다른 데이터를 하나로 묶을 수도 있고 그리고 각 데이터 요소에 접근해서 사용할 수도 있다. 이렇게 정의해놓으면 같은 타입을 갖는 여러 변수 할당에 효율적이고 parameter로도 사용할 수 있다.

• Class
• Struct

  Class, Struct 비슷한 느낌인데 Struct는 구조체 내부에 연산을 정의할 수 없다.

---

Linear Structure

One-Dimensional Array - Contiguous type

A composite data type made up of a fixed-size collection of homogeneous elements.

Direct Access using indexes
연속된 자료구조에서는 원소가 모두 같은 타입을 사용한다. 같은 타입이므로 같은 크기의 메모리를 사용하기에 시작 주소만 있으면 원소의 위치를 메모리 주소로 나타낼 수 있다. 데이터 접근 시간이 O(1)이다. 원소의 위치로 이동하려면 ++, -- 로 이동하므로 중간에 원소를 삽입하는 경우엔 O(n)을 가진다.

| Addess[idx] = Base_Address + idx * sizeofelement

Two_Dimensional Array

1차원이 두 개 있는 2차원이다. 데이터 타입 같고, 사이즈도 고정되어 있는데 다른 점은 a pair of indexes[row][col]을 이용한다는 것이다.

array

array(type, size)

원소 접근 방법 중에 data()를 이용해 포인터 연산도 가능하다. data()는 실제 데이터 메모리 버퍼를 가리키는 포인터를 반환한다.

arr = {1,2,3,4,5};

cout << *(arr.data() + 1 ) << endl; // print 2

| 어레이에 관계 연산자를 사용할 경우, 두 배열의 크기가 같아야 한다. array는 크기를 데이터 타입의 일부로 가지기 때문에 크기가 다른 array는 다른 타입으로 인식한다.

List vs. Array

List contains ADT variables
Array needs concrete data type like size and variable types.