CH3. 연결 리스트 (Linked list) 1-1

3-1 추상 자료형: Abstract Data Type

ADT와 자료구조의 관계
- 자료구조의 일부는 아님
- 단순히 code를 떠나 공학적 측면에서 관련되어있음

컴퓨터 공학에서의 추상 자료형 (Abstract Data Type)

추상 자료형은 ADT라고도 불리나 실제 의미상 약간의 차이가 있는 것처럼 느껴질 수 있음
이는 실제 의미에서 조금 확장된 의미로 사용되기 때문이며 실제 차이를 보이는것이 아님
- 즉, 큰 맥락선에선 하나이며 다만 이를 나타내는 형태에서 차이가 나는 것임
본 책에서는 자료구조의 관점에서 ADT를 다룸

자료구조에서의 추상 자료형

지갑에서 동전을 넣고 빼는 등 지갑이 제공하는 기능들의 행위의 묘사
- 동전을 넣고 빼는 자세한 과정이 생략되어 있음 (지갑을 연다던가..)
이처럼 구체적인 기능의 완성과정을 언급하지 않고 순수하게 기능이 무엇인지를 나열한 것 을 가리켜 추상 자료형(ADT)라고 함
(추상)자료형 = 기능 (그 기능이 어떻게 동작하는가에 대해 나열하지 않는 것이 추상 자료형)
- 예를 들어 지갑의 기능을 나열하면 아래와 같음
  - 카드의 삽입 추출
  - 동전의 삽입 추출
  - 지폐의 삽입 추출
즉, 기능을 나열 하되 그 과정을 언급하지 않음
기능의 명세를 가리켜 왜 자료형(data type)이라 하는것이 왜 포함되는지에 대해 알아보면?
- int라는 자료형을 생각하면 보통 data를 생각함
  - int라는 데이터는 어떻게 생겼나?
  - int의 기능적 측면으로 본다면 선언, 연산, 초기화 할 때 연산자 를 사용함
  - 하지만 데이터적 관점에서는 자세히 알 수 없음
- 보통 자료형을 이야기 할 때는 그 기능을 중시 여김
  - 자료형이라 하는것은 연산에 훨씬 더 그 의미가 있음
- 구조체의 정의 또한 자료형의 정의이나, 기능을 제공하나?
C에서 코딩이라는 것은?
- 구조체를 정의하고, 더불어 함수도 같이 정의한다(구조체 정의) 그러고 나서 함수를 정의한다.
- 구조체를 정의하고(Data) 그와 관련된 연산을 정의
예시를 들기 위해 구조체를 이용하여 지갑을 정의

typedef struct_wallet
{
  int coin100Num;
  int bill5000Num;
} Wallet;

위처럼 c를 기반으로 구조체를 정의하는 것은 구조체를 기반으로 지갑을 의미하는 Wallet 자료형을 정의하는것
하지만 컴퓨터공학 측면에서 위의 구조체 정의만으로 Wallet이라는 자료형의 정의가 완성되는 것이 아님
- Wallet을 기반으로 하는 연산의 종류를 결정하는 것도 자료형 정의의 일부로 보아야 함
- 이러한 연산의 종류가 결정되었을 때 자료형의 정의가 완성됨
지갑에 대한 예시를 이어 들면 아래와 같음
- Wallet을 기반으로 제공할 수 있는 기능 관련 연산

int TakeOutMoney(Wallet *pw, int coinNum, int billNum); //돈을 꺼내는 연산
void PutMoney(Wallet *pw, int coinNum, int billNum); // 돈을 넣는 연산

이렇듯 C언어에서는 구조체에서 필요로 하는 연산을 함수를 이용해 정의
만약 Wallet 구조체가 필요로 하는 연산이 위의 두 종류가 다라면, 이로써 Wallet에 대한 자료형의 정의가 완성됨
즉, ‘자료형’의 정의에 ‘기능, 연산’과 관련된 내용을 명시할 수 있음
구조체를 정의 할 때, 해당 구조체의 연산을 담당하는 함수를 정의하는것이 중요!
- 구조체를 정의 하고, 그 연산을 담당하는 함수를 정의하는것이 포함되는것이 구조체 정의
예를 들어 int 변수를 선언 할 때, 그에 맞게 연산자가 다 정의된 것이라 여기는것과 동일
- int 변수에 대해 +,-,* 등등.. 모든 연산자가 int 구조체에 알맞게 동작하는 함수가 정의되어 있는 꼴
따라서 자료형의 정의보다, 자료형의 연산을 담당하는 함수의 정의가 더 중요함

구조체 Wallet의 추상 자료형 정의

