안녕하세요. 오늘은 배열로 구현한 리스트에 대해 알아보겠습니다. (리스트는 배열 뿐만 아니라 포인터로도 구현이 가능합니다.)
배열이란 ‘동일한 데이터 타입을 연속해서 정적인 크기만큼 할당받는 형태’라고 볼 수 있겠는데요. 이런 배열의 특징을 활용하면 리스트를 만들 수 있습니다.
그렇다면 리스트란 무엇일까요? 간단하게 표현하자면 ‘요소들 사이에 선형관계가 있는 동일한 요소들의 모음’라고 할 수 있겠네요.
리스트는 ‘unsorted list’와 ‘sorted list’로 나뉘는데요, 먼저 ‘unsorted list’에 대해 알아볼게요.
(클래스, 배열에 대한 기초지식이 필요합니다. 관련 지식이 없으신 분들께서는 먼저 클래스와 배열에 대한 정보를 접하고 오셔야합니다.)
UnsortedList란? 명칭에서 짐작할 수도 있겠지만 요소들을 어떠한 기준없이 정렬해서 나열하는 데이터 구조입니다. 동일한 요소의 데이터들을 추가하고 제거하고 수정하고 조회하고 비우고 등의 작동 메커니즘이 UnsortedList라는 틀을 통해 이뤄진다고 생각하시면 됩니다.
UnsortedList의 Class
member variable(멤버변수): length(UnsortedList에 들어있는 데이터의 갯수), Item[](데이터가 저장될 배열), CurrentPosition(특정 배열 칸에 접근하기 위한 index)
member function(멤버함수): Add(추가), Delete(삭제), MakeEmpty(비우기), IsFull(꽉 찼는지 여부), LengthIs(들어온 데이터 갯수), RetrieveItem(특정 데이터 찾기), ResetList(index를 -1로 초기화), GetNextItem(index에 +1 연산)
다음은 UnsortedList의 각 멤버함수 별 설명입니다. UnsortedList를 크기5짜리 배열로 묘사하고 설명을 진행한 점 참고해주세요.
Add(UnsortedList에 데이터를 추가한다)
그림1의 배열에 ‘5’를 넣는다면
그림2처럼 제일 앞에 위치한 index부터 데이터가 들어가게 됩니다. 이 상태로 ‘10’을 넣는다면
그림3처럼 ‘10’이 넣어지겠죠. 추가로 ‘2’를 넣는다면 어떻게 될까요?
그림4처럼 ‘2’가 넣어집니다. Add 부분에서 제가 말씀드리고 싶은것은 이것입니다. UnsortedList는 어떠한 정렬기준 없이 넣어지는 순서대로 데이터가 나열된다는 것을 말이죠. 그래서 크기가 크든 작든 뒤의 남은 공간에 데이터를 넣어도 이 데이터 정렬기준(들어온 순서대로 차례대로 정렬)은 변하지 않을 것입니다.
Delete(UnsortedList의 데이터를 삭제한다)
그렇다면 채워진 배열에서 데이터를 삭제를 한다면 어떤 방식으로 나열이 이뤄질까요?
방금 세 개의 데이터로 채워진 배열에서 ‘10’을 삭제해보았습니다.
그림5처럼 빈공간이 있는 상태로 배열을 내버려둬도 괜찮을까요? 아닙니다. 리스트는 선형관계가 특징이기 때문에 데이터 사이에 빈 공간이 있으면 안되며 그렇기에 저 빈공간이 없어져야합니다. 어떻게 처리가 될까요?
바로 그림6처럼 맨뒤에 있는 데이터(‘2’)를 데이터가 지워진 빈공간(Item[1])으로 옮기는 것이 UnsortedList에서 Delete로 빈자리가 생겼을 경우의 방법입니다. 만약 ‘10’이 아니라 ‘5’가 지워졌다면 ‘2’는 Item[0]의 자리로 이동 할 것입니다. 정리: unsorted list에서 데이터가 지워진다면 그 빈자리는 맨 뒤에 있던 데이터가 채움으로써 메꿔진다.
MakeEmpty(UnsortedList의 데이터를 모두 제거한다)
MakeEmpty 멤버함수는 이름처럼 unsortedlist를 비우는 함수입니다. 그림6에 있었던 ‘5’, ‘2’가 삭제됐네요.
LengthIs(UnsortedList에 속한 데이터의 갯수를 파악한다)
LengthIs 멤버함수는 현재 UnsortedList안에 데이터가 얼마나 들어왔는지 파악할 수 있는 함수입니다.
예를들어 그림8 상태의 UnsortedList에 LengthIs 멤버함수를 사용한다면 5개의 데이터가 들어가있는 상태이기 때문에 ‘5’라는 return값을 반환할 것입니다.
IsFull(UnsortedList에 남은 자리가 있는지 파악한다.)
IsFull 멤버함수는 현재 UnsortedListd안에 데이터가 꽉 찼는지의 여부를 검사해주는 함수입니다.
그림9처럼 아직 꽉찬 상태가 아닐 때는 false를 반환할 것이고
그림10처럼 꽉찬 상태일때는 true를 반환할 것입니다.
RetrieveItem(UnsortedList에서 특정 데이터를 검색한다)
RetrieveItem 멤버함수는 이름처럼 특정 item의 정보를 검색하는 함수입니다.
‘4’의 위치를 찾는다고 했을 때 우리는 그림11을 본 후 ‘[2]에 있네’라고 생각할 수 있지만 UnsortedList는 어떻게 판단할 수 있을까요? 이때 UnsortedList의 멤버변수인 ‘CurrentPostion’와 멤버함수인 ‘GetNextItem’을 사용합니다.
그림12를 보면 CurrentPosition이 -1로 설정되어있는 것을 보실 수 있습니다. 현재 UnsortedList 속의 어떠한 값도 가리키고 있지 않죠. 하지만 ‘4’를 찾기로 마음먹은 이상 CurrentPosition을 사용하여 그 위치를 가리킬 것입니다.
그림13에서 CurrentPosition이 0으로 증가하였습니다. 바로 ‘GetNextItem’함수를 사용했기 때문입니다. ‘GetNextItem’은 CurrentPosition의 값을 1씩 증가시켜 UnsortedList 안의 값을 하나하나 살펴볼 수 있도록 도와주는 것이죠. 자 그렇다면 설명은 잠시 멈추고 마저 ‘4’를 찾아보도록 하죠. 현재 [0]에 위치한 값은 ‘4’가 아니라 ‘3’이네요.
그림14에서 CurrentPostion은 ‘4’를 찾은 것이 아니기 때문에 ‘GetNextItem’함수가 다시 1 증가시켰습니다. 이번에는 [1]에 접근했는데요, 역시 ‘4’가 아닙니다.
중요: 참고로 이 과정은 찾을 때까지 혹은 Length값 끝에 도달할 때까지 반복됩니다.
그림15에서 드디어 CurrentPostion이 ‘4’가 위치한 [2]에 도달했습니다. 이로써 UnsortedList는 자신이 가진 데이터 속에 ‘4’가 있다는 정보와 위치 또한 알게되었습니다.
그림16에서 CurrentPostion이 다시 처음 설정되있었던 ‘-1’로 돌아가있는 것을 확인할 수 있습니다. ‘ResetList’라는 UnsortedList의 멤버함수를 사용했기 때문입니다. RetrieveItem 함수를 쓰는 동안 CurrentPostion이 [2]까지 이동했었기 때문에 추후에 다시 사용하기 위한 초기화 작업이라고 생각하시면 됩니다.
만약 찾으려는 값이 UnsortedList 속에 없어서 데이터 끝까지 CurrentPostion이 이동하게된다면 RetrieveItem은 찾으려는 값이 없다는 것을 UnsortedList에게 알려줄 것이며 추후에 검색기능을 재사용 할 것을 대비해서 CurrentPosition은 ‘ResetList’를 통해 ‘-1’로 초기화됩니다.
배열 리스트에서 UnsortedList를 다뤄보았는데요 개인적으로 구현이 쉽다고 생각했습니다. 다음에 다룰 SortedList는 어떨지 궁금하네요. 그러면 다음 주제인 SortedList를 가지고 돌아오도록 하겠습니다. 혹시 글에서 주제와 관련되어 오류가 있는 내용이 있다면 댓글로 피드백 부탁드리겠습니다. 글 보러 와주신 모든 분들 정말 감사합니다.
