열혈 자료구조 - 4-2. 단순 연결 리스트의 ADT와 구현(1)

정렬 기능이 추가된 리스트 자료구조의 ADT

- 순차 리스트, 연결 리스트간 ADT는 달라지지 않음(기능은 동일) 하지만 구현은 달라야 함

- 기반에 따라 효율측면에 따라 추가하고 뺄 수 있음

- 초기화 : 초기화될 리스트를 인자로 전달하고 리스트 생성 후 가장 먼저 호출되어야 함

void ListInit(List* plist);

- 데이터 저장 : 리스트에 데이터를 저장

- 데이터를 HEAD에 추가하는 경우의 장단점

    -> 장점 : Node* TAIL이 불필요하기 때문에 코드를 보기에 수월해짐

    -> 단점 : 저장된 순서를 유지하지 않음(저장 순서와 역순)

- 데이터를 TAIL에 추가하는 경우의 장단점

    -> 장점 : 저장된 순서가 유지됨

    -> 단점 : Node* TAIL이 필요함

void LInsert(List* plist, LData data);

- 저장된 데이터의 탐색 및 탐색 초기화 : 저장된 데이터 중에서 첫번째 데이터를 반환받음. 반환 값은 성공 여부

int LFirst(List* plist, LData* pdata);

- 다음 데이터의 참조(반환) : LFirst 이후의 데이터를 반환받을 때 사용. LFirst -> LNext -> LNext ...

    -> LFirst, LNext를 구분한 이유 : 데이터를 참조할 때 처음부터 참조하겠다라는 것을 명시적으로 해주기 위해

int LNext(List* plist, LData* pdata);

- 바로 이전에 참조(반환)한 데이터를 삭제 : LFirst, LNext 함수의 마지막 반환 데이터를 삭제

LData LRemove(List* plist);

- 현재 저장되어 있는 데이터의 수를 반환

int LCount(List* plist);

- 정렬 : 리스트에 정렬의 기준이 되는 함수를 등록

    -> 중간에 노드를 삽입

void SetSortRule(List* plist, int (*comp)(Ldata d1, LData d2));

    -> 두 번째 매개변수로 함수 포인터를 받음

    -> 반환형과 매개변수를 가지는 함수를 받음

int WhoIsPrecede(int d1, int d2)
{
	if(d1 < d2)
		return 0;    // d1이 정렬 순서상 앞선다.
	else
		return 1;    // d2가 정렬 순서상 앞서거나 같다.
}

SetSortRule(&list, WhoIsPrecede);		// 비교를 하는 함수를 전달

더미 노드를 사용하는 연결 리스트

- 더미를 사용하지 않는 경우 첫번째 노드와 그 이후의 노드의 삽입, 삭제, 참조의 코드가 구분됨

- 억지로 짜 맞추면 코드가 오히려 이상하기 때문에 더미 노드를 사용하면 깔끔해짐

- 더미 노드를 사용하면 첫번째 노드로 고정시켜 유효한 데이터는 그 이후의 노드에만 있게 만듬

- 그렇기 때문에 첫번째 노드를 삽입, 삭제, 참조하려는 구문을 없애고 일관된 패턴을 구성할 수 있음