구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것을 가리켜 ‘추상 자료형’ 또는 ADT라고 한다.
Wallet의 ADT(기능 명세서)
- int TakeOutMoney(Wallet *pw, int coinNum, int billNum);
  - 첫 번째 인자로 전달된 주소의 지갑에서 돈을 꺼냄
  - 두 번째 인자로 꺼낼 동전의 수, 세 번째 인자로 꺼낼 지폐의 수를 전달
  - 꺼내고자 하는 돈의 총액이 반횐되며 그만큼의 돈은 차감됨
- void PutMoney(Wallet *pw, int coinNum, int billNum);
  - 첫 번째 인자로 전달된 주소의 지갑에 돈을 넣음
  - 두 번째 인자로 넣을 동전의 수, 세 번째 인자로 넣을 지폐의 수를 전달
  - 넣은 동전과 지폐의 수 만큼 증가
하지만 ADT에 구지 필요없는 기능을 포함시키는것은 바람직하지 않음
- Wallet 구조체에 동전 및 지폐의 갯수를 반환하는 ADT가 필요한가?
  - 필요 없음. 그냥 구조체의 멤버에 직접 접근하면 됨
한 번에 완벽하게 정의 할 필요가 없음(할 수도 없음). 필요하면 나중에 추가해도 되는 구조.
구조체 Wallet의 정의를 ADT에 포함 시키지 않아도 됨 (웬만해선 포함시키지 않음)

자료구조의 학습에 ADT의 정의를 포함

학습순서
- 1. 리스트 자료구조의 ADT를 정의
    - 기능을 명시한다는 의미
    - 공부 할 때 기능 중심적으로.
- 1. ADT를 근거로 리스트 자료구조를 활용하는 main 함수 정의
    - ADT가 잘 정의되었다면, ADT 리스트의 내부 구조를 몰라도 main에서 잘 쓸 수 있기 때문
    - 즉, ADT를 잘 정의 할 수 있도록 하는 연습하기 위함임
- 1. ADT를 근거로 리스트를 구현
2번과 3번의 순서가 바뀌엇다고 생각 할 수 있지만 ADT의 본질을 이해하는데 방해가 되므로 위의 순서를 따름

3-2 배열을 이용한 리스트의 구현

리스트의 이해

리스트 자료구조는 구현방법에 따라 크게 두 가지로 나뉨
- 순차 리스트: 배열을 기반으로 구현된 리스트 (이번 챕터에서)
- 연결 리스트: 메모리의 동적 할당을 기반으로 구현된 리스트 (다음 챕터에서)
이는 리스트의 구현방법의 차이에서 비롯된 것이기 때문에 ADT가 동일하다고 해서 문제가 되지 않음
- 리스트 자료구조의 기본 기능은 똑같음
- 다만 그 기능을 제공함에 있어서 특성, 성능 등의 차이가 나타남
리스트의 ADT 정의를 위해 리스트 자료구조의 가장 기본적이고 중요현 특성은 다음과 같음
- 저장 형태: 리스트 자료구조는 데이터를 나란히 저장한다
- 저장 특성: 중복된 데이터의 저장을 막지 않는다
위의 특징이 리스트 ADT를 정의하는데 있어서 고려해야 할 유일한 요소
위의 특성을 갖도록 하다 보니 순차/연결 리스트 형태로 구현방법이 나뉘게 됨

리스트 자료구조의 ADT

리스트라는 자료구조가 어떠한 특성을 갖는지, 어떠한 식으로 활용할 수 있는지 알 수 있음
- 구현 방법, 기능의 과정에 대해서는 ADT에 반영되지 않음
- 기존의 방법에도 기본 특성을 지키는 한에서 새로운 기능을 추가/제거 할 수 있음
데이터가 나란히 저장된다는 특성을 기반으로 제공해야 할 기능들을 정의
리스트 자료구조의 ADT (Operations)
- void ListInit(List *plist);
  - 초기화할 리스트의 주소 값을 인자로 전달
  - 리스트 생성 후 제일 먼저 호출되어야 하는 함수
  - C라는 언어 특성 상 변수 선언 후 초기화가 이루어져야 하므로 필요
- void LInsert(List *plist, LData data);
  - 매개변수 data에 전달된 값을 *plist 주소의 리스트에 저장
  - 데이터를 저장하는 역할
- int LFirst(List *plist, LData *pdata);
  - 저장된 데이터들 중 첫 번째 데이터를 반환받아 저장할 때 사용
  - 첫 번째 데이터가 pdata가 가리키는 메모리에 저장됨
  - 데이터의 참조를 위한 초기화가 진행
  - 참조 성공시 TRUE, 실패시 FALSE 반환
