열혈 자료구조3

참고문헌 - 윤성우 <윤성우의 열혈 자료구조>

♨ 개인적 해석이 들어간 글임으로, 인지하지 못한 오류가 있을 수 있습니다 ♨

 

Chapter 3. 연결 리스트(Linked List) 1

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

▣ 자료구조에서의 추상 자료형 (Abstract Data Type)

추상 자료형, ADT(캡스 아님)는 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지 나열한 것을

의미한다

예) 지갑의 기능을 나열해보자면

 - 카드의 삽입/추출

 - 동전의 삽입/추출

 - 지폐의 삽입/추출

   위와 같이 기능이 이루어지는 과정(지폐를 넣기 위해서 지갑을 완전히 열고, 지폐를 넣는 공간에 지폐를 넣고

   지갑을 닫는다)에 대한 언급 없이, 기능만 나열한 것

 

교재에서는 추상 자료형에 대한 추가적인 설명을, 구조체를 이용한 자료형에 대한 설명으로 이루어져 있다

(추상 자료형이 왜  "자료형"이라는 이름이 붙여졌는지에 대한 설명)

위 코드는 Wallet이라는 자료형(Wallet이라는 구조체 자료형)의 정의이다

그러나 컴퓨터 공학적 측면에서 위의 구조체 정의만으로 Wallet이라는 자료형의 정의가 완료된 것은 아니라고한다

Why? → Wallet을 기반으로 하는 연산의 종류를 결정하는 것도 자료형 정의의 일부로 보아야 하고,

            이러한 '연산'의 종류가 결정되었을 때 자료형의 정의가 완성된다

 

(∴ 위 코드는 Wallet이라는 자료형 정의의 '일부' 정도인 것이다,

 여기에 Wallet이 사용하는 '연산'의 종류까지 있어야 완전한 정의)

 

여기서 말하는  '연산'이란 사칙연산 같은 기본 연산자를 의미하는 것이 아닌,

Wallet을 기반으로 할 수 있는 연산, Wallet이 지갑을 의미했으므로, 돈을 꺼내거나 넣는 연산을 의미한다

 

결론 - 자료형의 정의는 기능 + 연산

 

▣ 구조체 Wallet의 추상 자료형(ADT) 정의

Wallet도 자료구조의 일종이다! -> 데이터를 저장하는 방법

※ 구조체 정의(멤버변수는 뭐가 있는지... 멤버함수는 어떤게 좋은지.... 밥은 뭐 좋아하는지...)가

   ADT에 포함되어 있지 않더라도 괜찮다

 ->  Wallet을 기반으로 하는 연산이 필요로 하는 정보가 이미 충분하게 있기 때문

      (돈을 넣고, 빼는데에 구조체의 멤버 구성까지 알 필요는 없다)

 

 

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

앞으로 나올 자료구조들에 대해 적용할 학습 순서

  1. 자료구조의 ADT를 정의

  2. ADT를 근거로 자료구조를 활용하는 main함수를 정의

  3. ADT를 근거로 자료구조를 구현

 

※ main함수 정의가 자료구조를 구현하는 것 보다 후순이지만 해당 자료구조 사용자에게

   사용방법 이외의 불필요한 부분까지 알도록 부담주지 않기위한 순서라 한다

(내부 구조 - 예: Wallet의 멤버 구성 -을 알지 못해도 활용할 수 있도록)

 

 

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

▣ 리스트(List)의 이해

리스트라는 자료구조는 구현 방법에 따라서 2가지로 나뉜다

 1. 순차 리스트 : 배열을 기반으로 구현된 리스트

 2. 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트

 

-> 이 둘의 구현방법의 차이가 있지만, ADT는 동일하다 (구현방법에 초점을 두어 ADT를 다르게 하기도 한다)

※ 하나의 자료구조에 대해 ADT가 다르다는 뜻은 ADT에 표준이 없다는 의미이다(그렇다고 주먹구구식은 아니다)

 

리스트의 가장 기본적(base)이고도 중요한(Important) 특성

- 데이터를 나란히 저장한다

- 중복된 데이터의 저장이 허용된다(중복 검사X) - 수학의 '집합'과 다르다 e말이야

 

▣ 리스트의 ADT

위의 언급된 리스트의 특징을 기반으로 ADT를 작성해보자

※ 나란히 저장하는 방법을 작성하는 것이 아니라, 그러한 특성을 기반으로하는

예) A라는 카드에 전투의 함성 효과가 있다면, 브란을 이용할 생각을 하라는거지,

     A가 나올때 전투의 함성을 시전하는 코드를 만들라는게 아니다라고 생각하자 E말이야

 

자료형 LData는 리스트에 저장할 데이터의 자료형에 제한을 주지 않기위해 typedef 선언한 것이다

-> 위 정보들 만드로 리스트의 활용방법을 정확히 이해할 수는 없으나, 어느정도 예측은 가능해야 한다

 

 

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

main함수 안에서 실제로 리스트가 사용되는 모습을 보면

리스트의 ADT에서 소개하는 함수들의 기능을 보다 더 이해할 수 있다

 

1. 리스트 초기화

 자료구조에는 저장되는 정보와 저장된 정보를 효율적으로 관리, 참조하기 위한 정보도 포함된다

따라서 이와 관련된 변수들의 초기화가 선행되어야하며, 이를 수행하는 것이 ListInit 함수이다

-> 그냥 리스트 객체를 만들고 생성자가 아닌 함수로 객체를 초기화 한다는 느낌이다

 

2. 데이터 저장 방법

리스트의 주소를 첫 번째 인자로, 리스트에 담을 데이터를 두 번째 인자로 전달하고 있다

 

