[Data Structures][04-2] 단순 연결 리스트의 ADT와 구현 [구현중]

목차
Chapter 04. 연결 리스트(Linked List) 2

Chapter 04-2: 단순 연결 리스트의 ADT와 구현

- 정렬 기능 추가된 연결 리스트의 ADT

- 새 노드의 추가 위치에 따른 장점과 단점

- SetSortRule 함수 선언에 대한 이해

- 정렬의 기준을 결정하는 함수에 대한 약속!

- 우리가 구현할 더미 노드 기반 연결 리스트

- 정렬 기능 추가된 연결 리스트

  - 구조체

  - 헤더 파일

- 더미 노드 연결 리스트 구현

  - 초기화

  - 삽입 1

  - 삽입 2

  - 참조 1

  - 참조 2

  - 삭제 1

  - 삭제 2

- 더미 기반 단순 연결 리스트 한데 묶기

 

---

단순 연결 리스트의 ADT와 구현

 배열 기반은 나란히 연결되는데, 연결 리스트의 경우에는 각각의 노드로 연결해야 한다. 배열의 경우는 인덱스 값으로 바로 접근할 수 있지만, 반면 연결 리스트의 경우에는 Linear, 처음부터 쭉 읽어야 한다.

 이제 리스트의 ADT를 보자. 

 

정렬 기능 추가된 연결 리스트의 ADT

 

 

 SetSortRule 함수는 정렬의 기준을 설정하기 위해 정의된 함수! 이 함수의 선언 및 정의를 이해하기 위해서는  '함수 포인터'의 대한 이해가 필요하다.

 

 이전에 사용했었던 연결 리스트의 ADT와 동일한 기능을 사용하지만, 새롭게 정렬 기능 함수를 추가한다. 

 

---

새 노드의 추가 위치에 따른 장점과 단점

 

새 노드를 연결 리스트의 머리에 추가하는 경우

 

장점  포인터 변수 tail이 불필요하다.

단점  저장된 순서를 유지하지 않는다.

 

 

새 노드를 연결 리스트의 꼬리에 추가하는 경우

 

장점  저장된 순서가 유지된다.

단점  포인터 변수 tail이 필요하다.

 

두 가지 다 가능한 방법이다. 다만 tail의 관리를 생략하기 위해서 머리에 추가하는 것을 원칙으로 하자!

 

SetSortRule 함수 선언에 대한 이해

 연결 리스트의 정렬 메커니즘이 이 함수 안에 담겨 있다, 함수 포인터 변수가 쓰인다. 

int (*comp) *comp를 함수 포인터 변수라 한다. 

 

여기서 이해해야 할 것은 int 반환형과 SetSortRule 매개변수이다. 

 

정렬의 기준을 결정하는 함수에 대한 약속!

 정렬 기준을 가지고

 

 

 

우리가 구현할 더미 노드 기반 연결 리스트

 더미 노드란 유효한 값이 없는 노드를 의미한다. 더미 노드 기반 연결 리스트가 일반적으로 쓰인다.

 

---

정렬 기능 추가된 연결 리스트

구조체

노드의 구조체 표현

typedef struct _node
{
	Ldata data;		// typedef int LData
    struct _node * next;
} Node;

 

연결 리스트의 구조체 표현

typedef struct _linkedList
{
	Node * head;		// 더미 노드를 가리키는 멤버
    Node * cur;			// 참조 및 삭제를 돕는 멤버
    Node * before;		// 삭제를 돕는 멤버
    int numOfData;		// 저장된 데이터의 수를 기록하기 위한 멤버
    int (*comp)(Ldata d1, Ldata d2);	// 정령의 기준을 등록하기 위한 멤버
} LinkedList;

 

헤더 파일

 

 

---

더미 노드 연결 리스트 구현

초기화

 

 

삽입 1

void LInsert(List * plist, Ldata data)
{
	if(plist->comp == NULL)		// 정렬기준이 마련되지 않았다면,
    	FInsert(plist, data);	// 머리에 노드를 추가!
    else						// 정렬기준이 마련되었다면,
    	SInsert(plist, data);	// 정렬기준에 근거하여 노드를 추가!
}

 

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)++;							// 저장된 노드의 수를 하나 증가시킴
}

 

삽입 2

여기서 head는 plist의 head이다. head는 멤버 변수이다. 

 

참조 1

 

 

참조 2

 

 

삭제 1

 

 

 

삭제 2

 

 

 

---

더미 기반 단순 연결 리스트 한데 묶기