- int LNext(List *plist, LData *pdata);
  - LFirst 이후에 두 번째 인자 이후를 얻을 때 호출하며 사용법은 LFirst와 동일
    - 구지 구분짓는 이유는 조회를 처음부터 다시 시작하는 경우등에서 필요하므로(일반적인 패턴)
  - 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장
  - 순차적인 참조를 위해 반복 호출 가능
  - 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 함
  - 참조 성공시 TRUE, 실패시 FALSE 반환
- LData LRemove(List *plist);
  - LFirst 또는 LNext 함수의 마지막(바로 이전) 반환(참조)된 데이터를 삭제
  - 삭제된 데이터는 반환
  - 마지막 반환 데이터를 삭제하므로 연이는 반복 호출 불허
- int LCount(List *plist);
  - 리스트에 현재 저장되어 있는 데이터의 수를 반환
LData는 리스트에 저장할 데이터의 자료형에 제한을 두지 않기 위한 typedef 선언의 결과

리스트의 ADT를 기반으로 정의된 main 함수

리스트의 ADT가 정의되었다는 가정 하에 리스트의 활용 예를 main 함수를 이용해 살펴봄
- 실제로 list가 구현 된 라이브러리가 있다 가정 하고, 그 라이브러리를 기준으로 작성 된 main함수를 살핌
main 함수를 이해 하면 ADT기능을 갖는 함수 각각의 구조를 이해하고 리스트 자체의 이해가 가능해짐
- 함수 내의 LInsert 등의 함수들이 어떻게 구현되어있나보다, 어떻게 쓰이냐에 더 집중해서 학습
- ArrayList.h까지는 열어보고 확인해도 좋지만, ListMain.c를 참고하여 ArrayList.c는 직접 구현해보는편이 좋음
리스트의 초기화

int data;
List list; // 리스트의 생성
ListInit(&list); // 리스트의 초기화

초기화된 리스트에 데이터 저장
- 리스트는 데이터를 나란히, 순서대로 저장함(순서는 무관)

LInsert(&list, 11);  LInsert(&list, 11);
LInsert(&list, 22);  LInsert(&list, 22);
LInsert(&list, 33);

리스트의 데이터 참조 과정
- LFirst를 처음에 호출 하여 첫 번째 데이터 값을 변수 data에 저장
- 리스트에 저장된 숫자 처음부터 끝까지 모두 출력(참조)하는 과정
- LFirst 다음으로 LNext 함수를 호출하는 이유
  - 모든 데이터를 한 번만 참조하고 끝내는 것이면 LNext로만 가능하지만, 데이터의 참조는 자주 일어나고 앞에서부터 참조가 진행되어야 하므로 처음부터 참조를 진행하는 의미를 갖는 LFirst를 별도로 지정함
  - LFirst는 처음 시작을 알리는 용도
- 데이터 참조 일련의 과정
  - LFirst -> LNext -> LNext -> …

if(LFirst(&list, &data))    // 첫 번째 데이터 조회
{
  printf("%d ", data);

  while(LNext(&list, &data))    // 두 번째 이후의 데이터 조회
    printf("%d ", data);
}

리스트의 데이터 삭제 방법
- LRemove 함수는 연이은 호출을 혀용하지 않음
  - 심지어 동작 메커니즘이 불필요한 형태임
- 기본적으로 리스트 자료구조는 하나씩 가져다가 판단을 하는 형태임
  - 즉, LFirst나 LNext 함수로 각각 값을 가져다가 하나씩 비교하고 삭제하는 형태
  - 삭제가 그냥 하는게 아니라 일련의 참조 과정이 포함되어 삭제가 가능한 형태
- 일반적으로 아래와 같은 스타일로 리스트 자료구조가 동작하게 됨

if(LFirst(&list, &data)) // 첫 번째 데이터를 가져와서 data에 저장
{
  if(data == 22) // 만약 가져온 데이터가 22면
    LRemove(&list); // 해당 데이터 삭제

  while(LNext(&list, &data)) // 두 번째 데이터부터 가져와서 data 저장
  {
    if(data == 22) // 만약 가져온 데이터가 22면
      LRemove(&list); // 해당 데이터 삭제
  }
}

Seongkyun Han's blog

CH3. 연결 리스트 (Linked list) 1-1

CH3. 연결 리스트 (Linked list) 1-1

3-1 추상 자료형: Abstract Data Type

컴퓨터 공학에서의 추상 자료형 (Abstract Data Type)

자료구조에서의 추상 자료형

구조체 Wallet의 추상 자료형 정의

자료구조의 학습에 ADT의 정의를 포함

3-2 배열을 이용한 리스트의 구현

리스트의 이해

리스트 자료구조의 ADT

리스트의 ADT를 기반으로 정의된 main 함수

Related Posts

알고리즘 포스팅 글 관련 사항 16 Jun 2020

2D convolution methods 30 Jan 2020

Semantic Segmentation (FCN, Fully Convolutional Network) 08 Dec 2019