자료구조(1) 리스트 배열

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

(카드의삽입, 동전의 삽입, 지폐의 삽입 등등)을 가르켜 ADT라고한다.)

 

컴퓨터 공학적 측면에서 단순 구조체(데이터값만 있는)의 정의만으로 wallet이라는 자료형의 정의가 완성되는 것이 아니다. wallet을 기반으로 하는 연산의 종류를 결정하는 것도 자료형의 정의로 일부(지폐의 삽입같은 기능)로 보아야 하고, 이러한 연산의 종류가 결정되었을 때 자료형의 정의는 완성된다.

 

최소한 구조체 wallet의 의는 ADT에 포함시켜야하는가? ㄴㄴ

물론 필요하다면 포함시켜도 된다. 중요한 정보라면 무엇이든 추가할 수 있으며, 그 방법에는 제한이 없다.

하지만 불필요한 것을 포함시키는 것은 바람직하지 않다. wallet을 기반으로 돈을 넣고 꺼내는데 있어서,

구조체 wallet 멤버가 어떻게 구성이 되어 있는지를 알 필요는 없다. 동전의 수를 확인해야한다면, 그에 관련된 연산을 ADT에 추가하는 것이 옳다. 우리는 구조체의 멤버에 직접 적근하는 것에 훨씬 익숙하다. 하지만 이것이 옳은 것인지는 고민해봐야한다. 우리는 파일입출력을 공부하면서 FILE구조체의 내부를 궁금해하지 않았다. FILE의 구조체의 내부를 몰라도 파일과 관련된 연산을 처리할 수 있기 때문이다. 

 

자료구조의 올바른 학습 순서 방법

1. 리스트 자료구조의 ADT를 정의한다(기능을 정의)
2. ADT를 근거로 리스트 자료구조를 활용하는 main 함수를 정의한다(기능을 토대로 main함수 작성)
3. ADT를 근거로 리스트를 구현한다

즉 앞으로 만들 모든 자료구조는 그 내부 구현을 알지 못해도 활용할 수 있도록 구현하도록하는 것이다.

 

리스트의 종류

• 순차 리스트 : 배열을 기반으로 구현된 리스트
• 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트

두 가지로 나뉘는 이유는 리스트의 구현방법의 차이에서 비롯된 것이기 때문에, 이 둘의 ADT가 동일하다고 해서 문제될 것은 없다.

 

리스트의 중요한 특성

• 리스트 자료구조는 데이터를 나란히 저장합니다. 그리고 중복된 데이터의 저장을 막지않습니다.(자료구조 중에서는 중복된 데이터의 저장을 허용하지 않는 경우도 있다)

 

모든 자료구조는 내부적으로 다양한 정보를 담게된다. 그저 데이터만 담는 게 아니라 그 데이터를 효율적으로 저장 및 참조하기 위한 정보들도 담기기 마련이다.

 

본래 데이터의 저장보다 참조가 더 복잡하기 마련이다.

 

 

어떠한 자료구조이건 간에 "자료구조의 구현"과 "구현된 자료구조의 활용"은 완전히 구분되도록 ADT를 정의해야한다

 

굳이 Lfirst 함수를 호출하도록 ADT를 디자인한 이유는, Lnext 함수를 호출할 때마다 다음에 저장된 데이터를 얻을 수 있기때문이다. 이것이 가능한 이유는 리스트 내에서 "데이터의 참조위치"를 기록하기 때문이다. 따라서 처음부터 새롭게 시작하기 위해서는 바로 이 정보를 초기화해야하고 이를 목적으로 LFirst함수의 호출을 요구하는 것이다

 

삭제를 위해서는 탐색이 선행되어야 한다. Lremove 함수가 호출되면, 바로 직전에 Lfirst 또는 Lnext 함수의 호출을 통해서 참조된 데이터가 삭제된다.

 

Lremove 함수가 삭제된 데이터를 반환하도록 디자인한 이유이것이다 만약 반환되는 데이터가 예를들면 malloc으로 만들어진 "Point 구조체 변수의 주소 값"이라면 이 주소값은 동적으로 할당한 결과이기 때문에, 반드시 free함수를 통한 메모리 해제과정을 거쳐야 하기때문이다.

질문 : 메모리의 해제는 리스트가 책임을 져야 한다고 생각하나요?

답변 : 일반적인 리스트는 메모리의 해제까지 책임을 지지 않는다. 왜냐하면 리스트에 저장된 값이 주소 값인 경우, 그리고 그 주소값이 동적 할당의 결과인 경우를 구분하여 메모리의 해제를 진행하도록 하는 것은 무리가 있기때문이다. 때문에 Lremove 함수처럼 데이터를 소멸하는 함수는, 소멸된 데이터를 반환하도록 정의해야 한다. 그래서 메모리 소멸의 기회를 줄 수 있어야 한다. 달리말하면 할당된 메모리 소멸의 책임을 전가해야 한다.

 

배열 기반 리스트의 단점

• 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.
• 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.

 

배열 기반 리스트의 장점

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

 

위의 장단점은 "연결 기반 리스트"를 대상으로 비교한 결과이기 때문에 그것을 배우면 더 정확히 이해가능