연결리스트-자료구조<3>

연결 리스트이 ADT정의

우리는 1,2번글을 통해 단순연결리스트의 코드를 분석했다
하지만 아직까지 연결 리시트의 ADT를 정의하고 정의한 ADT를 구현해보지 않았다

• 올바른 자료구조 공부순서
  1.자료구조 ADT정의
  2.정의한 ADT의 구현
  3.자료구조 활용

단순 연결 리스트이 ADT정의

우리가 만들 연결 리스트의 ADT를 정의해 보나

• ADT정의
  1.void ListInit(List * plist)
  초기화할 리시트의 주소 값을 인자로 전달
  리스트 생성 후 제일 먼저 호출되는 함수

  2.void LInsert(List * plist, LData data)
  리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.

  3.int LFirst(List plist, LData pdata)
  첫 번째 데이터가 pdata가 가리키는 메모리에 저장된다.
  데이터의 참조를 위한 초기화 진행
  참조 성공시 1 실패 시 0 반환

  4.int LNext(List plist, LData pdata)
  참조된 데이터의 다음 데이터가 pdata가 가리키는 메로리에 저장
  순차적인 참조를 위해서 반복 호출이 가능
  참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다
  참조 성공 시 1, 실패 시 0 반환

  5.LData LRemove(List * plist) //LDAT = int
  LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다
  삭제된 데이터는 반환된다
  마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다

  6.int LCount(List * plist)
  리시트의 저장된 데이터 수를 반환한다

  7.void SetSortRule(List plist, int (comp)(LData d1, LData d2))
  리스트에 정렬의 기준이 되는 함수를 등록한다

이렇게 ADT를 정의해 보았고 구현에 앞서 먼저 연결 리시트의 새로운 노드를 추가할때
머리와 꼬리 중 어디에 저장할 것인가에 대해 알아보자
(본 글은 머리에 붙일거다)

• 머리
  장점: 포인터 변수 tail이 불필요하다
  단점: 저장된 순서를 유지하지 않는다

• 꼬리
  장점: 저장된 순서를 유지한다
  단점: 포인터 변수 tail이 필요하다

꼬리에 붙이는 방식은 이전 글에서 알아봤으니 머리에 붙이는 방식을 알아보자

기존에 우리가 보던 연결리스트에서 꼬리가 사라진 상태다 여기서 새로운 노드를 추가해보자

여기서 헤드에 붙이는 일련의 순서를 그림으로 살펴보자

순서를 살펴보자
1.새 노드가 head가 가리키는 노드를 가리키게 한다
2.head가 새로운 노드를 가리키게 한다

보다시피 tail포인터 없이도 새로운 노드를 연결 리스트의 추가했다

(잠깐!!)
ADT구현을 이해하기 앞서 더미노드라는 개념을 알아보자

더미노드

• 더미노드를 사용하는 이유
  1.더미 노드를 사용하면 코드의 분기문을 사용하지 않을 수 있다.
  

더미 노드를 사용하지 않을때는 위의 그림처럼 포인터 변수에 null을 넣어놓고 그다음 추가된 노드에 따라
진행해야 한다

ADT구현

1.더미 노드 리시트를 초기화

그림처럼 head가 더미 노드를 바로 가르킨 상태가 되게끔 초기화를 한다

2.새로운 노드를 생성

코드

void FInsert(List * plist, LData data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = plist->head->next;
	plist->head->next = newNode;

	(plist->numOfData)++;
}

3.데이터 조회

코드

int LFirst(List * plist, LData * pdata)
{
	if(plist->head->next == NULL)
		return 0;

	plist->before = plist->head;
	plist->cur = plist->head->next;

	*pdata = plist->cur->data;
	return 1;
}

3-1 다음 데이터 조회

코드

int LNext(List * plist, LData * pdata)
{
	if(plist->cur->next == NULL)
		return FALSE;

	plist->before = plist->cur;
	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;
	return TRUE;
}

4.노드 삭제

코드

	LData LRemove(List * plist)
{
	Node * rpos = plist->cur;
	LData rdata = rpos->data;

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

5.노드 정렬

코드

void SInsert(List * plist, LData data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	Node * pred = plist->head;
	newNode->data = data;

	while(pred->next != NULL &&
		plist->comp(data, pred->next->data) != 0)
	{
		pred = pred->next;
	}

	newNode->next = pred->next;
	pred->next = newNode;

	(plist->numOfData)++;
}