[자료구조] 리스트(unsorted & sorted list) c++ [컴공과고씨]

* 참고서적 c++ plus data structures

* 전체코드는 https://github.com/goragoraki/Data-Structure 에서 볼 수 있습니다.

 

리스트는 배열과 같이 원소들을 저장하고 있는 것을 말합니다.

이 리스트를 두 개로 나눕니다. 

1. 비정렬 리스트

2. 정렬 리스트.

책에서는 class를 사용하여 리스트에 대해 설명하고 있습니다.

 

ItemType() 

이 class 경우 두 리스트에서 

ItemType()

이렇게 구성이 되어있습니다.

리스트에 원소를 넣을 때 우리는 ItemType() 객체를 넣어주는 것입니다.

우리는 Initialize()를 통해서 value에 값을 초기화 합니다. 즉, value 값이 실제 원소 값이 되는 것이죠.

그 생성한 ItemType() 객체를 리스트에 넣어주는 형식인 것이죠.

 

비정렬 리스트

ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ 이런식으로 칸이 있으면 각 칸마다 원소를 넣어주는 것이죠.

정렬를 하지 않기 때문에 그냥 앞에서 순서대로 채워주게 됩니다.

UnsortedType

UnsortedType() 객체의 경우 이런식으로 구성이 되어있습니다.

info가 ItemType()의 객체를 담는 배열이고 length를 이용하여 리스트에 insert를 해줍니다.

InsertItem()은 info[length]에 값을 넣어주고 length의 값을 1을 늘려주면 됩니다.

GetNextItem()은 말 그대로 다음 item 정보를 불러오는 것입니다. 이것은 currentPos를 이용합니다.

currentPos가 초기 -1로 시작하여 함수가 호출되면 currentPos+1을 하고 info[currentPos]의 값을 가져오는 식입니다.

ResetList()는 currentPos를 -1로 만들어 다시 처음부터 리스트의 값을 가져올 수 있게 만듭니다.

DeleItem() 은 삭제하고 싶은 값을 처음부터 읽으면서 찾은 후 삭제합니다.

주의해야할 것은 리스트 중간에 있는 값이 삭제 되면 리스트가 중간에 비기 때문에 이것을 방지하기 위해

맨 뒤에 있는 length-1에 들어있는 값을 삭제 된 자리에 넣어주고 length - 1을 해주어야 합니다.

*정렬이 되어있지 않기 때문에 binary search는 불가합니다.

 

정렬 리스트

정렬 리스트는 리스트가 정렬이 되어있는 것을 말합니다.

SortedType() 같은 경우는 비정렬 객체와 구성은 같다.

하지만 비정렬 리스트의 insert 부분과 deleltem 함수 부분을 수정하여 정렬 되어지도록 만들어주어야한다.

그래서 insert를 할 때 앞에서 부터 리스트를 검사하면서 더 작은 값이 나올때 까지 이동한다.

값을 찾으면 그 자리의 값 부터 한 자리 씩 쭉 뒤로 밀어주어 자리를 만든 후 값을 넣어준다.

ex) 현재 리스트 : 1234789     넣을 값 : 5

1. 앞에서 부터 리스트 검사 -> 7을 만남 7>5 이므로 멈춤.

2. 5가 들어갈 자리는 만들어 줌. 1234 ㅁ 789.

3. 5를 넣어줌. 1234 5 789 이런식으로 작동한다.

delete같은 경우는 정렬 리스트이기 때문에 binary search를 사용하여 삭제할 값을 찾을 수 있다.

삭제한 후 맨 뒤에 값을 앞으로 땡기면 정렬이 무너지기 때문에 삭제한 뒤의 값부터 모든 원소를 앞으로

땡겨주는 작업을 해주어야한다.

12345678에서 5를 삭제하면

1234 ㅁ 678

1234 678 이런식으로.

 

시간 복잡도

OPERATION	UnsortedList	SortedList
RetrieveItem ( 값을 찾는 함수)	O(N)	O(N) linear search O(logN) binary search
InsertItem              Find              Put              Combined	O(1) O(1) O(1)	O(N) search O(N) moving down O(N)
DeleteItem             Find               Put                          Combined	O(N) O(1) swap O(N)	O(N) search O(N) moving up O(N)