3. 리스트에 저장된 데이터 참조

앞서 리스트 ADT에서 첫 번째로 저장된 데이터에 접근하기 위해서 LFirst 함수를 사용하였고

LNext함수를 이용하면 그 다음에 저장된 데이터에 접근할 수 있었다

(list안에 a - b - c - d가 있다면 LFirst로 a에 접근할 수 있고,

LNext로 b에 한번 더 LNext를 호출하면 c에 접근이 가능하다)

 -> 여기서 한가지 추론할 수 있는 점 : 리스트 내에서 '데이터의 참조 위치'를 기억한다

(함수를 호출하는 것만으로 그 다음 저장된 데이터에 접근할 수 있으니까 - MSG 첨가하면 진짜 맞는듯)

 

4. 저장된 데이터 삭제

삭제는 LRemove 함수를 통해 이루어진다

여기서 주목해야할 점은 LRemove함수의 호출되는 타이밍이다

-> LFirst / LNext가 호출된 후!

 

1~4의 내용이 어떻게 구현되는지는 이후에 설명된다

 

▣ 배열기반으로 리스트 구현하기1 : 헤더파일의 정의

배열 기반의 리스트 구현을 위한 헤더파일

위의 정의된 구조체 ArrayList에는 데이터의 저장공간이 배열로 선언되었고

저장된 데이터의 수를 기록하기 위한 멤버(numOfData)도 존재한다

참조의 위치를 기록하기 위한 curPosition도 있다

 

또한 LData에 대한 typedef를 int로 선언했는데 int 대신 다른 자료형을 넣음으로써

다양한 종류의 데이터를 저장할 수 있게 만들었다

 

또한 ArrayList에 List라는 다름을 붙여준 것도 추후에

typedef를 통해 LinkedList도 List라는 이름을 붙여주어

main함수를 변경하지 않고도, main 내에서 기존에 사용하던 (array)리스트를 Linkedlist로 대체할 수 있다

 

▣ 배열을 기반으로 리스트 구현하기2 : 삽입과 조회

함수의 정의

1. ListInit - 초기화

curPosition에는 배열의 인덱스 값이 저장된다

그 인덱스 값을 이용하여 LFirst와 LNext함수가 참조해야할 배열의 위치를 알 수 있다

(현재 정의된 내용은 적힌대로 아직 아무것도 데이터가 담겨있지 않다는 뜻이다)

 

 

2. LInsert - 데이터 저장(삽입)

기존 배열에 저장되어있는 데이터의 인덱스, 바로 그 다음 인덱스에 데이터 삽입

 (∵ 저장되는 인덱스 = 저장되어있는 데이터의수)

 

LFirst는 내부에서 배열의 첫 번째 데이터를 참조한다(curPosition 변수를 이용)

반면 LNext에서는 현재 인덱스가 가리키는 위치(curPosition의 수)를 증가시켜 그 다음 위치의 데이터에 접근한다

 

▣ 배열을 기반으로 리스트 구현하기3 : 삭제

LRemove함수가 호출되면 curPosition을 확인해서, 조회가 이루어진 데이터의 위치를 확인한 다음 그 데이터를 삭제한다

이때 삭제가 이뤄진 후 해당 위치 이후에 저장되어 있던 데이터들의 위치가 한 단위씩 앞으로 이동한다

like this!

 참조위치를 하나 되돌리는 이유

-> 데이터를 삭제해도 curPosition은 그 위치의 인덱스를 의미하기 때문에 LNext함수에 영향을 주지 않기 위해서는

    그 이전 위치의 인덱스를 가리켜야 한다

 

▣ 리스트에 구조체 변수 저장하기1 : 구조체 Point와 관련 함수들의 정의

앞서 나온 리스트에는 정수를 저장하였다

이번에는 '구조체 변수의 주소값(포인터)'를 저장해려고 하신다

리스트에 저장할 구조체는 다음과 같다

구조체와 구조체와 관련 있는 함수들까지 함께 정의하여 활용할 예정이다

 

비교 함수 PointComp의 반환값은 아래와 같다

 - 두 Point 변수의 xpos만 같을 경우 : 1
 - 두 Point 변수의 ypos만 같을 경우 : 2
 - 두 Point 변수의 멤버가 모두 같을 경우 : 0
 - 두 Point 변수의 멤버가 모두 다를 경우 : -1

 

위 정보들을 토대로 만든 Point.h 와 Point.cpp (교재는 C언어로 되어 있지만 cpp로 했다 왜? : 그냥)

 

Point.h

Point.cpp

 

▣ 리스트에 구조체 변수 저장하기 2 : 구조체 Point와 관련함수들의 정의

위의 Point 구조체의 주소를 담는 리스트를 기존에 정수를 담았던 리스트를 개조해서 사용해보자

typedef ind LData   -> typedef Point * LData  (include "Point.h")

ArrayList.h 에서 변경된 내용

이 내용이 반영된 Main 함수를 만들어보면

 

실행 결과

 

LRemove 함수에서 반환값이 삭제된 데이터인 이유는

Point 구조체 변수가 new 키워드를 통해 동적할 당되었기 때문에

리스트에서 삭제할 때 delete를 통해 메모리 해제를 해줘야 하기 때문이다

 

▣ 배열의 장점과 단점 그리고 연결 기반 리스트

 배열 기반 리스트의 단점

- 배열의 길이가 초기에 결정되어야 한다(길이 변경 불가)

- 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다

 

 배열 기반 리스트의 장점

- 데이터의 참조가 쉽다 (인덱스 값을 기준으로 어디든 한번에 참조가 가능하다)